Binary Search Trees - PowerPoint Presentation ,Engineering, Semester Notes | EduRev

: Binary Search Trees - PowerPoint Presentation ,Engineering, Semester Notes | EduRev

 Page 1


Binary Search Trees (13.1/12.1)
• Support Search, Minimum, Maximum, 
Predecessor, Successor, Insert, Delete
• In addition to key each node has 
– left = left child, right = right child, p = parent
• Binary search tree property:
– all keys in the left   subtree of x = key[x] 
– all keys in the right subtree of x = key[x]
• Resembles quicksort
Page 2


Binary Search Trees (13.1/12.1)
• Support Search, Minimum, Maximum, 
Predecessor, Successor, Insert, Delete
• In addition to key each node has 
– left = left child, right = right child, p = parent
• Binary search tree property:
– all keys in the left   subtree of x = key[x] 
– all keys in the right subtree of x = key[x]
• Resembles quicksort
In-Order-Tree Walk
• Procedure In-Order-Tree(x) (O(n)) 
– In-Order-Tree(left[x])
– print key[x]
– In-Order-Tree(right[x])
7
5
6 3
6 2
8
9
4
Page 3


Binary Search Trees (13.1/12.1)
• Support Search, Minimum, Maximum, 
Predecessor, Successor, Insert, Delete
• In addition to key each node has 
– left = left child, right = right child, p = parent
• Binary search tree property:
– all keys in the left   subtree of x = key[x] 
– all keys in the right subtree of x = key[x]
• Resembles quicksort
In-Order-Tree Walk
• Procedure In-Order-Tree(x) (O(n)) 
– In-Order-Tree(left[x])
– print key[x]
– In-Order-Tree(right[x])
7
5
6 3
6 2
8
9
4
Searching (13.2/12.2)
Searching (O(h)):
Given pointer to the root and key
Find pointer to a nod with key or nil 
Procedure Tree-Search(x,k) 
if  k  = key[x], then return x
if  k  < key[x] 
then return Tree-Search(left[x]) 
else return Tree-Search(right[x])
Iterative Tree-Search(x,k) 
while k  ? key[x] do
if k  < key[x] then x ? left[x]
else x ? right[x]
return x
7
5
6 3
6 2
8
9
4
Page 4


Binary Search Trees (13.1/12.1)
• Support Search, Minimum, Maximum, 
Predecessor, Successor, Insert, Delete
• In addition to key each node has 
– left = left child, right = right child, p = parent
• Binary search tree property:
– all keys in the left   subtree of x = key[x] 
– all keys in the right subtree of x = key[x]
• Resembles quicksort
In-Order-Tree Walk
• Procedure In-Order-Tree(x) (O(n)) 
– In-Order-Tree(left[x])
– print key[x]
– In-Order-Tree(right[x])
7
5
6 3
6 2
8
9
4
Searching (13.2/12.2)
Searching (O(h)):
Given pointer to the root and key
Find pointer to a nod with key or nil 
Procedure Tree-Search(x,k) 
if  k  = key[x], then return x
if  k  < key[x] 
then return Tree-Search(left[x]) 
else return Tree-Search(right[x])
Iterative Tree-Search(x,k) 
while k  ? key[x] do
if k  < key[x] then x ? left[x]
else x ? right[x]
return x
7
5
6 3
6 2
8
9
4
Min-Max, Successor-Predecessor
• MIN: go to the left  x ? left[x]
• MAX: go to the right x ? right[x]
• Procedure Tree-Successor(x)
– if right[x] ? nil then return MIN(right[x])
– y = p[x]
– while y ? nil and x = right[y]
• x ? y
• y ? p[y]
– return y
7
5
6 3
6 2
8
9
4
Page 5


Binary Search Trees (13.1/12.1)
• Support Search, Minimum, Maximum, 
Predecessor, Successor, Insert, Delete
• In addition to key each node has 
– left = left child, right = right child, p = parent
• Binary search tree property:
– all keys in the left   subtree of x = key[x] 
– all keys in the right subtree of x = key[x]
• Resembles quicksort
In-Order-Tree Walk
• Procedure In-Order-Tree(x) (O(n)) 
– In-Order-Tree(left[x])
– print key[x]
– In-Order-Tree(right[x])
7
5
6 3
6 2
8
9
4
Searching (13.2/12.2)
Searching (O(h)):
Given pointer to the root and key
Find pointer to a nod with key or nil 
Procedure Tree-Search(x,k) 
if  k  = key[x], then return x
if  k  < key[x] 
then return Tree-Search(left[x]) 
else return Tree-Search(right[x])
Iterative Tree-Search(x,k) 
while k  ? key[x] do
if k  < key[x] then x ? left[x]
else x ? right[x]
return x
7
5
6 3
6 2
8
9
4
Min-Max, Successor-Predecessor
• MIN: go to the left  x ? left[x]
• MAX: go to the right x ? right[x]
• Procedure Tree-Successor(x)
– if right[x] ? nil then return MIN(right[x])
– y = p[x]
– while y ? nil and x = right[y]
• x ? y
• y ? p[y]
– return y
7
5
6 3
6 2
8
9
4
Insertion (13.3/12.3)
7
5
6 3
6 2
8
9
4
O(h) operation
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!