Chapter 5 – Part 2: Search Trees
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Chapter 5 – Part 2: Search Trees as PDF for free.
More details
- Words: 2,521
- Pages: 50
Chapter 5 – Part 2: Search Trees
• Binary search trees • AVL trees
1
Binary Search Trees • All items in the left subtree < the root. • All items in the right subtree >= the root. • Each subtree is itself a binary search tree.
2
Binary Search Tree Traversals preorder 23 18 12 20 44 35 52
23 18 12
postorder
44 20
35
52
12 20 18 35 52 44 23
inorder 12 18 20 23 35 44 52 3
Find Smallest Node Algorithm
findSmallestBST (val root <pointer>)
Finds the smallest node in a BST Pre
root is a pointer to a non-empty BST 23
Return address of smallest node 1 if (root −> left = null) 1 2
return (root)
return findSmallestBST (root −> left) 12
End
18
44 20
35
52
findSmallestBST
4
Find Largest Node Algorithm
findLargestBST (val root <pointer>)
Finds the largest node in a BST Pre
root is a pointer to a non-empty BST 23
Return address of largest node 1 if (root −> right = null) 1 2
return (root)
return findLargestBST (root −> right)12
End
18
44 20
35
52
findLargestBST
5
BST Search Algorithm searchBST (val root <pointer>, val arg) Searches a binary search tree for a given value Pre root is a pointer to a non-empty BST arg is the key value requested Return the node address if the value is found; null otherwise 1 if (root = null) 1 return null 2 else if (arg = root −> key) 23 1 return root 3 else if (arg < root −> key) 18 44 1 searchBST (root −> left, arg) 4 else if (arg > root −> key) 1 searchBST (root −> right, arg) 12 20 35 52 5 else 1 return null End searchBST
6
BST Insertion Taking place at a node having a null branch
23 18
12
44 20
35
52
19 23
23
18 12
20 19
22
44 35
52
18 12
44 20
19
35 22
52
7
Iterative BST Insertion Algorithm Algorithm
insertBST (ref root <pointer>, val new <pointer>)
Inserts a new node into BST using iteration Pre
root is address of the root new is address of the new node
Post new node inserted into the tree
8
Iterative BST Insertion Algorithm
1 if (root = null) 1 root = new 18 2 else 1 pWalk = root 12 2 loop (pWalk not null) 1 parent = pWalk 19 2 if (new −> key < pWalk −> key) 1 pWalk = pWalk −> left 3 else 1 pWalk = pWalk −> right Location found for the new node 3 if (new −> key < parent −> key) 1 parent −> left = new 4 else 1 parent −> right = new 3 return End
insertBST
23 44 20
35
52
9
Recursive BST Insertion Algorithm Algorithm
addBST (ref root <pointer>, val new <pointer>)
Inserts a new node into BST using recursion Pre
root is address of the root new is address of the new node
Post new node inserted into the tree
10
Recursive BST Insertion Algorithm 23
1 if (root = null) 1 root = new 2 else 1 if (new −> key < root −> key) 1 addBST (root −> left, new) 2 else 1 addBST (root −> right, new) 3 return End addBST
18 12
44 20
19
35
52
22
11
BST Deletion • Leaf node: set the deleted node's parent link to null. • Node having only right subtree: attach the right subtree to the deleted node's parent. • Node having only left subtree: attach the left subtree to the deleted node's parent. 12
BST Deletion Node having both subtrees 23
23
18 12
20 19
?
44 35 22
52
12
44 20
19
35
52
22
13
BST Deletion Node having both subtrees 23
23
18 12
44 20
19
35 22
12 52
12
44 20
19
35
52
22
Using largest node in the left subtree 14
BST Deletion Node having both subtrees 23
23
18 12
44 20
19
35 22
19 52
12
44 20
19
35
52
22
Using smallest node in the right subtree 15
BST Deletion Algorithm Algorithm deleteBST (ref root <pointer>, val dltKey) Deletes a node from a BST Pre root is a pointer to a non-empty BST dltKey is the key of the node to be deleted Post node deleted & memory recycled if dltKey not found, root unchanged Return true if node deleted; false otherwise 1 if (root = null) 1 return false 2 if (dltKey < root −> data.key) 1 deleteBST (root −> left, dltKey) 3 else if (dltKey > root −> data.key) 1 deleteBST (root −> right, dltKey) 4 else Deleted node found 16
BST Deletion Algorithm 4
else Deleted node found 1 if (root −> left = null) 1 dltPtr = root 2 root = root −> right 3 recycle (dltPtr) 4 return true 2 else if (root −> right = null) 1 dltPtr = root 2 root = root −> left 3 recycle (dltPtr) 4 return true 3 else 1 dltPtr = root −> left 2 loop (dltPtr −> right not null) 1 dltPtr = dltPtr −> right 3 root −> data = dltPtr −> data 4 return deleteBST (root −> left, dltPtr −> data.key) End deleteBST
17
AVL Trees • The heights of the left subtree and the right subtree differ by no more than one. • The left and right subtrees are AVL trees themselves. (G.M. Adelson-Velskii and E.M. Landis, 1962 )
18
AVL Trees 23 LH
8 E H
18
44
LH
E H
12
20
35
E H
E H
E H
14
52 E H
E H
19
Getting Unbalanced 18
insert 4
LH
8 E H
18 LH
12
20
12
20
E H
E H
LH
E H
14 E H
4
8
14
LH
E H
E H
Left of Left 20
Getting Unbalanced 14 12 E H
14
insert 44
R H
20
12
18
E H
E H
E H
23 E H
R H
20
18
R H
E H
23 R H
44 E H
Right of Right 21
Getting Unbalanced 18
insert 13
LH
8 E H
18 LH
12
20
12
20
E H
E H
R H
E H
14
8
E H
E H
14 LH
13 E H
Right of Left 22
Getting Unbalanced 14 12 E H
14
insert 19
R H
20
12
18
E H
E H
E H
44 E H
R H
20 LH
18
44
R H
E H
19 E H
Left of Right 23
Balancing Trees 20 LH
20
insert 12
18 E H
18
18
rotate right 12 E H
12
E H
20 E H
Left of Left 24
Balancing Trees 18
insert 4
LH
8 E H
12
20
E H
E H
14 E H
rotate right
18 12
12 E H
18
4
14
E H
E H
E H
20
8 LH
8
14
4
20 E H
Left of Left 25
Balancing Trees
12 R H
insert 20 18 E H
12
18
rotate left 18
12 20
E H
E H
20 E H
Right of Right 26
Balancing Trees 14 12 E H
R H
20
18
E H
E H
insert 44 23
rotate left
14 12
20
20 18
E H
14 23
12 44
E H
E H
E H
23
18
R H
44
E H
E H
Right of Right 27
Balancing Trees 12 LH 4 E H
8
12
rotate left
8
rotate right
8
4 E H
4
E H
12 E H
Right of Left 28
Balancing Trees rotate left
18 LH
4 E H
12
20
E H
E H
14 E H
16
rotate right
18 14
14 E H
18
4
16
E H
E H
E H
20
12 LH
12
16
4
20 E H
Right of Left 29
Balancing Trees 12 R H
44
rotate right
12 18
12
LH 18
18
rotate left
44
E H
E H
44 E H
Left of Right 30
Balancing Trees rotate right
18 12 E H
20
R H
44
rotate left
18 12
23
23
18
LH 23
52
LH
E H
20
12
44 52
E H
E H
E H
44
20
R H
52
E H
E H
Left of Right 31
AVL Node Structure Node key
18
data leftSubTree <pointer> rightSubTree <pointer> bal End Node
12 E H
20
R H
44 LH
23
52
LH
E H
E H
32
AVL Insertion Algorithm Algorithm
insertAVL (ref root <pointer>, val newPtr <pointer>, ref taller)
Inserts a new node into an AVL tree using recursion Pre
root is address of the root newPtr is address of the new node
Post taller = true indicating the tree's height has increased; false ortherwise
33
AVL Insertion Algorithm 1
2
if (root = null) 1 taller = true 2 root = newPtr else 1 if (newPtr −> key < root −> key) 1 insertAVL (root −> left, newPtr, taller) 2 if (taller) 1 if (root left-high) 1 leftBalance (root, taller) 2 else if (root right-high) 1 taller = false 2 root −> bal = EH 3 else 1 root −> bal = LH 2 else if (newPtr −> key > root −> key) 34
AVL Insertion Algorithm else if (newPtr −> key > root −> key) 1 insertAVL (root −> right, newPtr, taller) 2 if (taller) 1 if (root right-high) 1 rightBalance (root, taller) 2 else if (root left-high) 1 taller = false 2 root −> bal = EH 3 else 1 root −> bal = RH 3 else 1 error ("Dupe data") 2 recycle (newPtr) 3 taller = false 3 return End insertAVL 2
35
AVL Left Balance Algorithm Algorithm
leftBalance (ref root <pointer>, ref taller <pointer>)
Balances an AVL tree that is left heavy Pre
root is address of the root taller = true
Post root has been updated (if necessary) taller has been updated
36
AVL Left Balance Algorithm 1 2
leftTree = root −> left if (leftTree left-high) Case 1: Left of left. Single rotation required. 1 adjust balance factors 2 rotateRight (root) 3 taller = false
4 E H
18
12
LH
E H
18
4
14
E H
E H
E H
12
20
8
LH
E H
LH
8
14
LH
E H
20 E H 37
AVL Left Balance Algorithm 3
else Case 2: Right of left. Double rotation required. 1 rightTree = leftTree −> right 2 adjust balance factors 3 rotateLeft (leftTree) 4 rotateRight (root) 5 taller = false 4 return End leftBalance 18
18
14
LH
4 E H
12
20
R H
E H
14 E H
16 E H
14
E H
18
4
16
E H
E H
E H
20
12 LH
12 4
16
20 E H
38
Rotate Algorithms Algorithm
rotateRight (ref root <pointer>)
Exchanges pointers to rotate the tree right Pre
root is address of the root
Post Node rotated and root updated
39
Rotate Algorithms 1 tempPtr = root −> left 2 root −> left = tempPtr −> right 3 tempPtr −> right = root 4 root = tempPtr 5 return End rotateRight
r oot tempPtr
18 14
20
12
16
4
r oot tempPtr
18 14
12 4
r oot tempPtr 20
16
14 12
4
r oot 18
16
14 12
20
4
18 16
20 40
Rotate Algorithms Algorithm rotateLeft (ref root <pointer>) Exchanges pointers to rotate the tree left Pre
root is address of the root
Post Node rotated and root updated 1
tempPtr = root −> right
2 root −> right = tempPtr −> left 3 tempPtr −> left = root 4 root = tempPtr 5 return End
rotateLeft 41
AVL Deletion 12 9 E H
delete 9
R H
18
15
E H
E H
rotate left
12 18
20
15
20
E H
18 LH 12
20
E H
E H
15 E H
Right subtree is evenbalanced 42
AVL Deletion 12 9 E H
R H
delete 9 18 R H
rotate left
12 18
20
18 12
20
E H
E H
20 E H
E H
Right subtree is not evenbalanced 43
AVL Deletion Algorithm Algorithm
deleteAVL (ref root <pointer>, val deleteKey, ref shorter )
Deletes a node from an AVL tree Pre
root is address of the root deleteKey is the key of the node to be deleted
Post
node deleted if found shorter = true if the tree is shorter
Return
success true if node deleted; false otherwise
44
AVL Deletion Algorithm 1
2
3
4
if (root null) 1 shorter = false 2 return success = false if (deleteKey < root −> key) 1 success = deleteAVL (root −> left, deleteKey, shorter) 2 if (shorter) 1 deleteRightBalance (root, shorter) 3 return success else if (deleteKey > root −> key) 1 success = deleteAVL (root −> right, deleteKey, shorter) 2 if (shorter) 1 deleteLeftBalance (root, shorter) 3 return success else Delete node found - Test for leaf node 45
AVL Deletion Algorithm 4
else Delete node found - Test for node having a null subtree 1 deleteNode = root 2 if (no left subtree) 1 root = root −> right 2 shorter = true 3 recycle (deleteNode) 4 return success = true 3 else if (no right subtree) 1 root = root −> left 2 shorter = true 3 recycle (deleteNode) 4 return success = true 4 else Delete node has two subtrees 46
AVL Deletion Algorithm 4
else Delete node has two subtrees 1 exchPtr = root −> left 2 loop (exchPtr −> right not null) 1 exchPtr = exchPtr −> right 3 root −> data = exchPtr −> data 4 deleteAVL (root −> left, exchPtr −> data.key, shorter) 5 if (shorter) 1 deleteRightBalance (root, shorter) 6 return success = true 5 return End deleteAVL
47
Delete Right Balance Algorithm Algorithm deleteRightBalance (ref root <pointer>, ref shorter <pointer>) Adjusts the balance factors, and balance the tree by rotating left if necessary Pre tree is shorter Post balance factors updated and balance restored root updated shorter updated 1 if (root left-high) 1 root −> bal = EH 2 else if (root even-high) 1 root −> bal = RH 2 shorter = false 3 else Tree was right high already. Rotate left
48
Delete Right Balance Algorithm 3
else Tree was right high already. Rotate left 1 rightTree = root −> right 2 if (rightTree left-high) Double rotation required 1 leftTree = rightTree −> left 2 leftTree −> bal = EH 3 rotateRight (rightTree) 4 rotateLeft (root) 3 else Single rotation required
49
Delete Right Balance Algorithm 1
2
Single rotation required if (rightTree even-high) 1 root −> bal = RH 2 rightTree −> bal = LH 3 shorter = false else 1 root −> bal = EH 2 rightTree −> bal = EH rotateLeft (root)
3 4 return End deleteRightBalance
50
• Binary search trees • AVL trees
1
Binary Search Trees • All items in the left subtree < the root. • All items in the right subtree >= the root. • Each subtree is itself a binary search tree.
2
Binary Search Tree Traversals preorder 23 18 12 20 44 35 52
23 18 12
postorder
44 20
35
52
12 20 18 35 52 44 23
inorder 12 18 20 23 35 44 52 3
Find Smallest Node Algorithm
findSmallestBST (val root <pointer>)
Finds the smallest node in a BST Pre
root is a pointer to a non-empty BST 23
Return address of smallest node 1 if (root −> left = null) 1 2
return (root)
return findSmallestBST (root −> left) 12
End
18
44 20
35
52
findSmallestBST
4
Find Largest Node Algorithm
findLargestBST (val root <pointer>)
Finds the largest node in a BST Pre
root is a pointer to a non-empty BST 23
Return address of largest node 1 if (root −> right = null) 1 2
return (root)
return findLargestBST (root −> right)12
End
18
44 20
35
52
findLargestBST
5
BST Search Algorithm searchBST (val root <pointer>, val arg
6
BST Insertion Taking place at a node having a null branch
23 18
12
44 20
35
52
19 23
23
18 12
20 19
22
44 35
52
18 12
44 20
19
35 22
52
7
Iterative BST Insertion Algorithm Algorithm
insertBST (ref root <pointer>, val new <pointer>)
Inserts a new node into BST using iteration Pre
root is address of the root new is address of the new node
Post new node inserted into the tree
8
Iterative BST Insertion Algorithm
1 if (root = null) 1 root = new 18 2 else 1 pWalk = root 12 2 loop (pWalk not null) 1 parent = pWalk 19 2 if (new −> key < pWalk −> key) 1 pWalk = pWalk −> left 3 else 1 pWalk = pWalk −> right Location found for the new node 3 if (new −> key < parent −> key) 1 parent −> left = new 4 else 1 parent −> right = new 3 return End
insertBST
23 44 20
35
52
9
Recursive BST Insertion Algorithm Algorithm
addBST (ref root <pointer>, val new <pointer>)
Inserts a new node into BST using recursion Pre
root is address of the root new is address of the new node
Post new node inserted into the tree
10
Recursive BST Insertion Algorithm 23
1 if (root = null) 1 root = new 2 else 1 if (new −> key < root −> key) 1 addBST (root −> left, new) 2 else 1 addBST (root −> right, new) 3 return End addBST
18 12
44 20
19
35
52
22
11
BST Deletion • Leaf node: set the deleted node's parent link to null. • Node having only right subtree: attach the right subtree to the deleted node's parent. • Node having only left subtree: attach the left subtree to the deleted node's parent. 12
BST Deletion Node having both subtrees 23
23
18 12
20 19
?
44 35 22
52
12
44 20
19
35
52
22
13
BST Deletion Node having both subtrees 23
23
18 12
44 20
19
35 22
12 52
12
44 20
19
35
52
22
Using largest node in the left subtree 14
BST Deletion Node having both subtrees 23
23
18 12
44 20
19
35 22
19 52
12
44 20
19
35
52
22
Using smallest node in the right subtree 15
BST Deletion Algorithm Algorithm deleteBST (ref root <pointer>, val dltKey
BST Deletion Algorithm 4
else Deleted node found 1 if (root −> left = null) 1 dltPtr = root 2 root = root −> right 3 recycle (dltPtr) 4 return true 2 else if (root −> right = null) 1 dltPtr = root 2 root = root −> left 3 recycle (dltPtr) 4 return true 3 else 1 dltPtr = root −> left 2 loop (dltPtr −> right not null) 1 dltPtr = dltPtr −> right 3 root −> data = dltPtr −> data 4 return deleteBST (root −> left, dltPtr −> data.key) End deleteBST
17
AVL Trees • The heights of the left subtree and the right subtree differ by no more than one. • The left and right subtrees are AVL trees themselves. (G.M. Adelson-Velskii and E.M. Landis, 1962 )
18
AVL Trees 23 LH
8 E H
18
44
LH
E H
12
20
35
E H
E H
E H
14
52 E H
E H
19
Getting Unbalanced 18
insert 4
LH
8 E H
18 LH
12
20
12
20
E H
E H
LH
E H
14 E H
4
8
14
LH
E H
E H
Left of Left 20
Getting Unbalanced 14 12 E H
14
insert 44
R H
20
12
18
E H
E H
E H
23 E H
R H
20
18
R H
E H
23 R H
44 E H
Right of Right 21
Getting Unbalanced 18
insert 13
LH
8 E H
18 LH
12
20
12
20
E H
E H
R H
E H
14
8
E H
E H
14 LH
13 E H
Right of Left 22
Getting Unbalanced 14 12 E H
14
insert 19
R H
20
12
18
E H
E H
E H
44 E H
R H
20 LH
18
44
R H
E H
19 E H
Left of Right 23
Balancing Trees 20 LH
20
insert 12
18 E H
18
18
rotate right 12 E H
12
E H
20 E H
Left of Left 24
Balancing Trees 18
insert 4
LH
8 E H
12
20
E H
E H
14 E H
rotate right
18 12
12 E H
18
4
14
E H
E H
E H
20
8 LH
8
14
4
20 E H
Left of Left 25
Balancing Trees
12 R H
insert 20 18 E H
12
18
rotate left 18
12 20
E H
E H
20 E H
Right of Right 26
Balancing Trees 14 12 E H
R H
20
18
E H
E H
insert 44 23
rotate left
14 12
20
20 18
E H
14 23
12 44
E H
E H
E H
23
18
R H
44
E H
E H
Right of Right 27
Balancing Trees 12 LH 4 E H
8
12
rotate left
8
rotate right
8
4 E H
4
E H
12 E H
Right of Left 28
Balancing Trees rotate left
18 LH
4 E H
12
20
E H
E H
14 E H
16
rotate right
18 14
14 E H
18
4
16
E H
E H
E H
20
12 LH
12
16
4
20 E H
Right of Left 29
Balancing Trees 12 R H
44
rotate right
12 18
12
LH 18
18
rotate left
44
E H
E H
44 E H
Left of Right 30
Balancing Trees rotate right
18 12 E H
20
R H
44
rotate left
18 12
23
23
18
LH 23
52
LH
E H
20
12
44 52
E H
E H
E H
44
20
R H
52
E H
E H
Left of Right 31
AVL Node Structure Node key
18
data leftSubTree <pointer> rightSubTree <pointer> bal
12 E H
20
R H
44 LH
23
52
LH
E H
E H
32
AVL Insertion Algorithm Algorithm
insertAVL (ref root <pointer>, val newPtr <pointer>, ref taller
Inserts a new node into an AVL tree using recursion Pre
root is address of the root newPtr is address of the new node
Post taller = true indicating the tree's height has increased; false ortherwise
33
AVL Insertion Algorithm 1
2
if (root = null) 1 taller = true 2 root = newPtr else 1 if (newPtr −> key < root −> key) 1 insertAVL (root −> left, newPtr, taller) 2 if (taller) 1 if (root left-high) 1 leftBalance (root, taller) 2 else if (root right-high) 1 taller = false 2 root −> bal = EH 3 else 1 root −> bal = LH 2 else if (newPtr −> key > root −> key) 34
AVL Insertion Algorithm else if (newPtr −> key > root −> key) 1 insertAVL (root −> right, newPtr, taller) 2 if (taller) 1 if (root right-high) 1 rightBalance (root, taller) 2 else if (root left-high) 1 taller = false 2 root −> bal = EH 3 else 1 root −> bal = RH 3 else 1 error ("Dupe data") 2 recycle (newPtr) 3 taller = false 3 return End insertAVL 2
35
AVL Left Balance Algorithm Algorithm
leftBalance (ref root <pointer>, ref taller <pointer>)
Balances an AVL tree that is left heavy Pre
root is address of the root taller = true
Post root has been updated (if necessary) taller has been updated
36
AVL Left Balance Algorithm 1 2
leftTree = root −> left if (leftTree left-high) Case 1: Left of left. Single rotation required. 1 adjust balance factors 2 rotateRight (root) 3 taller = false
4 E H
18
12
LH
E H
18
4
14
E H
E H
E H
12
20
8
LH
E H
LH
8
14
LH
E H
20 E H 37
AVL Left Balance Algorithm 3
else Case 2: Right of left. Double rotation required. 1 rightTree = leftTree −> right 2 adjust balance factors 3 rotateLeft (leftTree) 4 rotateRight (root) 5 taller = false 4 return End leftBalance 18
18
14
LH
4 E H
12
20
R H
E H
14 E H
16 E H
14
E H
18
4
16
E H
E H
E H
20
12 LH
12 4
16
20 E H
38
Rotate Algorithms Algorithm
rotateRight (ref root <pointer>)
Exchanges pointers to rotate the tree right Pre
root is address of the root
Post Node rotated and root updated
39
Rotate Algorithms 1 tempPtr = root −> left 2 root −> left = tempPtr −> right 3 tempPtr −> right = root 4 root = tempPtr 5 return End rotateRight
r oot tempPtr
18 14
20
12
16
4
r oot tempPtr
18 14
12 4
r oot tempPtr 20
16
14 12
4
r oot 18
16
14 12
20
4
18 16
20 40
Rotate Algorithms Algorithm rotateLeft (ref root <pointer>) Exchanges pointers to rotate the tree left Pre
root is address of the root
Post Node rotated and root updated 1
tempPtr = root −> right
2 root −> right = tempPtr −> left 3 tempPtr −> left = root 4 root = tempPtr 5 return End
rotateLeft 41
AVL Deletion 12 9 E H
delete 9
R H
18
15
E H
E H
rotate left
12 18
20
15
20
E H
18 LH 12
20
E H
E H
15 E H
Right subtree is evenbalanced 42
AVL Deletion 12 9 E H
R H
delete 9 18 R H
rotate left
12 18
20
18 12
20
E H
E H
20 E H
E H
Right subtree is not evenbalanced 43
AVL Deletion Algorithm Algorithm
deleteAVL (ref root <pointer>, val deleteKey
Deletes a node from an AVL tree Pre
root is address of the root deleteKey is the key of the node to be deleted
Post
node deleted if found shorter = true if the tree is shorter
Return
success true if node deleted; false otherwise
44
AVL Deletion Algorithm 1
2
3
4
if (root null) 1 shorter = false 2 return success = false if (deleteKey < root −> key) 1 success = deleteAVL (root −> left, deleteKey, shorter) 2 if (shorter) 1 deleteRightBalance (root, shorter) 3 return success else if (deleteKey > root −> key) 1 success = deleteAVL (root −> right, deleteKey, shorter) 2 if (shorter) 1 deleteLeftBalance (root, shorter) 3 return success else Delete node found - Test for leaf node 45
AVL Deletion Algorithm 4
else Delete node found - Test for node having a null subtree 1 deleteNode = root 2 if (no left subtree) 1 root = root −> right 2 shorter = true 3 recycle (deleteNode) 4 return success = true 3 else if (no right subtree) 1 root = root −> left 2 shorter = true 3 recycle (deleteNode) 4 return success = true 4 else Delete node has two subtrees 46
AVL Deletion Algorithm 4
else Delete node has two subtrees 1 exchPtr = root −> left 2 loop (exchPtr −> right not null) 1 exchPtr = exchPtr −> right 3 root −> data = exchPtr −> data 4 deleteAVL (root −> left, exchPtr −> data.key, shorter) 5 if (shorter) 1 deleteRightBalance (root, shorter) 6 return success = true 5 return End deleteAVL
47
Delete Right Balance Algorithm Algorithm deleteRightBalance (ref root <pointer>, ref shorter <pointer>) Adjusts the balance factors, and balance the tree by rotating left if necessary Pre tree is shorter Post balance factors updated and balance restored root updated shorter updated 1 if (root left-high) 1 root −> bal = EH 2 else if (root even-high) 1 root −> bal = RH 2 shorter = false 3 else Tree was right high already. Rotate left
48
Delete Right Balance Algorithm 3
else Tree was right high already. Rotate left 1 rightTree = root −> right 2 if (rightTree left-high) Double rotation required 1 leftTree = rightTree −> left 2 leftTree −> bal = EH 3 rotateRight (rightTree) 4 rotateLeft (root) 3 else Single rotation required
49
Delete Right Balance Algorithm 1
2
Single rotation required if (rightTree even-high) 1 root −> bal = RH 2 rightTree −> bal = LH 3 shorter = false else 1 root −> bal = EH 2 rightTree −> bal = EH rotateLeft (root)
3 4 return End deleteRightBalance
50
Related Documents
Binary Search Trees
October 2019 21
Chapter 2 Part 2
June 2020 12
Chapter 7 Part 5
November 2019 9
13 Trees, Graphs And Search
November 2019 8
Chapter 17-part 2
June 2020 8
Chapter 2 - Groundwater Movements - Part 5.pdf
October 2019 8More Documents from "Trisha Veronica Candelaria AVENGOZA"
Hashing
April 2020 15
Definition About Analysis And Design Algorithm
April 2020 15