Question

Let T1 and T2 be AVL trees such that the largest key in T1 is less than

the smallest key in T2. Give an algorithm (in psuedocode) for procedure JOIN-AVL-
TREES(T1, T2) that joins these two AVL trees. The runtime should be O(log n),

where n is the size of the resulting AVL tree. Can you explain how can we achieve this and why is the complexity such that?

Answer 1

We will begin by computing the heights ,H1 of T1 and H2 of T2. this will be taking time as O(H1+H2): we have to simply traverse the path begin from root , if balance factor is -1 than go towards left child , if balance factor is positive than go towards right child and if the balance factor is 0 than can go to any of the children until you reach leaf node.

Assume that H1>=H2 and the other cases are symmetric.

Next Step, DELETE the smallest element (let X) from T2 leaving T2' of Height H , this will take O(H2) time complexity.

find a node V on the rightmost path from the root of T1 , whose height is either H or H+1 , this can be illustrated as follows:

V<--root(T1)

H'<--H1

while H'>H+1 do

if balance factor (V) = -1

then H'<--H'-2

else

H'<--H'-1

V<--rightchild(V)

This will take O(H1) time.

Let U denotes the parent of V , from a new tree whose root contains the key X , whose left subtree is the subtree which is rooted at V and whose right subtree will be T2'.

NOTE: this is a valid binary search tree, since all the key of the subtree which are rooted at V in T1 and hence it is Smaller than X and by construction , X is smaller than or equal to all elements in T2'. The balance factor of the root of this new tree is H-H'. which will be valued to be either -1 or it will be 0. hence the new generated tree is a valid AVL TREE.. the height of this new tree is H'+1, which is one bigger than V's height.

Let the root of this new tree is the right child of U in place of V again, since all the keys in this new tree are at least as big as U, this will results in a valid binary search tree. this part of construction takes constant time.

Now when we will be in the INSERT Algorithm, we will go up to the tree, starting point will be U fixing balance factorand perhaps doing a rotation. this will take O(H1) time. NOTE that the correctness and efficiency will be follows from the condition which is at U before this process is begun is a condition that can arise during INSERT algorithm.

Since H1,H2 belongs to O(log n), hence the total time taken by this algorithm is in O(log n).

Answer 2

FTrst, compute the heig hts ot T, and T, Then, traverse siom te root, oing to let child om -he root , Qoing to left child the balance actor 1s child Children the - 1s posihve and to an o te balance factor is o unti ou each a lea -Assume that, h, hi Next , delete the smallest element heiqht b. Jis takes -Then,-fnd a node、v, on he -the hoot to T , uhose height? Scannedwith

-Hen balance factor C)=-1 if 4. 5 else 8 7% algorithm takes O(h) fine. Let denote theborent e v' Νοω , rm a neω-tree ωhose root contains the ke גיいhose left subtree 9s the sub tree scored arv. and whose tight Sub tree s T2 -And -ths re ง tree fs a valid binarq search tree. because all s in Sub tree are vooted at 'u are în T Here 1s Smaller lhan or eduat to all elements in The balance actor e roor et reuo tree nce factor So -this rew tree C Scanned with CamScanner is a valid Avi tree

The he ight new tree i-e., 1 bigger than new ree be the siht child let the aoor ain, becau se all keys n rew tree are at leat is a valid binary Search free above new tree Construchion takes Constant -time we' qo up n tree, Start fiom 'u and wi take χ1nq the balance factors Since helghts h,.h e o(log n) he total tme taken bu -ts algoritbm Scanned with CamScanner