Lecture 7:
Trees: Binary Search Tree
& AVL Tree
Dr. Alaa Alslaity
Trent University-GTA
These slides are prepared by Alaa Alslaity based on the lecture notes of Brian Srivastava-Trent University.
Binary Tree
Every node has at most 2 children
Binary Search Trees
Properties of a BST
All items in the left subtree are less than the root
All items in the right subtree are greater than or equal to the root
Each subtree is itself a BST
≥
3
Valid Binary Search Trees
Properties of a BST
All items in the left subtree are less than
the root
All items in the right subtree are greater
than or equal to the root
4
Invalid Binary Search Trees
5
What about this??
Is this a Binary Tree??
Is it a Binary Search Tree (BST)?
Binary Search – Log(n) search
The upside of the BST is that
the tree is kept in sorted order
searching in a BST is fast; that’s the whole idea
Disadvantage?
You need to insert in the right place, and,
that can create a hugely unbalanced tree,
so searching can be O(n) in the worst case
Binary Tree Using Nodes
Public class node{
Public node parent // maybe
Public node leftchild
Public node rightchild
}
Public class binary_tree{
Public node root
}
BST Traversals
Can use any of our traversal algorithms
Preorder, in-order, postorder
In-order is the most useful
Provides an ordered list of the elements in the tree
10
BST Traversals
Preorder traversal = 23, 18, 12, 20, 44, 35, 52
Inorder traversal = 12, 18, 20, 23, 35, 44, 52
Postorder traversal = 12, 20, 18, 35, 52, 44, 23 11
BST – Find Smallest Node
Smallest node is the leftmost leaf
Can use a recursive algorithm
algorithm findSmallestBST (val root <pointer>)
if (root-> left = null)
return root
else
return findSmallestBST(root->left)
12
13
BST – Find Largest Node
Largest node is rightmost leaf
Similar to finding smallest node except that we go right
algorithm findLargestBST (val root <pointer>)
if (root-> right = null)
return root
else
return findLargestBST(root->right)
14
BST Search
Compare target value to root
If target < root
take left subtree
If target > root
take right subtree
If target = root
we’ve found target, return it or its index
We continue with the above until we’ve
either found target or have nowhere else to
go
15
BST Search
algorithm searchBST (val root <pointer>, val argument <key>)
Return: node address if value found, null otherwise
if (root = null)
return null
if (argument < root -> key)
return searchtBST (root->left, argument)
elseif (argument > root -> key)
return searchtBST (root->right, argument)
else return root
16
BST Search
17
BST – Insert Node
Follow branches to an empty node and insert value
All BST inserts take place at a leaf or leaf-like node
Have at least one null branch
18
BST – Insert Node
Examples
19
BST – Insert Node
Iterative Insert
algorithm insertBST (ref root <pointer>, val new)
if (root = null)
root = new
else
pwalk = root
loop (pwalk != null)
parent = pwalk
if (new->key < pwalk)
pwalk = pwalk->left
else
pwalk = pwalk->right
//End of loop
if (new->key < parent->key)
parent-> left = new
else
parent-> right = new
20
return
BST – Insert Node
Recursive Insert
algorithm addBST (ref root <pointer>, val new <pointer>)
if (root = null)
root = new
else
if (new->key < root->key)
addBST(root->left, new)
else
addBST(root->right, new)
21
BST – Insert Node
Example
22
BST – Insert Node
Example
23
Delete Node - BST
Four possible cases
A. Node to be deleted has no children
Set node’s parent to null
Recycle memory
24
Delete Node - BST
Four possible cases
B. Node to be deleted has only a right subtree
Attach right subtree to delete node’s parent
Recycle memory
25
Delete Node - BST
Four possible cases
C. Node to be deleted has only a left subtree
Attach the left subtree to deleted node’s parent
26
Delete Node - BST
Four possible cases
D. Node to be deleted has two subtrees
Find data to take place of the deleted node
Two choices
Find the largest node in the left subtree
Find the smallest node in the right subtree
27
algorithm deleteBST (ref root <pointer>, val dltKey <key>)
Delete Node – BST if (root = null)
Algorithm return false
if (dltKey < root->data.key)
return deleteBST (root->left, dltKey)
elseif (dltKey > root->data.key)
return deleteBST (root->right, dltKey)
else //node is found
if (root-> left = null AND root-> right = null) //If leaf
recycle (root)
return true
else if (root-> left = null) //If no left
dltPtr = root
root = root->right
recycle (dltPtr)
return true
else if (root-> right = null) //If no right
dltPtr = root
root = root->left
recycle (dltPtr)
return true
else // node is not a leaf, find largest node on left subtree
dltPtr = root->left
loop (dltPtr ->right != null)
dltPtr = dltPtr->right
28
root->data = dltPtr->data
return true
Balanced Binary
Trees
Problem with a BST is that it is not
necessarily balanced
Inefficient searches
Worst case (O(n))
for an unbalanced tree with 1,000
nodes is 1,000
Worst case for a balanced (or nearly
balanced) tree is (Ologn))
for an unbalanced tree with 1,000
nodes is 10
Making a Tree Self Balancing
Start with some core rule for that type of tree, such as
The maximum difference in height between two subtrees is 2
AVL Tree
At most 2 children at the root, 3 nodes in internal nodes and 4 in leaves
2-3-4 Tree
Only insert to the right (meaning rotate so things can be inserted to the right)
AA Tree
Or several other types of self balancing trees
Then figure out how to enforce them
AVL Trees
AVL Trees
Problem with a BST is that
it is not necessarily balanced
Inefficient searches
So, use an AVL tree
Adelson Velsky and Landis
Just a balanced BST
Balance Factor:
| HL – HR | <= 1
AVL trees can be left-high LH (+1), even-high EH (0), or right-high RH (-1)
36
Examples
37
Examples
Not an AVL
38
Source: Insertion in an AVL Tree - GeeksforGeeks
Examples
39
AVL Operations
Traversal and search are the same as in a BST
Insert
Left Balance
Right Balance
Rotate Left
Rotate Right
Delete
Delete Left Balance
Delete Right Balance
40
AVL Node Structure RH
Same as in BST, only we include the balance factor
Public class node{
Public node leftchild
HL – HR = -2
Public node rightchild
Private short balance LH
…
}
Public class AVL{
Public node root
…
41
}
HL – HR = 2
Balancing AVL Trees
Whenever a node is inserted or deleted, the tree may become unbalanced
Four Insertion cases
Left of left
Adding a node to the left of a LH tree
Right of right
Adding a node to the right of a RH tree
Right of left
Adding a node to the right of a LH tree
Left of right
Adding a node to the left of a RH tree 42
43
44
Balancing AVL Trees
re-balance tree
Need to rotate nodes
Two Types of rotations:
Rotate Left
Rotate Right
45
Rotation
Rotate right
Y X
X T3 Y
T1
T1 T2 T2 T3
Rotate Left
Sub-trees
Rotate Algorithms
algorithm rotateRight (ref root)
tempPtr = root->left
root->left = tempPtr->right
tempPtr->right = root
return tempPtr
47
Balancing AVL-Rotation
Left of Left
Balance the tree by rotating the out-
of-balance tree to the right
48
Balancing AVL-Rotation
Right of Right
Balance the tree by rotating the
unbalanced tree to the left
49
Balancing AVL-Rotation
Right of Left
Need to rotate two nodes
One to the left and the other
to the right
50
Balancing AVL-Rotation
Left of Right
Similar to Right of Left only
we first rotate to the right and
then to the left
51
AVL Insert
Start as in BST
Find the location to insert node
Then, as we back out of tree, we check the balance of each node
If out of balance, re-balance it and then continue up tree
Not all insertions cause imbalance
Automatic balancing
52
Example
Suppose that we need to insert 15. (right of left)
Three becomes unbalanced at 18
Rotate left (at 12)
Rotate right (at 18)
Then, suppose that we need to insert 55. (right of
right)
Three becomes unbalanced at 44
Rotate left (at 44)
