SEHH2239

Data Structures

Lecture 9
Tree II
 Learning Objectives:

To describe the Binary Search Trees (BST)

To implement BST by using a linked chain
To use BST for searching and sorting
To analysis BST and realize the need of
balanced BST
To operate the AVL Tree

3
Binary Search Tree

4
 Key-value pair and Search Tree

Key-value pair (KVP) is a set of two data items:

Key, which is a unique identifier for some item of data, and
Value, which is either the data that is identified or a
pointer to the location of that data
Examples
(0, Apple), (1, Orange), (2, Pineapple),….
(002, “Chan Tia”), (004, “U Pei Yi”), (007, “Lee Chi Gi”)….
(“atmosphere”, “環境” ), (“believe”, “相信”) (“mood”, “ 心境，
心情，情緒；精神狀態”), (“process”, “過程；步驟”) ….

A Search Tree is a tree data structures that can be

used to perform searching from a (key, value) pair.

5
 Definition Of Binary Search Tree

• A binary tree.
• Each node has a (key, value) pair.
• Nodes are insert to the tree according to the key.
• For every node x, all keys in the left subtree of x
are smaller than the key in x.
• For every node x, all keys in the right subtree of
x are greater than the key in x.
• No duplicate nodes.
 Binary Search Trees
Key property
Key at node
Smaller values in left subtree
Larger values in right subtree
Example
X>Y
X
X<Z

Y Z

https://www.youtube.com/watch?v=mtvbVLK5xDQ
(00:00 – 02:00) 7
 Binary Search Trees
Examples
5
10 10
2 45
5 30 5 45
30
2 25 45 2 25 30
10

25

Binary Non-binary
search trees search tree
8
 Example Binary Search Tree
20

10 40

6 15 30

2 8 25

Insert 20, 10, 6, 2, 8, 15, 40, 30, 25

Only keys are shown.

 Inorder traversal of BST
Print out all the keys in sorted order

Inorder: 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20

10
 Searching BST
If we are searching for 15, then we are done.
If we are searching for a key < 15, then we
should search in the left subtree.
If we are searching for a key > 15, then we
should search in the right subtree.

11
12
 Key operations of BST
• get(k)
– get the value v for a given key k
• put(k, v)
– add a new (k, v) to a BST
• remove(k)
– delete a node with key k from BST

13
 The Operation get()
20

10 40

6 15 30

2 8 25

14
class Node:
The Operation get()
def __init__(self, key, data): left key, data right
self.left = None
self.right = None
self.key = key
self.data = data

def get(self, key):

p = self

while p is not None: 20

if key < p.key: <
p = p.left 10 40

elif key > p.key: <

6 15 30
p = p.right >
else: 2 8 25
Key = 8
return p.data =

#no matching key

return None
15
 The Operation put()
20

10 40

6 15 30

2 8 25 35

Put a pair whose key is 35.

16
 The Operation put()
20

10 40

6 15 30

2 8 25 35

Put a pair whose key is 7.

17
 The Operation put()
20

10 40

6 15 30

18 25 35
2 8

Put a pair whose key is 18.

18
 The Operation put()
20

10 40

6 15 30

18 25 35
2 8

19
 The Operation put()
def put(self, key, data):
# Compare the new value with the parent node
if self.key:
if key < self.key:
if self.left is None:
self.left = Node(key, data)
else:
self.left.put(key, data)
elif key > self.key:
if self.right is None:
self.right = Node(key, data)
else:
self.right.put(key, data)
else:
self.key = key
self.data = data

20
 Exercise

• For each of the following key sequences

determine the binary search tree obtained
when the keys are inserted one-by-one in
the order given into an initially empty tree:
A. 1, 2, 3, 4, 5, 6, 7.
B. 4, 2, 1, 3, 6, 5, 7.
C. 1, 6, 7, 2, 4, 3, 5.

21
 The Operation remove()

Three cases:
▪ Element is in a leaf.
▪ Element is in a degree 1 node.
▪ Element is in a degree 2 node.

22
 Remove From A Leaf
20

10 40

6 15 30

18 25 35
2 8

Remove a leaf element. key = 7

23
 Remove From A Leaf (contd.)
20

10 40

6 15 30

18 25 35
2 8

Remove a leaf element. key = 35

24
 Remove From A Degree 1 Node
20

10 40

6 15 30

18 25 35
2 8

Remove from a degree 1 node. key = 40

25
Remove From A Degree 1 Node (contd.)
20

10 40

6 15 30

18 25 35
2 8

Remove from a degree 1 node. key = 15

26
 Remove From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Remove from a degree 2 node. key = 10

27
 Remove From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

7
Replace with predecessor (largest key in left subtree of the deleted
node) or successor (smallest in right subtree of the deleted node).
28
 Remove From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Replace with predecessor (largest key in left

subtree of the deleted node) 29
 Remove From A Degree 2 Node
20

8 40

6 15 30

18 25 35
2 8

Largest key must be in a leaf or degree 1 node.

30
Another Remove From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Remove from a degree 2 node. key = 20

31
 Remove From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Replace with predecessor (largest key in

left subtree of the deleted node) 32
 Remove From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Replace with predecessor (largest key in

left subtree of the deleted node) 33
 Remove From A Degree 2 Node
18

10 40

6 15 30

18 25 35
2 8

Replace with predecessor (largest key in

left subtree of the deleted node) 34
 Remove From A Degree 2 Node
18

10 40

6 15 30

2 8 25 35

7
Remove from a degree 2 node. key = 10
Replace with successor (smallest in right subtree of the deleted node).
35
 Remove From A Degree 2 Node
18

10 40

6 15 30

2 8 25 35

Replace successor (smallest in right subtree of

the deleted node). 36
 Remove From A Degree 2 Node
18

15 40

6 15 30

2 8 25 35

Replace successor (smallest in right subtree of

the deleted node). 37
 Find smallest

# To find the inorder successor which

# is the smallest node in the subtree

def findsuccessor(self, node):

current_node = node
while current_node.left != None:
current_node = current_node.left
return current_node

38
 Remove()
def remove(self, root, key):
# Base Case
if root is None:
return root

# If the key to be deleted is smaller than

# the root's key, then it lies in left subtree
if key < root.key:
root.left = self.remove(root.left, key)

# If the key to be delete is greater than

# the root's key, then it lies in right subtree
elif key > root.key:
root.right = self.remove(root.right, key)

39
 Remove()

# If key is same as root's key, then this is the node

# to be deleted
else:

# Node with only one child or no child

if root.left is None:
return root.right Call: root = remove(root, key)
root = root.right

elif root.right is None:

return root.left root = root.left
 Remove()

# Node with two children:

# Get the inorder successor
# (smallest in the right subtree)
temp = self.findsuccessor(root.right)

# Copy the inorder successor's content to this node

root.key = temp.key
root.data = temp.data

# Delete the inorder successor

root.right = self.remove(root.right, root.key)

return root

41
4
2

Balanced BST / AVL Tree

42
 Balanced Binary Search Trees

• AVL (Adel’son-Vel’skii and Landis) trees

• Hopefully, height is O(log2 n), where n is
the number of elements in the tree
• Ideally, get, put, and remove take O(log2 n)
time

43
 AVL Tree
• binary tree
• for every node x, define its balance factor
balance factor of x = height of right subtree of x
- height of left subtree of x
• balance factor of every node x is -1, 0, or 1

Note: In some texts (e.g. the textbook by Sahni), the balance factor is computed
as follows:

balance factor of x = height of left subtree of x - height of right subtree of x

This note uses the above-mentioned implementation.

44
 Balance Factors
1

-1 -1

0 -1 1
0

0
0 0 1 0

This is an AVL tree.

45
 AVL Search Tree
1
10

-1 -1
7 40
0 -1 1
0 45
3 8 30
0
0 0 1 0 60
35
1 5 20
0
25

46
 put(9)
1
10

0 -1 -1
7 40
0 -1 1
0 1 45
3 8 30
0
0 0 0 1 0 60
35
1 5 9 20
0
25

47
 put(29)
1
10

-1 -1
7 40
0 -1 1
0 45
3 8 30
0
0 0 2 1 35
0 60
1 5 20
0 1
RR imbalance => new node is in 25
right subtree of right subtree of 0

blue node (node with bf = 2) 29

48
 put(29)
1
10

-1 -1
7 40
0 -1 1
0 45
3 8 30
0
0 0 0 0 60
35
1 5 25
0 0
20 29

RR rotation. 49
 AVL Rotations

• RR: One Left-rotate

2
0
20 Left Rotate
25
1 0 0
25 20 29
0
29

50
 AVL Rotations

• LL: One Right-rotate

0
-2
20 Right Rotate 12
0 0
-1 6 20
12

6 0

51
 AVL Rotations

• RL: Right-rotate + Left-rotate

2 2 0
20 20 23
Right Rotate 0
-1 Left Rotate 0
25 1 23
20 25
0
23 0 25

52
 AVL Rotations

• LR: Left-rotate + Right-rotate

-2 -2
0
20 20 18
Left Rotate Right Rotate 0
1 -1 0
16 18 16 20
0 0
18 16

https://www.youtube.com/watch?v=yAFLlCZFJy0
53
 Exercise

balance factor of node i = height of left subtree of node i -

height of right subtree of node i

Insertion of 68, 7, 23 into an AVL tree

Further insert the sequence of integer keys 45, 3, 12, 52

into the AVL tree

54
 Basic AVL Rotations
(in presence of subtrees underneath)

z z
Rotate at x right Rotate at y
y x
left
x y
C A

A B B C

The relation x < B < y is maintained

56
Exercise

57
RL imbalance

58
LR imbalance

Left rotation

26 15
Right rotation

15 06 26

06

59
 Summary

• Binary Search Tree

• Operations
• AVL

60