Courses

# 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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!