CODEWITHSUNDEEP
algorithmtreeavl-treeb-tree
user15230795
user15230795

Reputation:

Building AVL tree in O(n)?

In self balancing trees like AVL trees, inserting a node take O(log n) where n is the current number of nodes in tree.

Let's suppose I want to build a new AVL tree from scratch with the following values: 1,2,3,4...n Is there a way I can do this in O(n) instead of the traditional way that will take O(n log(n))?

Upvotes: 1

Views: 174

Answers (1)

Lionel Foxcroft
Lionel Foxcroft

Reputation: 1727

Yeah, it is possible. The idea behind it would be that you have a function that takes a range [x, y], and cuts it into two ranges [x, n), (n, y], makes a node with the value n, and then adds its two children by calling itself with those two ranges as its parameters.

Upvotes: 1

Related Questions