closed by
543 views

3 Answers

0 votes
0 votes

INSERTING AN OBJECT INTO AVL TREE WITH  n NODES

AVL tree with  nodes forms a tree structure of height log n

now to this tree we are adding an object

When u add a node it might make the tree unbalanced and therefore u have to reorder it which is O(log n)

now ur performing this on a log n height tree

so O(log log n)

0 votes
0 votes
It  will be O(log n) .... as rotations take constant time bcz few pointers only change there references. aslo height of AVL remains (log n) throughout by balancing its height. here updating height and getting balanced factor also takes constant time..thus time complexity of AVL insert is (log n) .  

Refer geeksforgeeks AVL tree insert portal .

Related questions

10 votes
10 votes
5 answers
1
Tushar Shinde asked Jan 18, 2016
4,022 views
The number of ways we can insert elements { 1, 2, 3, .... 7 } to make an AVL tree, so that it does not have any rotation are _______ ?
0 votes
0 votes
2 answers
2
Tushar Shinde asked Jan 15, 2016
908 views
I am stuck after JAN. It is not getting balanced even after 2 rotations. Can somebody help?
2 votes
2 votes
5 answers
3
Hardik Vagadia asked Nov 13, 2017
881 views
A 4-ary tree,i.e. each node has either 0 or 4 children tree has 20 leaf nodes. Then the total number of nodes in the tree are ____.