Binary Search Tree(BST)

Binary Search Trees

 

• left subtree contains nodes with keys less than the parent's key
• right subtree contains nodes with keys greater than the parent's key
• both the left and right subtrees must also be binary search trees

Searching in BST

search_BST(x,T) //x = item to be searched 
{
z←T
while z ≠ null do
{
if x == z.key
return z 
else if x < z.key
z ← z.left 
else
z ← z.right 
}
return z 
}

Finding Minimum

Min_BST(T) {
z← T
while (z.left ≠ null)
z ← z.left return (z)
}

Insertion in BST

Insert_BST(x,T) 
{ create new node (n) 
n.key←x
n.left ← null
n.right ← null
if (T == null) then
T← n 
else
z ← search_BST(x,T) /*Discussed before*/
n.parent ← z
if x < z.key then
z.left ← n 
else
z.right ← n 
}

Deletion in BST : leaf node

just delete it

Deletion in BST : having a single child

target node for deletion: z
Deleting a node having either left or right child empty (NULL)

 

Deletion in BST : having both left and right child • Two sub-cases

target node for deletion: z
Deleting a node having both left and right child present

Deletion Pseudo-code

Transplant

Transplant (T, u, v)
{
if u.parent == null then //u is the root node
T ←v
else if u == u.parent.left
u.parentarent.left ← v 
else
u.p.right ← v 
if v ≠ null
v.p ← u.parent 
}

Successor/"next value" to a Node

• successor of a node is the left-most leaf of its immediate right sub-tree

Finding Successor 1

if z has a right child
the successor is the minimum in the subtree of z.right

Finding Successor 2

if z.right is null, go up until the lowest ancestor such that z is at its left subtree

successor(z,T)

If z.right ≠ null then min(z.right) 
y ← z.parent
While y≠null and z = y.right
z←y
y ← y.parent 
return(y)

Complexity (if balanced)

• Insertion: O(log n)
• Deletion: O(log n)
• Search: O(log n)