›
›

Cơ sở dữ liệu - Avl tree

pdf 74 trang vanle 3050
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Avl 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_avl_tree.pdf

Nội dung text: Cơ sở dữ liệu - Avl tree

  1. AVL Tree DEFINITION: AVL Tree is: • A Binary Search Tree, • in which the heights of the left and right subtrees of the root differ by at most 1, and • the left and right subtrees are again AVL trees. 1
  2. AVL Tree The name comes from the discoverers of this method, G.M.Adel'son-Vel'skii and E.M.Landis. The method dates from 1962. 2
  3. Balance factor Balance factor: • left_higher: HL = HR + 1 • equal_height: HL = HR • right_higher: HR = HL + 1 (HL , HR : the height of left and right subtree) In C++: enum Balance_factor {left_higher, equal_height, right_higher}; 3
  4. AVL Trees and non-AVL Trees AVL trees non-AVL trees 4
  5. Linked AVL Tree AVL_Node AVL_Tree data root left End AVL_Tree right balance End AVL_Node 5
  6. Insertion into an AVL tree 6
  7. Insertion into an AVL tree  Follow the usual BST insertion algorithm: insert the new node into the empty left or right subtree of a parent node as appropriate.  We use a reference parameter taller of the recursive_Insert function to show if the height of a subtree, for which the recursive function is called, has been increased.  At the stopping case of recursive, the empty subtree becomes a tree with one node for new data, taller is set to TRUE. 7
  8. Insertion into an AVL tree Consider the subtree, for which the recursive function is called,  While taller is TRUE, for each node on the path from the subtree's parent to the root of the tree, do the following steps. a) If the subtree was the shorter: its parent's balance factor must be changed, but the height of parent HL tree is unchanged. \ taller becomes FALSE. - b) If two subtree had the same height, its parent's balance factor must be changed, the height of HL parent tree increases by 1. / taller remains TRUE. - c) If the subtree was the higher subtree: only in this case, the definition of AVL is violated at the parent HL node, rebalancing must be done. / // 8 taller becomes FALSE
  9. Insertion into an AVL tree  When taller becomes FALSE, the algorithm terminates.  When rebalancing must be done, the height of the subtree always returned to its original value, so taller always becomes FALSE! 9
  10. Insertion into an AVL tree 10
  11. Insertion into an AVL tree Case b taller = TRUE 11
  12. Insertion into an AVL tree Case b taller = TRUE 12
  13. Insertion into an AVL tree Case b taller = TRUE 13
  14. Insertion into an AVL tree Case b taller = TRUE 14
  15. Insertion into an AVL tree Case b taller = TRUE 15
  16. Insertion into an AVL tree Case b taller = TRUE 16
  17. Insertion into an AVL tree 17
  18. Insertion into an AVL tree Case b taller = TRUE18
  19. Insertion into an AVL tree taller = TRUE Case b 19
  20. Insertion into an AVL tree Case a taller = TRUE 20
  21. Insertion into an AVL tree taller = FALSE Case a 21
  22. Insertion into an AVL tree 22
  23. Insertion into an AVL tree Case b taller = TRUE 23
  24. Insertion into an AVL tree taller = TRUE Case b 24
  25. Insertion into an AVL tree Case c taller = TRUE 25
  26. Insertion into an AVL tree Case c taller = TRUE 26
  27. Rebalancing at the node violating AVL definition Case c taller = TRUE Single Rotation 27
  28. Rebalancing at the node violating AVL definition Case c taller = FALSE taller = TRUE Single Rotation 28
  29. Insertion into an AVL tree 29
  30. Insertion into an AVL tree Case b taller = TRUE 30
  31. Insertion into an AVL tree Case b taller = TRUE 31
  32. Insertion into an AVL tree Case b taller = TRUE 32
  33. Insertion into an AVL tree taller = TRUE Case b 33
  34. Insertion into an AVL tree Case c taller = TRUE 34
  35. Rebalancing at the node violating AVL definition Case c taller = TRUE Double Rotation 35
  36. Rebalancing at the node violating AVL definition Case c Case c taller = FALSE taller = TRUE taller = TRUE Double Rotation 36
  37. Insert Node into AVL Tree Insert (val DataIn ) Inserts a new node into an AVL tree. Post If the key of DataIn already belongs to the AVL tree, duplicate_error is returned. Otherwise, DataIn is inserted into the tree in such a way that the properties of an AVL tree are preserved. Return duplicate_error or success. Uses recursive_Insert . 1. taller // Has the tree grown in height? 2. return recursive_Insert (root, DataIn, taller) End Insert 37
  38. Recursive Insert recursive_Insert (ref subroot , val DataIn , ref taller ) Inserts a new node into an AVL tree. 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 an AVL tree are preserved. If the subtree is increased in height, the parameter taller is set to TRUE; otherwise it is set to FALSE. Return duplicate_error or success. Uses recursive_Insert , left_balance, right_balance functions. 38
  39. Recursive Insert (cont.) 1. result = success 2. if (subroot is NULL) 1. Allocate subroot 2. subroot ->data = DataIn - 3. taller = TRUE H = 0 H = 1 3. else if (DataIn = subroot ->data) 1. result = duplicate_error 2. taller = FALSE 4. else if (DataIn data) 39
  40. Recursive Insert (cont.) 4. else if (DataIn data) // Insert in the left subtree 1. result = recursive_Insert(subroot->left, DataIn, taller ) 2. if (taller = TRUE) Case c 1. if (balance of subroot = left_higher) H 1. left_balance (subroot) L / // 2. taller = FALSE // Rebalancing always shortens the tree. Case b 2. else if (balance of subroot = equal_height) HL 1. subroot->balance = left_higher - / 3. else if (balance of subroot = right_higher) Case a 1. subroot->balance = equal_height H 2. taller = FALSE L \ -
  41. 4. else // (DataIn > subroot ->data) Insert in the right subtree 1. result = recursive_Insert(subroot->right, DataIn, taller ) 2. if (taller = TRUE) Case a 1. if (balance of subroot = left_higher) HR 1. subroot->balance = equal_height / 2. taller = FALSE - Case b 2. else if (balance of subroot = equal_height) HR 1. subroot->balance = right_higher - \ 3. else if (balance of subroot = right_higher) Case c 1. right_balance (subroot) HR 2. taller = FALSE \ \\ // Rebalancing always shortens the tree. 1. return result End recursive_Insert 41
  42. Rotation of an AVL Tree subroot right_tree right_tree subroot rotate left Total height = h + 3 Total height = h + 2 1. right_tree = subroot->right 3. right_tree->left = subroot 2. subroot->right = right_tree->left 4. subroot = right_tree 42
  43. Rotation of an AVL Tree rotate_left (ref subroot ) Pre subroot is not NULL and points to the subtree of the AVL tree. This subtree has a nonempty right subtree. Post subroot is reset to point to its former right child, and the former subroot node is the left child of the new subroot node. 1. right_tree = subroot->right 2. subroot->right = right_tree->left 3. right_tree->left = subroot 4. subroot = right_tree End rotate_left 43
  44. Double Rotate subroot sub_tree right_tree right_tree subroot sub_tree Total height = h + 2 One of T2 or T3 has height h. Total height = h + 3 44
  45. Double Rotate The new balance factors for subroot and right_tree depend on the previous balance factor for subtree old new new new sub_tree subroot right_tree sub_tree - - - - / - \ - \ / - - 45
  46. right_balance function right_balance (ref subroot ) Pre subroot points to a subtree of an AVL tree, doubly unbalanced on the right. Post The AVL properties have been restored to the subtree. Uses rotate_right, rotate_left functions. 46
  47. right_balance function (cont.) 1. right_tree = subroot->right 2. if (balance of right_tree = right_higher) 1. subroot->balance = equal_height 2. right_tree->balance = equal_height 3. rotate_left (subroot) 3. if (balance of right_tree = equal_height) // impossible case 47
  48. right_balance function (cont.) 4. if (balance of right_tree = left_higher) 1. subtree = right_tree->left 2. subtree->balance = equal_height 3. rotate_right (right_tree) 4. rotate_left (subroot) 48
  49. right_balance function (cont.) 5. if (balance of subtree = equal_height) 1. subroot->balance = equal_height 2. right_tree->balance = equal_height 6. else if (balance of subtree = left_higher) 1. subroot->balance = equal_height 2. right_tree->balance = right_higher 7. else // (balance of subtree = right_higher) 1. subroot->balance = left_higher 2. right_tree->balance = equal_height End right_balance old new new new sub_tree subroot right_tree sub_tree - - - - / - \ - \ / - - 49
  50. Removal of a node  Reduce the problem to the case when the node x to be removed has at most one child.  We use a parameter shorter to show if the height of a subtree has been shortened.  While shorter is TRUE, do the following steps for each node p on the path from the parent of x to the root of the tree.  When shorter becomes FALSE, the algorithm terminates. 50
  51. Removal of a node • Case 1: Node p has balance factor equal. So only this balance factor must be changed. The height of p is unchanged. shorter becomes FALSE. 51
  52. Removal of a node • Case 2: The balance factor of p is not equal, the taller subtree was shortened. So the balance factor must be changed. The height of p is decreased. shorter remains TRUE. 52
  53. Removal of a node • Case 3: The balance factor of p is not equal, the shorter subtree was shortened. So AVL definition is violated at p. Rebalancing must be done. Let q be the root of the taller subtree of p. Case 3a: The balance factor of q is equal. So single rotation needs to do. shorter becomes FALSE. 53
  54. Removal of a node Case 3b: The balance factor of q is the same as that of p. So single rotation needs to do. Balance factors of p and q become equal. shorter remains TRUE. 54
  55. Removal of a node Case 3c: The balance factor of q and p are opposite. Double rotation must be done (first around q, then around p). The balance factor of the new root is equal. Other balance factors are set as appropriate. shorter remains TRUE. 55
  56. Removal of a node Delete p p 56
  57. Removal of a node Delete p p 57
  58. Removal of a node Delete p Case 2 shorter = TRUE 58
  59. Removal of a node Delete p shorter = TRUE Case 2 59
  60. Removal of a node Delete p Case 3b shorter = TRUE 60
  61. Removal of a node Delete p Case 3b shorter = TRUE 61
  62. Removal of a node Delete p shorter = TRUE shorter =Case TRUE 3b 62
  63. Removal of a node Delete p Case 3c shorter = TRUE shorter = TRUE 63
  64. Removal of a node Delete p Case 3c shorter = TRUE shorter = TRUE 64
  65. Removal of a node Delete p Case 3c shorter = TRUE 65
  66. Removal of a node Delete p Case 3c shorter = TRUE 66
  67. Analysis of AVL Tree  The number of recursive calls to insert a new node can be as large as the height of the tree.  At most one (single or double) rotation will be done per insertion.  A rotation improves the balance of the tree, so later insertions are less likely to require rotations. 67
  68. Analysis of AVL Tree  It is very difficult to find the height of the average AVL tree, but the worst case is much easier.  The worst-case behavior of AVL trees is essentially no worse than the behaviour of random BST.  The average behaviour of AVL trees is much better than that of random BST, almost as good as that which could be obtained from a perfectly balanced tree. 68
  69. Analysis of AVL Tree  To find the maximum height of AVL tree with n nodes, we instead find the minimum number of nodes that an AVL tree of height h can have. • Fh: an AVL tree of height h with minimum number of nodes. • FL: a left subtree of height hL= h-1 with minimum number of nodes. • FR: a right subtree of height hR = h-2 with minimum number of nodes. 69
  70. Built sparse AVL trees 70
  71. Fibonacci trees  Trees, as sparse as possible for AVL tree, are call Fibonacci trees. 71
  72. Analysis of AVL Tree If |T| is the number of nodes in tree T, we have: where and And we can calculate 72
  73. Analysis of AVL Tree  The sparsest possible AVL tree with n nodes has height about 1.44 lg n compared to: . A perfectly balanced BST with n nodes has height about lg n. . A random BST, on average, has height about 1.39 lg n. . A degenerate BST has height as large as n. 73
  74. Analysis of AVL Tree  Hence the algorithm for manipulating AVL trees are guaranteed to take no more than about 44 percent more time than the optimum.  In practice, AVL trees do much better than this on average, perhaps as small as lg n + 0.25. 74