Test: Binary Search Trees- 2

Key to be searched 273:

• I) 81, 537, 102, 439, 285, 376, 305 is not correct
  We cannot go to 376 from 285 as 273 is smaller than 285.
• II) 52, 97, 121, 195, 242, 381, 472 is not correct.
  We cannot go to 472 from 381 as 273 is smaller than 381.
• III) 142, 248, 520, 386, 345, 270, 307 is correct

• 550, 149, 507, 395, 463, 402, 270 is not correct. We cannot go to 463 from 395 in search of 273

A: I and IV are not in ascending order 
B: If 439 is root, It should be 1st element in preorder 
D: IV is a postorder sequence of some BST with 149 as the root, => False

²ⁿC_n/(n+1) = ⁶C₃/4 = 5

A perfect BST with all black nodes doesn't violate any of the Red-Black tree properties.

Both recoloring and rotation operations are used during insertion and deletion.

The recurrence relation for the recursive function is T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
= 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^i) + (2*i - 1) * (n/2)
Where i = lg(N)
= lg((2n - 1) / 2)
O(c * T(N / 2^i) + (2*i - 1) * (n/2)) reduces to
O((2*i - 1) * (n/2))
O((2*( lg((2n - 1) / 2)) - 1) * (n/2)) ...sub the value of i.
O(n * ln(n))

AVL tree is a balanced tree.
AVL tree's time complexity of searching = θ(logn) 
But a binary search tree, may be skewed tree, so in worst case BST searching time = θ(n)

O(m+n) as we can first perform inorder on both the trees and store them in two separate arrays. Now we have two sorted sequences and we can merge them in O(m+n) using standard merge algorithm and on the final sorted array we can use the binary search to create the tree using Recursion. Recursively adding middle element at the root and repeating the same process for left and right subarrays.

Time taken to search an element is where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be which is Which is] which can be written as.

AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees Following is the most unbalanced AVL tree that we can get with 7 nodes

A Binary Search Tree is AVL if balance factor of every node is either -1 or 0 or 1. Balance factor of a node X is [(height of X->left) - (height of X->right)]. In Tree B, the node with value 50 has balance factor 2. That is why B is not an AVL tree.

Refer following for steps used in AVL insertion. AVL Tree | Set 1 (Insertion)

After insertion of 70, tree becomes following

We start from 50 and travel up. We keep travelling up till we find an unbalanced node. In above case, we reach the node 60 and see 60 got unbalanced after insertion and this is Right Left Case. So we need to apply two rotations

See Splay Tree, AVL Tree and Red Black Tree

The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Following are C implementations of left-rotate and right-rotate 1

Red Black Tree with n nodes has height <= 2Log2(n+1) AVL Tree with n nodes has height less than Log_φ(√5(n+2)) - 2. Therefore, the AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree.

Refer Red Black Tree Insertion and AVL Tree Insertion