›
›

Cơ sở dữ liệu - Chapter 7: Tree

pdf 90 trang vanle 2340
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chapter 7: Tree", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_du_lieu_chapter_7_tree.pdf

Nội dung text: Cơ sở dữ liệu - Chapter 7: Tree

  1. Chapter 7 - Tree Basic tree concepts Binary trees Binary Search Tree (BST) 1
  2. Expression Trees 12
  3. Binary Tree ADT DEFINITION: A binary tree ADT is either empty, or it consists of a node called root together with two binary trees called the left and the right subtree of the root. Basic operations: • Construct a tree, leaving it empty. • Insert an element. • Remove an element. • Search an element. • Retrieve an element. • Traverse the tree, performing a given operation on each element. 13
  4. Binary Tree ADT Extended operations: • Determine whether the tree is empty or not. • Find the size of the tree. • Clear the tree to make it empty. 14
  5. Specifications for Binary Tree Create() isFull() isEmpty() Size() Clear() Search (ref DataOut ) Depend on various Insert (val DataIn ) types of binary Remove (val key ) trees (BST, AVL, 2d-tree) Retrieve (ref DataOut ) 15
  6. Specifications for Binary Tree • Binary Tree Traversal: Each node is processed once and only once in a predetermined sequence. • Depth-First Traverse: preOrderTraverse (ref Operation(ref Data )) inOrderTraverse (ref Operation(ref Data )) postOrderTraverse (ref Operation(ref Data )) • Breadth-First Traverse: BreadthFirstTraverse (ref Operation(ref Data )) 16
  7. Contiguous Implementation of Binary Tree BinaryTree Data > End BinaryTree 0 1 2 3 4 5 6 A B C D E F G Physical Conceptual i (suitable for complete tree, nearly complete tree, and 2i+1 2i+2 bushy tree) 24
  8. Contiguous Implementation of Binary Tree Record Data Parent Flag End Record BinaryTree Data > End BinaryTree 0 1 2 3 4 5 6 H Data A B E C F G H Conceptual Parent - A B A C C F Flag - L R R L R R Physical (suitable for sparse tree) 25
  9. Contiguous Implementation of Binary Tree BinaryTree NLR > LNR > End BinaryTree 0 1 2 3 4 5 6 NLR A B E C F H G LNR B E A F H C G H Physical Conceptual (A binary tree without identical data can be restored from two array of LNR and NLR traverse) 26
  10. Linked Implementation of Binary Tree BinaryNode A data left right End BinaryNode B C BinaryTree root E F G End BinaryTree Physical 27
  11. Depth-First Traversal Auxiliary functions for Depth_First Traversal: recursive_preOrder recursive_inOrder recursive_postOrder 28
  12. PreOrder Traversal Algorithm recursive_preOrder (val subroot , ref Operation(ref Data )) Traverses a binary tree in node-left-right sequence. Pre subroot points to the root of a tree/ subtree. Post each node has been processed in order. 1. if (subroot is not NULL) 1. Operation(subroot->data) 2. recursive_preOrder(subroot->left) 3. recursive_preOrder(subroot->right) End recursive_preOrder 29
  13. InOrder Traversal Algorithm recursive_inOrder (val subroot , ref Operation(ref Data )) Traverses a binary tree in left-node-right sequence Pre subroot points to the root of a tree/ subtree Post each node has been processed in order 1. if (subroot is not NULL) 1. recursive_inOrder(subroot->left) 2. Operation(subroot->data) 3. recursive_inOrder(subroot->right) End recursive_inOrder 3030
  14. PostOrder Traversal Algorithm recursive_postOrder (val subroot , ref Operation(ref Data )) Traverses a binary tree in left-right-node sequence Pre subroot points to the root of a tree/ subtree Post each node has been processed in order 1. if (subroot is not NULL) 1. recursive_postOrder(subroot->left) 2. recursive_postOrder(subroot->right) 3. Operation(subroot->data) End recursive_postOrder 31
  15. Depth-First Traversal preOrderTraverse (ref Operation(ref Data )) 1. recursive_preOrder(root, Operation) End preOrderTraverse inOrderTraverse (ref Operation(ref Data )) 1. recursive_inOrder(root, Operation) End inOrderTraverse postOrderTraverse (ref Operation(ref Data )) 1. recursive_postOrder(root, Operation) End postOrderTraverse 32
  16. Breadth-First Traversal Algorithm BreadthFirstTraverse (ref Operation(ref Data )) Traverses a binary tree in sequence from lowest level to highest level, in each level traverses from left to right. Post each node has been processed in order Uses Queue ADT 34
  17. Breadth-First Traversal Algorithm BreadthFirstTraverse (ref Operation(ref Data )) 1. if (root is not NULL) 1. queueObj 2. queueObj.EnQueue(root) 3. loop (not queueObj.isEmpty()) 1. queueObj.QueueFront(pNode) 2. queueObj.DeQueue() 3. Operation(pNode->data) 4. if (pNode->left is not NULL) 1. queueObj.EnQueue(pNode->left) 5. if (pNode->right is not NULL) 1. queueObj.EnQueue(pNode->right) End BreadthFirstTraverse 35
  18. BinaryBinary Search Search Tree Tree (BST) 36
  19. BinaryBinary Search Search Tree Tree (BST) . BST is one of implementations for ordered list. . In BST we can search quickly (as with binary search on a contiguous list). . In BST we can make insertions and deletions quickly (as with a linked list). . When a BST is traversed in inorder, the keys will come out in sorted order. 37 37
  20. Binary Search Tree (BST) Auxiliary functions for Search: recursive_Search iterative_Search 38
  21. Search node in BST (recursive version) recursive_Search (val subroot , val target ) Searches target in the subtree. Pre subroot points to the root of a tree/ subtree. Post If target is not in the subtree, NULL is returned. Otherwise, a pointer to the node containing the target is returned. 39
  22. Search node in BST (recursive version) 1. if (subroot is NULL) OR (subroot->data = target) 1. return subroot 2. else if (target data) 1. return recursive_Search(subroot->left, target) 3. else 1. return recursive_Search(subroot->right, target) subroot End recursive_Search Target = 22 40
  23. Search node in BST (recursive version) 1. if (subroot is NULL) OR (subroot->data = target) 1. return subroot 2. else if (target data) 1. return recursive_Search(subroot->left, target) 3. else 1. return recursive_Search(subroot->right, target) End recursive_Search subroot Target = 22 41
  24. Search node in BST (recursive version) 1. if (subroot is NULL) OR (subroot->data = target) 1. return subroot 2. else if (target data) 1. return recursive_Search(subroot->left, target) 3. else 1. return recursive_Search(subroot->right, target) End recursive_Search subroot Target = 22 42
  25. Search node in BST (recursive version) 1. if (subroot is NULL) OR (subroot->data = target) 1. return subroot 2. else if (target data) 1. return recursive_Search(subroot->left, target) 3. else 1. return recursive_Search(subroot->right, target) End recursive_Search Target = 22 subroot 43
  26. Search Node in BST (nonrecursive version) iterative_Search (val subroot , val target ) Searches target in the subtree. Pre subroot points to the root of a tree/ subtree. Post If target is not in the subtree, NULL is returned. Otherwise, a pointer to the node containing the target is returned. 44
  27. Search Node in BST (nonrecursive version) 1. while (subroot is not NULL) AND (subroot->data.key data.key) 1. subroot = subroot->left 2. else 1. subroot = subroot->right 2. return subroot subroot End iterative_Search Target = 22 45
  28. Search Node in BST (nonrecursive version) 1. while (subroot is not NULL) AND (subroot->data.key data.key) 1. subroot = subroot->left 2. else 1. subroot = subroot->right 2. return subroot End iterative_Search subroot Target = 22 46
  29. Search Node in BST (nonrecursive version) 1. while (subroot is not NULL) AND (subroot->data.key data.key) 1. subroot = subroot->left 2. else 1. subroot = subroot->right 2. return subroot End iterative_Search subroot Target = 22 47
  30. Search Node in BST (nonrecursive version) 1. while (subroot is not NULL) AND (subroot->data.key data.key) 1. subroot = subroot->left 2. else 1. subroot = subroot->right 2. return subroot End iterative_Search Target = 22 subroot 48
  31. Search node in BST Search (ref DataOut ) Searches target in the subtree. Pre DataOut contains value needs to be found in key field. Post DataOut will reveive all other values in other fields if that key is found. Return success or notPresent Uses Auxiliary function recursive_Search or iterative_Search 1. pNode = recursive_Search(root, DataOut.key) 2. if (pNode is NULL) 1. return notPresent 3. dataOut = pNode->data 4. return success End Search 49
  32. Search node in BST . The same keys may be built into BST of many different shapes. . Search in bushy BST with n nodes will do O(log n) comparisons of keys . If the tree degenerates into a long chain, search will do Ө(n) comparisons on n vertices. . The bushier the tree, the smaller the number of comparisons of keys need to be done. 51
  33. Insert Node into BST 52
  34. Insert Node into BST Question: ?? Can Insert method use recursive_Search or iterative_Search instead of recursive_Insert like that: Insert (val DataIn ) 1. pNode = recursive_Search (root, DataIn.key) 2. if (pNode is NULL) 1. Allocate pNode 2. pNode->data = DataIn 3. return success 3. else 1. return duplicate_error End Insert 53
  35. Insert Node into BST Auxiliary functions for Insert: recursive_Insert iterative_Insert 54
  36. Recursive Insert recursive_Insert (ref subroot , val DataIn ) Inserts a new node into a BST. Pre subroot points to the root of a tree/ subtree. DataIn contains data to be inserted into the subtree. Post If the key of DataIn already belongs to the subtree, duplicate_error is returned. Otherwise, DataIn is inserted into the subtree in such a way that the properties of a BST are preserved. Return duplicate_error or success. Uses recursive_Insert function. 55
  37. Recursive Insert (cont.) recursive_Insert (ref subroot , val DataIn ) subroot 1. if (subroot is NULL) 1. Allocate subroot 2. subroot->data = DataIn 3. return success 2. else if (DataIn.key data.key) 1. return recursive_Insert(subroot->left, DataIn) 3. else if (DataIn.key > subroot->data.key) DataIn.key = 22 1. return recursive_Insert(subroot->right, DataIn) 4. else 1. return duplicate_error 5. End recursive_Insert 56
  38. Recursive Insert (cont.) recursive_Insert (ref subroot , val DataIn ) subroot 1. if (subroot is NULL) 1. Allocate subroot 2. subroot->data = DataIn 3. return success 2. else if (DataIn.key data.key) 1. return recursive_Insert(subroot->left, DataIn) 3. else if (DataIn.key > subroot->data.key) DataIn.key = 22 1. return recursive_Insert(subroot->right, DataIn) 4. else 1. return duplicate_error 5. End recursive_Insert 57
  39. Recursive Insert (cont.) recursive_Insert (ref subroot , val DataIn ) 1. if (subroot is NULL) subroot 1. Allocate subroot 2. subroot->data = DataIn 3. return success 2. else if (DataIn.key data.key) 1. return recursive_Insert(subroot->left, DataIn) 3. else if (DataIn.key > subroot->data.key) DataIn.key = 22 1. return recursive_Insert(subroot->right, DataIn) 4. else 1. return duplicate_error 5. End recursive_Insert 58
  40. Recursive Insert (cont.) recursive_Insert (ref subroot , val DataIn ) 1. if (subroot is NULL) 1. Allocate subroot 2. subroot->data = DataIn subroot 3. return success 2. else if (DataIn.key data.key) 1. return recursive_Insert(subroot->left, DataIn) 3. else if (DataIn.key > subroot->data.key) DataIn.key = 22 1. return recursive_Insert(subroot->right, DataIn) 4. else 1. return duplicate_error 5. End recursive_Insert 59
  41. Recursive Insert (cont.) recursive_Insert (ref subroot , val DataIn ) 1. if (subroot is NULL) 1. Allocate subroot 2. subroot->data = DataIn subroot 3. return success 2. else if (DataIn.key data.key) 1. return recursive_Insert(subroot->left, DataIn) 3. else if (DataIn.key > subroot->data.key) DataIn.key = 22 1. return recursive_Insert(subroot->right, DataIn) 4. else 1. return duplicate_error 5. End recursive_Insert 60
  42. Iterative Insert iterative_Insert (ref subroot , val DataIn ) Inserts a new node into a BST. Pre subroot is NULL or points to the root of a subtree. DataIn contains data to be inserted into the subtree. Post If the key of DataIn already belongs to the subtree, duplicate_error is returned. Otherwise, DataIn is inserted into the subtree in such a way that the properties of a BST are preserved. Return duplicate_error or success. 61
  43. Iterative Insert (cont.) iterative_Insert (ref subroot , val DataIn ) 1. if (subroot is NULL) 1. Allocate subroot subroot 2. subroot->data = DataIn 3. return success 2. else DataIn.key = 22 62
  44. Iterative Insert (cont.) iterative_Insert (ref subroot , val DataIn ) 1. if (subroot is NULL) 1. Allocate subroot subroot 2. subroot->data = DataIn 3. return success 2. else DataIn.key = 22 63
  45. Iterative Insert (cont.) subroot 2. else pCurr 1. pCurr = subroot 2. loop (pCurr is not NULL) 1. if (pCurr->data.key = DataIn.key) 1. return duplicate_error 2. parent = pCurr 3. if (DataIn.key data.key) 1. pCurr = parent -> left 4. else 1. pCurr = parent -> right 3. if (DataIn.key data.key) 1. Allocate parent->left 2. parent->left.data = DataIn DataIn.key = 22 4. else 1. Allocate parent->right 2. parent->right.data = DataIn 5. return success End Iterative_Insert 64
  46. Iterative Insert (cont.) subroot 2. else parent 1. pCurr = subroot 2. loop (pCurr is not NULL) pCurr 1. if (pCurr->data.key = DataIn.key) 1. return duplicate_error 2. parent = pCurr 3. if (DataIn.key data.key) 1. pCurr = parent -> left 4. else 1. pCurr = parent -> right 3. if (DataIn.key data.key) 1. Allocate parent->left 2. parent->left.data = DataIn DataIn.key = 22 4. else 1. Allocate parent->right 2. parent->right.data = DataIn 5. return success End Iterative_Insert 65
  47. Iterative Insert (cont.) 2. else subroot 1. pCurr = subroot 2. loop (pCurr is not NULL) parent 1. if (pCurr->data.key = DataIn.key) 1. return duplicate_error pCurr 2. parent = pCurr 3. if (DataIn.key data.key) 1. pCurr = parent -> left 4. else 1. pCurr = parent -> right 3. if (DataIn.key data.key) 1. Allocate parent->left 2. parent->left.data = DataIn DataIn.key = 22 4. else 1. Allocate parent->right 2. parent->right.data = DataIn 5. return success End Iterative_Insert 66
  48. Iterative Insert (cont.) 2. else subroot 1. pCurr = subroot 2. loop (pCurr is not NULL) 1. if (pCurr->data.key = DataIn.key) 1. return duplicate_error parent 2. parent = pCurr 3. if (DataIn.key data.key) 1. pCurr = parent -> left pCurr 4. else 1. pCurr = parent -> right 3. if (DataIn.key data.key) 1. Allocate parent->left 2. parent->left.data = DataIn DataIn.key = 22 4. else 1. Allocate parent->right 2. parent->right.data = DataIn 5. return success End Iterative_Insert 67
  49. Iterative Insert (cont.) 2. else subroot 1. pCurr = subroot 2. loop (pCurr is not NULL) 1. if (pCurr->data.key = DataIn.key) 1. return duplicate_error parent 2. parent = pCurr 3. if (DataIn.key data.key) 1. pCurr = parent -> left pCurr 4. else 1. pCurr = parent -> right 3. if (DataIn.key data.key) 1. Allocate parent->left 2. parent->left.data = DataIn DataIn.key = 22 4. else 1. Allocate parent->right 2. parent->right.data = DataIn 5. return success End Iterative_Insert 68
  50. Insert Node into BST Insert (val DataIn ) Inserts a new node into a BST. Post If the key of DataIn already belongs to the BST, duplicate_error is returned. Otherwise, DataIn is inserted into the tree in such a way that the properties of a BST are preserved. Return duplicate_error or success. Uses recursive_Insert or iterative_Insert function. 1. return recursive_Insert (root, DataIn) End Insert 69
  51. Insert Node into BST . Insertion a new node into a random BST with n nodes takes O(log n) steps. . Insertion may take n steps when BST degenerates to a chain. . If the keys are inserted in sorted order into an empty tree, BST becomes a chain. 70
  52. Delete node from BST • Deletion of a leaf: Set the deleted node's parent link to NULL. 71
  53. Delete node from BST • Deletion of a node having only right subtree or left subtree: Attach the subtree to the deleted node's parent. 72
  54. Delete node from BST Replace X by W Delete original W W is predecessor of X • Deletion of a node having both subtrees: Replace the deleted node by its predecessor or by its successor, recycle this node instead. 73
  55. Delete node from BST • Node having both subtrees 74
  56. Delete node from BST • Node having both subtrees 75
  57. Delete node from BST Auxiliary functions for Insert: recursive_Delete iterative_Delete 76
  58. Recursive Delete recursive_Delete (ref subroot , val key ) Deletes a node from a BST. Pre subroot is NULL or points to the root of a subtree. Key contains value needs to be removed from BST. Post If key is found, it will be removed from BST. Return notFound or success. Uses recursive_Delete and RemoveNode functions. 77
  59. Recursive Delete (cont.) recursive_Delete (ref subroot , val key ) 1. if (subroot is NULL) 1. return notFound 2. else if (key data.key) 1. return recursive_Delete(subroot->left, key) 3. else if (key > subroot->data.key) 1. return recursive_Delete(subroot->right, key) 4. else 1. RemoveNode(subroot) 2. return success End recursive_Delete 78
  60. Delete Node from BST Delete (val key ) Deletes a node from a BST. Pre subroot is NULL or points to the root of a subtree. Key contains value needs to be removed from BST. Post If key is found, it will be removed from BST. Return notFound or success. Uses recursive_Delete and RemoveNode functions. 1. return recursive_Delete (root, key) End Delete 79
  61. Auxiliary Function RemoveNode RemoveNode (ref subroot , val key ) 1. pDel = subroot // remember node to delete at end. 2. if (subroot ->left is NULL) // leaf node or node having only right subtree. 1. subroot = subroot->right // (a) and (b) 3. else if (subroot->right is NULL) // node having only left subtree. 1. subroot = subroot->left subroot subroot pDel pDel (a) key needs to be deleted = 18 (b) 80
  62. Auxiliary Function RemoveNode RemoveNode (ref subroot , val key ) 1. pDel = subroot // remember node to delete at end. 2. if (subroot ->left is NULL) // leaf node or node having only right subtree. 1. subroot = subroot->right // (a) and (b) 3. else if (subroot->right is NULL) // node having only left subtree. 1. subroot = subroot->left subroot subroot pDel pDel (a) key needs to be deleted = 18 key needs to be deleted = 18 (b) 81
  63. Auxiliary Function RemoveNode RemoveNode (ref subroot , val key ) 1. pDel = subroot // remember node to delete at end. 2. if (subroot ->left is NULL) // leaf node or node having only right subtree. 1. subroot = subroot->right 3. else if (subroot->right is NULL) // node having only left subtree. 1. subroot = subroot->left // (c) subroot pDel key needs to be deleted = 44 (c) 82
  64. Auxiliary Function RemoveNode RemoveNode (ref subroot , val key ) 1. pDel = subroot // remember node to delete at end. 2. if (subroot ->left is NULL) // leaf node or node having only right subtree. 1. subroot = subroot->right 3. else if (subroot->right is NULL) // node having only left subtree. 1. subroot = subroot->left // (c) subroot pDel key needs to be deleted = 44 (c) 83
  65. Auxiliary Function RemoveNode (cont.) 4. else // node having both subtrees. (d) 1. parent = subroot 2. pDel = parent ->left // move left to find the predecessor. 3. loop (pDel->right is not NULL) // pDel is not the predecessor 1. parent = pDel 2. pDel = pDel->right key needs to be deleted = 23 4. subroot->data = pDel->data parent subroot 5. if (parent = subroot) 1. parent->left = pDel->left pDel 6. else 1. parent->right = pDel->left 7. recycle pDel End RemoveNode (d) 84
  66. Auxiliary Function RemoveNode (cont.) 1. else // node having both subtrees. (d) 1. parent = subroot 2. pDel = parent ->left // move left to find the predecessor. 3. loop (pDel->right is not NULL) // pDel is not the predecessor 1. parent = pDel 2. pDel = pDel->right key needs to be deleted = 23 4. subroot->data = pDel->data subroot 5. if (parent = subroot) 1. parent->left = pDel->left parent 6. else 1. parent->right = pDel->left 7. recycle pDel pDel End RemoveNode (d) 85
  67. Auxiliary Function RemoveNode (cont.) 1. else // node having both subtrees. (d) 1. parent = subroot 2. pDel = parent ->left // move left to find the predecessor. 3. loop (pDel->right is not NULL) // pDel is not the predecessor 1. parent = pDel 2. pDel = pDel->right key needs to be deleted = 23 4. subroot->data = pDel->data subroot 5. if (parent = subroot) 1. parent->left = pDel->left 6. else 1. parent->right = pDel->left 7. recycle pDel parent End RemoveNode pDel (d) 86
  68. Auxiliary Function RemoveNode (cont.) 1. else // node having both subtrees. (d) 1. parent = subroot 2. pDel = parent ->left // move left to find the predecessor. 3. loop (pDel->right is not NULL) // pDel is not the predecessor 1. parent = pDel 2. pDel = pDel->right key needs to be deleted = 23 4. subroot->data = pDel->data subroot 5. if (parent = subroot) 1. parent->left = pDel->left 6. else 1. parent->right = pDel->left 7. recycle pDel parent End RemoveNode pDel 22 (d) 87
  69. Auxiliary Function RemoveNode (cont.) 1. else // node having both subtrees. (d) 1. parent = subroot 2. pDel = parent ->left // move left to find the predecessor. 3. loop (pDel->right is not NULL) // pDel is not the predecessor 1. parent = pDel 2. pDel = pDel->right key needs to be deleted = 23 4. subroot->data = pDel->data subroot 5. if (parent = subroot) 22 1. parent->left = pDel->left 6. else 1. parent->right = pDel->left 7. recycle pDel parent End RemoveNode pDel 22 (d) 88
  70. Auxiliary Function RemoveNode (cont.) 1. else // node having both subtrees. (d) 1. parent = subroot 2. pDel = parent ->left // move left to find the predecessor. 3. loop (pDel->right is not NULL) // pDel is not the predecessor 1. parent = pDel 2. pDel = pDel->right key needs to be deleted = 23 4. subroot->data = pDel->data subroot 5. if (parent = subroot) 22 1. parent->left = pDel->left 6. else 1. parent->right = pDel->left parent 7. recycle pDel End RemoveNode pDel (d) 89
  71. Performance of random BST  The average number of nodes visited during a search of average BST with n nodes approximately 2 ln2 = (2 ln 2) (lg n)≈ 1.39 lg n  The average BST requires approximately 2 ln2 ≈ 1.39 times as many comparisons as a completely balanced tree. 90