Transcript Document

Search
Trees
Chapter 8
Ceng-112 Data Structures I
2006
1
Binary Search Trees
• The binary search is a very efficient search algorithm, without
insertion and deletion, when we store ordered data in the array
structure.
• When we use linked list, in that case we have to use sequential
search as an inefficient search algorithm.
• Binary search trees provide a suitable structure.
Ceng-112 Data Structures I
2006
2
Binary Search Trees Definition
1. All terms in the left subtree are less than the root.
2. All terms in the right subtree are greater than or equal to the root.
3. Each subtree is itself a binary search tree.
<K
Figure 8-1
Ceng-112 Data Structures I
2006
3
Binary Search Trees
Figure 8-2
Ceng-112 Data Structures I
2006
4
Binary Search Trees
Figure 8-3
Ceng-112 Data Structures I
2006
5
Binary Search Trees
Preorder traversal?
Postorder traversal?
Inorder traversal?
Figure 8-4
Ceng-112 Data Structures I
2006
6
Binary Search Trees Binary Search Trees
Find the smallest value
algorithm findsmallestBST(val root <pointer>)
This algorithm finds the smallest node in a BST.
PRE root is a pointer to a non-empty BST.
Return address of smallest node
1. if (root->left null)
1. return (root)
2. return findsmallestBST(root->left)
end findsmallestBST
Ceng-112 Data Structures I
2006
7
Binary Search Trees
Find the smallest node in BST.
Figure 8-5
Ceng-112 Data Structures I
2006
8
Binary Search Trees Binary Search Trees
Find the largest value
algorithm findlargestBST(val root <pointer>)
This algorithm finds the larges node in a BST.
PRE root is a pointer to a non-empty BST.
Return address of largest node
1. if (root->right null)
1. return (root)
2. return findlargestBST(root->right)
end findlargestBST
Ceng-112 Data Structures I
2006
9
Binary Search Tree Search
Finding a specific node in the tree!
Figure 8-6
Ceng-112 Data Structures I
2006
10
We are looking for node 20.
Figure 8-7
Ceng-112 Data Structures I
2006
11
Binary Search Trees Binary Search Trees
Find the specific value
algorithm searchBST(val root <pointer>, val argument <key>)
Search a binary search tree for a given value.
PRE root is the root to a binary tree or subtree, argument is the key value
requested.
Return the node address if the value is found, null if the node is not in the tree.
1 If (root is null)
1 return null
2 If (argument < root->key)
1 return searchBST(root->left, argument)
3 else If (argument > root->key)
1 return searchBST(root->right, argument)
4 else
1 return root
end searchBST
Ceng-112 Data Structures I
2006
12
Binary Search Tree – Insert Node
Ceng-112 Data Structures I
2006
13
Binary Search Tree – Insert Node
algorithm insertBST(ref root <pointer>, val new <pointer>)
Insert node containing new node into BST using iteration
PRE root is address of the first node in a BST, new is address
of node containing data to be inserted.
POST new node inserted into tree.
Ceng-112 Data Structures I
2006
14
Binary Search Tree – Insert Node
1 If (root is null)
1 root = new
2 else
1 pwalk = root
2 loop (pwalk not null)
1 parent =pwalk
2 If (new->key < pwalk->key)
1 pwalk=pwalk->left
3 else pwalk=pwalk->right
Location for new node found
3 If (new->key < parent->key)
1 parent->left=new
4 else parent->right=new
3 return
end insertBST
Ceng-112 Data Structures I
2006
15
Binary Search Tree – Delete Node
Ceng-112 Data Structures I
2006
16
Binary Search Tree – Delete Node
Ceng-112 Data Structures I
2006
17
Binary Search Tree – Delete Node
algorithm deleteBST(ref root <pointer>, val dltkey <key>)
This algorithm deletes a node from BST.
Pre root is pointer to tree containing data to be deleted,
dltkey is key of node to be deleted.
Post node deleted & memory rcycled, if dltkey not found, root
unchanged.
Return true if node deleted, false if not found.
Ceng-112 Data Structures I
2006
18
Binary Search Tree – Delete Node
1 If (root null)
1 return false
2 If (dltkey < root->key) return deleteBST(root->left, dltkey)
3 else If (dltkey > root->key) return deleteBST(root->right, dltkey)
4 else /*(Delete node found --- Test for leaf node)*/
1 If (root ->left null)
1 dltprt=root, root =root->right, recycle(dltprt), return true
2 else If (root->right null)
1 dltprt=root, root =root->left, recycle(dltprt), return true
3 else /*Node is not a leaf, find largest node on left subtree*/
1 dltprt = root->left
2 loop (dltprt->right not null)
1 dltprt=dltprt->right
3 root->data =dltprt->data
4 return deleteBST(root->left, dltprt->data.key)
end deleteBST
Ceng-112 Data Structures I
2006
19
HW-8
1. Create a BST with positive integer numbers which are taken from the
screen.
2. Write the BST delete function which establishes to delete desired node
from the BST.
3. Write the BST list function which lists the nodes in the BST with
inorder traversal.
4. Collect all above functions under a user menu.
Load your HW-8 to FTP site until 14 May. 07 at 09:00 am.
Ceng-112 Data Structures I
2006
20
AVL Trees
In 1962, two Russian mathematicians, G. M. Adelson-Velskil and
E. M. Landis created balanced binary tree structure that is named
after them – the AVL trees.
O(n)
O(log2n)
|HL-HR| < = 1
Height balanced trees.
Ceng-112 Data Structures I
2006
21
Ceng-112 Data Structures I
2006
22
AVL Trees – Balancing
When we insert a node into a tree or delete a node from a tree, the
resulting tree may be unbalanced and we must rebalance it.
Figure 8-14 (a and b)
Ceng-112 Data Structures I
2006
23
All unbalanced trees fall into one of these four cases:
1. Left to left
2. Right to right
3. Right of left
4. Left of right
Ceng-112 Data Structures I
2006
24
LEFT-OF-LEFT
We must balance the left-height
tree by rotating the out-of-balance
node to the right.
Figure 8-15
Ceng-112 Data Structures I
2006
25
RIGHT-OF-RIGHT
We must balance the right-height
tree by rotating the out-of-balance
node to the left.
Figure 8-16
Ceng-112 Data Structures I
2006
26
RIGHT-OF-LEFT
1. Rotate left
2. Rotate right
Figure 8-17
Ceng-112 Data Structures I
2006
27
LEFT-OF-RIGHT
1. Rotate right
2. Rotate left
Figure 8-18
Ceng-112 Data Structures I
2006
28
AVL Node Structure
Node
key
data
leftsubtree
rightsubtree
bal
End Node
Ceng-112 Data Structures I
<key type>
<data type>
<pointer to Node>
<pointer to Node>
<LH, EH, RH>
2006
29
AVL Rotate Algorithm
algorithm rotateRight( ref root <tree pointer>)
This algorithm exchanges pointers to rotate the tree right.
PRE root points to tree to be rotated.
POST Node rotated and root updated.
1 tempPtr = root->left
2 root->left = tempPtr->right
3 tempPtr->right = root
4 root = tempPtr
5 return
end rotateRight
Ceng-112 Data Structures I
2006
30
AVL Insert
• The search and retrieval algorithms are the same as for any
binary tree.
• Inorder travelsal is used because AVL trees are search trees.
• As a binary search tree, we have to find suitable leaf node on left
or right subtree, then we connect new node to this parent node
and begin back out of tree.
• As we back out of tree we check the balance of each node. If we
find unbalanced node we balance it and continue up the tree.
• Not all inserts create an out of balance condition.
Ceng-112 Data Structures I
2006
31
AVL Insert Algorithm
algoritm AVLInsert (ref root <tree pointer>,
ref newPtr <tree pointer>,
ref taller <boolean>)
Using recursion, insert a node into AVL tree.
PRE root is a pointer to first node in AVL tree/subtree
newPtr is a pointer to new node to be inserted.
POST taller is a boolean: true indicating the subtree height has
increased, false indicating same height.
Ceng-112 Data Structures I
2006
32
AVL Insert Algorithm
1 if (root null) // Insert at root //
1 taller = true
2 root= newPtr
2 else
1 if (newPtr->key < root->key)
//left subtree //
1 AVLInsert(root->left, newPtr, taller)
2 if (taller) // insertion is completed and height is changed //
1 if (root left-height)
1 leftBalance(root, taller)
2 else if (root right-height)
1 taller =false
3 adjust balance factor
2 else if (newPtr->key > root->key)
//right subtree //
1 AVLInsert(root->right, newPtr, taller)
2 if (taller) // insertion is completed and height is changed //
1 if (root left-height)
1 taller =false
2 else if (root right-height)
1 rihtBalance(root, taller)
3 adjust balance factor
3 else
1 error (“Dupe Data”)
2 recycle(newPtr)
3 taller = false
3 return
end AVLInsert
Ceng-112 Data Structures I
2006
33
AVL Left Balance Algorithm
algorithm leftBalance(ref root <tree pointer>, ref taller <boolean>)
This algorithm is entered when the root is left heavy (the left subtree is higher then
the right subtree)
PRE root is a pointer to the root of the (sub)tree, taller is true.
POST root and taller has been updated.
1 leftTree = root->left
2 if (leftTree left-heigh) //Case 1: Left of left, single rotation required. //
1 rotateRight (root)
2 adjust balance factors
3 taller false
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
Ceng-112 Data Structures I
2006
34
AVL Delete Balancing
Figure 8-22
Ceng-112 Data Structures I
2006
35
Excercise
Which of the trees in the following figure is a valid binary search tree
and which one is not?
Figure 8-25
Ceng-112 Data Structures I
2006
36
Excercise
Travers the binary search tree using a inorder traversal.
Figure 8-26
Ceng-112 Data Structures I
2006
37
Excercise
The binary search tree was created starting with a null tree and entering
data from the keyboard. In what sequence were the data entered? If
there is more than one possible sequence, identify the alternatives.
Figure 8-27
Ceng-112 Data Structures I
2006
38
Excercise
The binary search tree was created starting with a null tree and entering
data from the keyboard. In what sequence were the data entered? If
there is more than one possible sequence, identify the alternatives.
Figure 8-28
Ceng-112 Data Structures I
2006
39
Excercise
Insert 44, 66 and 77 in the binary search tree.
Figure 8-29
Ceng-112 Data Structures I
2006
40
Excercise
Delete the node 60 and then 85 from the tree.
Figure 8-30
Ceng-112 Data Structures I
2006
41
Excercise
Balance the tree.
Figure 8-31
Ceng-112 Data Structures I
2006
42
Excercise
Balance the tree.
Figure 8-32
Ceng-112 Data Structures I
2006
43
Excercise
Add 49 to the AVL tree. The result must be an AVL tree. Show the
balance factors in the resulting tree.
Figure 8-33
Ceng-112 Data Structures I
2006
44
Excercise
Add 68 to the AVL tree. The result must be an AVL tree. Show the
balance factors in the resulting tree.
Figure 8-33
Ceng-112 Data Structures I
2006
45
HW-9
1. Create an AVL tree with positive integer numbers which are taken from
the screen.
2. Write the AVL delete function which establishes to delete desired node
from the AVL.
3. Write the AVL list function which lists the nodes in the AVL with
inorder traversal.
4. Collect all above functions under a user menu.
Load your HW-9 to FTP site until 14 May. 07 at 09:00 am.
Ceng-112 Data Structures I
2006
46