數(shù)據(jù)結構與程序設計(27)AVL Tree

1、11/23/2021數(shù)據(jù)結構與程序設計 110.4 Height Balance: AVL Treesn10.3 節(jié)創(chuàng)建的二叉查找樹左右子樹高度不能節(jié)創(chuàng)建的二叉查找樹左右子樹高度不能保證總是近似平衡。例如保證總是近似平衡。例如8個節(jié)點時，個節(jié)點時，8為根，為根，整棵右子樹為空。整棵右子樹為空。nAVL Definition:nAn 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 in which the

2、 left and right subtrees are again AVL trees.11/23/2021數(shù)據(jù)結構與程序設計 2Height Balance: AVL TreesnWith each node of an AVL tree is associated a balance factor that is left higher, equal, or right higher according, respectively, as the left subtree has height greater than, equal to, or less than that of th

3、e right subtree.11/23/2021數(shù)據(jù)結構與程序設計 3Height Balance: AVL TreesnIn drawing diagrams, we shall show a left-higher node by /, a node whose balance factor is equal by , and a right-higher node by .11/23/2021數(shù)據(jù)結構與程序設計 4Height Balance: AVL Trees11/23/2021數(shù)據(jù)結構與程序設計 5Height Balance: AVL Trees11/23/2021數(shù)據(jù)結構與

4、程序設計 6Height Balance: AVL TreesnWe employ an enumerated data type to record balance factors: nenum Balance_factor left_higher, equal_height, right_higher ;nAVL nodes are structures derived from binary search tree nodes with balance factors included.Left* balance_factor data right*Left* data right*AV

5、L Node 是是Tree Node的子類的子類Binary Search Tree Node11/23/2021數(shù)據(jù)結構與程序設計 7Binary Tree Nodeenum Balance_factor left_higher, equal_height, right_higher ;template struct Binary_node / data members:Entry data;Binary_node *left;Binary_node *right;/ constructors:Binary_node( );Binary_node(const Entry &x);/

6、virtual methods:virtual void set_balance(Balance_factor b);virtual Balance_factor get_balance( ) const;11/23/2021數(shù)據(jù)結構與程序設計 8AVL Trees Node#include Binary_node.cpptemplate struct AVL_node: public Binary_node / additional data member:Balance_factor balance;/ constructors:AVL_node( );AVL_node(const Rec

7、ord &x);/ overridden virtual functions:void set_balance(Balance_factor b);Balance_factor get_balance( ) const;11/23/2021數(shù)據(jù)結構與程序設計 9AVL Node的繼承分析Left* balance_factor data right*Left* data right*紅色：Binary Node中的元素。黑色：子類AVL node中增加的元素。Tree NodeAVL NodeLeft* balance_factor data right*Binary_node* le

8、ft;left = new AVL_Node; /父類指針指向子類的對象父類指針指向子類的對象Left-setBanlance(equal_height); /此處發(fā)生動態(tài)綁定，調(diào)用的是此處發(fā)生動態(tài)綁定，調(diào)用的是子類子類AVL_Node中中setBanlance方法的實現(xiàn)。方法的實現(xiàn)。11/23/2021數(shù)據(jù)結構與程序設計 10AVL Trees Node實現(xiàn)實現(xiàn)AVL_node : AVL_node()left = NULL;right = NULL;balance = equal_height;template AVL_node : AVL_node(const Record &x

9、)data = x;left = NULL;right = NULL;balance = equal_height;11/23/2021數(shù)據(jù)結構與程序設計 11AVL Trees Node實現(xiàn)實現(xiàn)template void AVL_node : set_balance(Balance_factor b)balance = b;template Balance_factor AVL_node : get_balance( ) constreturn balance;11/23/2021數(shù)據(jù)結構與程序設計 12Binary Tree Nodeenum Balance_factor left_hig

10、her, equal_height, right_higher ;template struct Binary_node / data members:Entry data;Binary_node *left;Binary_node *right;/ constructors:Binary_node( );Binary_node(const Entry &x);/ virtual methods:virtual void set_balance(Balance_factor b);virtual Balance_factor get_balance( ) const;11/23/202

11、1數(shù)據(jù)結構與程序設計 13Binary Tree Node 實現(xiàn)實現(xiàn)template Binary_node : Binary_node()left = NULL;right = NULL;template Binary_node : Binary_node(const Entry &x)data = x;left = NULL;right = NULL;11/23/2021數(shù)據(jù)結構與程序設計 14Binary Tree Node 實現(xiàn)實現(xiàn)template void Binary_node : set_balance(Balance_factor b)template Balance_

12、factor Binary_node : get_balance( ) constreturn equal_height;11/23/2021數(shù)據(jù)結構與程序設計 15left-get_balance( )nWe often invoke these methods ( set_balance, get_balance) through pointers to nodes, such as left-get_balance( ). nLeft為為Binary_node類型的指針。類型的指針。nLeft指向的是指向的是Binary_node的對象時，調(diào)用的是父類中的對象時，調(diào)用的是父類中get_b

13、alance()方法的實現(xiàn)。方法的實現(xiàn)。nLeft指向的是指向的是AVL_node的對象時，調(diào)用的是的對象時，調(diào)用的是AVL_node中中get_balance()方法的實現(xiàn)。方法的實現(xiàn)。nget_balance( )為虛函數(shù)，支持動態(tài)綁定。為虛函數(shù)，支持動態(tài)綁定。11/23/2021數(shù)據(jù)結構與程序設計 16Height Balance: AVL Trees 定義定義#include Search_tree.cpptemplate class AVL_tree: public Search_tree public:Error_code insert(const Record &new_

14、data);Error_code remove(Record &old_data);11/23/2021數(shù)據(jù)結構與程序設計 17Height Balance: AVL Trees 定義定義private: / Add auxiliary function prototypes here.Error_code avl_insert(Binary_node * &sub_root, const Record &new_data, bool &taller);void rotate_left(Binary_node * &sub_root);void rota

15、te_right(Binary_node * &sub_root);void right_balance(Binary_node * &sub_root);void left_balance(Binary_node * &sub_root);/add for removeError_code avl_remove(Binary_node * &sub_root, Record &new_data, bool &shorter);bool right_balance2(Binary_node * &sub_root);bool left_b

16、alance2(Binary_node * &sub_root);11/23/2021數(shù)據(jù)結構與程序設計 1810.4.2 Insertions into an AVL tree11/23/2021數(shù)據(jù)結構與程序設計 1910.4.2 AVL樹插入的方法n向AVL樹中插入新節(jié)點的方法與二分查找樹插入新節(jié)點的方法基本相同：n 首先按照二分查找樹構建的方法，向AVL樹中插入新節(jié)點。（10.2.3 P452）n在新節(jié)點插入之后，從樹葉向根部依次分析樹的平衡因子是否被破壞了，如果被破壞則需要立即按照一定的方法重新調(diào)整樹的結構。11/23/2021數(shù)據(jù)結構與程序設計 20Insertions i

17、nto an AVL tree如圖所示，在插入新節(jié)點如圖所示，在插入新節(jié)點u之后，之后，K的平衡因子被破壞，此的平衡因子被破壞，此時需要進行調(diào)整。左旋，具體的旋轉方法在后面介紹。時需要進行調(diào)整。左旋，具體的旋轉方法在后面介紹。問題：怎么樣判斷節(jié)點的平衡因子是否被破壞？問題：怎么樣判斷節(jié)點的平衡因子是否被破壞？11/23/2021數(shù)據(jù)結構與程序設計 21Insertions into an AVL treen問題：怎么樣判斷節(jié)點問題：怎么樣判斷節(jié)點n的平衡因子是否被破的平衡因子是否被破壞？壞？n方法：先判斷在節(jié)點方法：先判斷在節(jié)點n的左子樹還是右子樹有插入的左子樹還是右子樹有插入操作且該子樹的高

18、度是否改變（即高度增加操作且該子樹的高度是否改變（即高度增加1）。）。n如果左子樹有插入操作，且高度改變?nèi)绻笞訕溆胁迦氩僮?，且高度改變n如果節(jié)點的平衡因子為如果節(jié)點的平衡因子為 - 變?yōu)樽優(yōu)?/ 。n如果節(jié)點的平衡因子為如果節(jié)點的平衡因子為 /,變?yōu)樽優(yōu)?/，且需要調(diào)整。，且需要調(diào)整。n如果節(jié)點的平衡因子為如果節(jié)點的平衡因子為, 變?yōu)樽優(yōu)? 。n如果右子樹有插入操作，且高度有改變?nèi)绻易訕溆胁迦氩僮?，且高度有改變n如果節(jié)點的平衡因子為如果節(jié)點的平衡因子為 - 變?yōu)樽優(yōu)?。n如果節(jié)點的平衡因子為如果節(jié)點的平衡因子為 ,變?yōu)樽優(yōu)?，且需要調(diào)整。，且需要調(diào)整。n如果節(jié)點的平衡因子為如果節(jié)點的平衡因

19、子為/, 變?yōu)樽優(yōu)? 。11/23/2021數(shù)據(jù)結構與程序設計 22Insertions into an AVL tree插入節(jié)點插入節(jié)點P時，時，m的平衡因子被破壞，現(xiàn)在需要調(diào)整結構。的平衡因子被破壞，現(xiàn)在需要調(diào)整結構。11/23/2021數(shù)據(jù)結構與程序設計 23AVL Trees 插入操作插入操作template Error_code AVL_tree : insert(const Record &new_data)/* Post: If the key of new data is already in the AVL tree , a code of duplicate_err

20、or is returned. Otherwise, a code of success is returned and the Record new data is inserted into the tree in such a way that the properties of an AVL tree are preserved.Uses: avl_insert . */bool taller; / Has the tree grown in height?return avl_insert(root, new_data, taller); /向向root中插入一個新節(jié)點中插入一個新節(jié)

21、點new_data. /taller表示插入是否使得以表示插入是否使得以root為根的樹高度增加。為根的樹高度增加。11/23/2021數(shù)據(jù)結構與程序設計 24template Error_code AVL_tree : avl_insert(Binary_node * &sub_root, const Record &new_data, bool &taller)Error_code result = success;if (sub_root = NULL) sub_root = new AVL_node(new_data);taller = true; else i

22、f (new_data = sub_root-data) result = duplicate_error;taller = false; 11/23/2021數(shù)據(jù)結構與程序設計 25else if (new_data data) / Insert in left subtree.result = avl_insert(sub_root-left, new_data, taller); if (taller = true)switch (sub_root-get_balance( ) / Change balance factors.case left_higher:left_balance(

23、sub_root);taller = false; / Rebalancing always shortens the tree.break;case equal_height:sub_root-set_balance(left_higher);break;case right_higher:sub_root-set_balance(equal_height);taller = false;break; 11/23/2021數(shù)據(jù)結構與程序設計 26在在Subroot的左子樹插入節(jié)點后的情況的左子樹插入節(jié)點后的情況分析：分析：h+1hcase left_higherleft_balance(su

24、b_root)hhcase equal_heighttaller = truehcase right_higherh+1sub_root11/23/2021數(shù)據(jù)結構與程序設計 27else / Insert in right subtree.result = avl_insert(sub_root-right, new_data, taller);if (taller = true)switch (sub_root-get_balance( ) case left_higher:sub_root-set_balance(equal_height);taller = false;break;ca

25、se equal_height:sub_root-set_balance(right_higher);break;case right_higher:right_balance(sub_root);taller = false; / Rebalancing always shortens the tree.break; return result; 11/23/2021數(shù)據(jù)結構與程序設計 28h+1hcase left_higherhhcase equal_heighttaller = truehcase right_higherright_balance(sub_root);h+1sub_r

26、oot在在Subroot的右子樹插入節(jié)點后的右子樹插入節(jié)點后的情況分析：的情況分析：11/23/2021數(shù)據(jù)結構與程序設計 29P480 2 Rotations 旋轉操作旋轉操作n如果節(jié)點的平衡因子被破壞，用什么方法調(diào)整平衡。n方法：需要根據(jù)破壞平衡的原因來調(diào)整。n破壞平衡的原因有四種：nRR型，RL型，LL型，LR型。n其中RR與LL雷同，RL與LR雷同。n下面重點介紹RR型的調(diào)整和RL型的調(diào)整。11/23/2021數(shù)據(jù)結構與程序設計 30P480 2 Rotations 旋轉操作旋轉操作11/23/2021數(shù)據(jù)結構與程序設計 31第一種情況：第一種情況：case right_higher:

27、11/23/2021數(shù)據(jù)結構與程序設計 32AVL Trees 左旋操作左旋操作template void AVL_tree : rotate_left(Binary_node * &sub_root)/* Pre: sub_root points to a subtree of the AVL tree . This subtree has a nonempty right subtree.Post: sub_root is reset to point to its former right child, and the former sub_root node is the le

28、ft child of the new sub_root node. */if (sub_root = NULL | sub_root-right = NULL) / impossible casescout WARNING: program error detected in rotate left endl;else Binary_node *right_tree = sub_root-right;sub_root-right = right_tree-left;right_tree-left = sub_root;sub_root = right_tree; 11/23/2021數(shù)據(jù)結構

29、與程序設計 33第二種情況：第二種情況：case left_higher:11/23/2021數(shù)據(jù)結構與程序設計 34template void AVL_tree : rotate_right(Binary_node * &sub_root)/* Pre: sub_root points to a subtree of the AVL tree . This subtree has a nonemptyleft subtree.Post: sub_root is reset to point to its former left child, and the former sub_ro

30、otnode is the right child of the new sub_root node. */if (sub_root = NULL | sub_root-left = NULL) / impossible casescout WARNING: program error detected in rotate right endl;else Binary_node *left_tree = sub_root-left;sub_root-left = left_tree-right;left_tree-right = sub_root;sub_root = left_tree; A

31、VL Trees 右旋操作右旋操作11/23/2021數(shù)據(jù)結構與程序設計 35當右子樹過高于左子樹當右子樹過高于左子樹2層時的調(diào)整層時的調(diào)整template void AVL_tree : right_balance(Binary_node * &sub_root)/* Pre: sub root points to a subtree of an AVL tree , doubly unbalanced on the right.Post: The AVL properties have been restored to the subtree.Uses: Methods of st

32、ruct AVL node ; functions rotate_right ,rotate_left . */Binary_node * &right_tree = sub_root-right;switch (right_tree-get_balance( ) case right_higher: / single rotation leftsub_root-set_balance(equal_height);right_tree-set_balance(equal_height);rotate_left(sub_root); break;case equal_height: /

33、impossible case because taller = truecout WARNING: program error in right balance endl;11/23/2021數(shù)據(jù)結構與程序設計 36case left_higher: / double rotation leftBinary_node *sub_tree = right_tree-left;switch (sub_tree-get_balance( ) case equal_height:sub_root-set_balance(equal_height);right_tree-set_balance(equ

34、al_height); break;case left_higher: /T2 is h, T3 is h-1sub_root-set_balance(equal_height);right_tree-set_balance(right_higher); break;case right_higher: /T2 is h-1, T3 is hsub_root-set_balance(left_higher);right_tree-set_balance(equal_height); break; sub_tree-set_balance(equal_height);rotate_right(r

35、ight_tree);rotate_left(sub_root); break; 11/23/2021數(shù)據(jù)結構與程序設計 37case left_higher:11/23/2021數(shù)據(jù)結構與程序設計 38template void AVL_tree : left_balance(Binary_node * &sub_root)/* Pre: sub root points to a subtree of an AVL tree , doubly unbalanced on the left.Post: The AVL properties have been restored to t

36、he subtree.Uses: Methods of struct AVL node ; functions rotate_right ,rotate_left . */Binary_node * &left_tree = sub_root-left;switch (left_tree-get_balance( ) case left_higher: / single rotation leftsub_root-set_balance(equal_height);left_tree-set_balance(equal_height);rotate_right(sub_root); b

37、reak;case equal_height: / impossible casecout WARNING: program error in right balance endl;當左子樹過高于右子樹當左子樹過高于右子樹2層時的調(diào)整層時的調(diào)整11/23/2021數(shù)據(jù)結構與程序設計 39case right_higher: / double rotation leftBinary_node *sub_tree = left_tree-right;switch (sub_tree-get_balance( ) case equal_height:sub_root-set_balance(equa

38、l_height);left_tree-set_balance(equal_height); break;case right_higher:sub_root-set_balance(equal_height);left_tree-set_balance(left_higher); break;case left_higher:sub_root-set_balance(right_higher);left_tree-set_balance(equal_height); break; sub_tree-set_balance(equal_height);rotate_left(left_tree

39、);rotate_right(sub_root); break; 11/23/2021數(shù)據(jù)結構與程序設計 40Insertions into an AVL tree插入節(jié)點插入節(jié)點P時，時，m的平衡因子被破壞，現(xiàn)在需要調(diào)整結構。的平衡因子被破壞，現(xiàn)在需要調(diào)整結構。11/23/2021數(shù)據(jù)結構與程序設計 41AVL Trees-Mainvoid main()AVL_tree mytree;for(int i=1;i10;i+)mytree.insert(Record(i);coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:

40、endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendlendl;11/23/2021數(shù)據(jù)結構與程序設計 42AVL Trees-Main1122312314Rotate_left11/23/2021數(shù)據(jù)結構與程序設計 43AVL Trees-Main24153452631Rotate_leftRotate_left11/23/2021數(shù)據(jù)結構與程序設計 44AVL Trees-Main462731546273158Rotate_left11/23/2021數(shù)據(jù)結構與程序設計

41、45AVL Trees-Main462831597Rotate_left11/23/2021數(shù)據(jù)結構與程序設計 46AVL Trees-MainAVL_tree mytree2;for(i=9;i0;i-)mytree2.insert(Record(i);coutPreorder:endl;mytree2.preorder(print);coutendl;coutinorder:endl;mytree2.inorder(print);coutendl;coutPostorder:endl;mytree2.postorder(print);coutendlendl;cin.get();11/23

42、/2021數(shù)據(jù)結構與程序設計 47AVL Trees-Main9988978976Rotate_right11/23/2021數(shù)據(jù)結構與程序設計 48AVL Trees-Main89675685974Rotate_rightRotate_right11/23/2021數(shù)據(jù)結構與程序設計 49AVL Trees-Main684953768495372Rotate_right11/23/2021數(shù)據(jù)結構與程序設計 50AVL Trees-Main684952731Rotate_right11/23/2021數(shù)據(jù)結構與程序設計 5110.4.3 AVL的刪除操作n向AVL樹中刪除節(jié)點的方法與二分查找

43、樹刪除節(jié)點的方法基本相同：n 首先按照二分查找樹刪除的方法，找到刪除的節(jié)點。n在節(jié)點刪除之后，從刪除點所在的位置向根部依次分析樹的平衡因子是否被破壞了，如果被破壞則需要立即按照一定的方法重新調(diào)整樹的結構。（調(diào)整方法與插入操作相同）11/23/2021數(shù)據(jù)結構與程序設計 52平衡因子的分析（1）11/23/2021數(shù)據(jù)結構與程序設計 53平衡因子的分析（2）11/23/2021數(shù)據(jù)結構與程序設計 54平衡因子的分析（3）11/23/2021數(shù)據(jù)結構與程序設計 55Example：Remove P487刪除P以后的結果是？11/23/2021數(shù)據(jù)結構與程序設計 56Example：Remove P

44、487第一步：調(diào)整節(jié)點第一步：調(diào)整節(jié)點o11/23/2021數(shù)據(jù)結構與程序設計 57Example：Remove P487第二步：調(diào)整節(jié)點第二步：調(diào)整節(jié)點m， LR型的結構，需要先左旋，再右旋型的結構，需要先左旋，再右旋11/23/2021數(shù)據(jù)結構與程序設計 58Example：Remove P48711/23/2021數(shù)據(jù)結構與程序設計 59Remove（.）template Error_code AVL_tree : remove(Record &new_data)/* Post: If the key of new data is not in the AVL tree , a

45、code of not_present is returned. Otherwise, a code of success is returned and the Record new data is removed from the tree in such a way that the properties of an AVL tree are preserved.Uses: avl_remove . */bool shorter=true; / Has the tree shorter in height?return avl_remove(root, new_data, shorter

46、);11/23/2021數(shù)據(jù)結構與程序設計 60avl_remove(.)template Error_code AVL_tree : avl_remove(Binary_node * &sub_root, Record &new_data, bool &shorter)Error_code result = success; Record sub_record;if (sub_root = NULL) shorter = false;return not_present; 11/23/2021數(shù)據(jù)結構與程序設計 61else if (new_data = sub_ro

47、ot-data) /刪除節(jié)點，操作與二分查找樹相同刪除節(jié)點，操作與二分查找樹相同Binary_node *to_delete = sub_root;/ Remember node to delete at end.if (sub_root-right = NULL) /右子樹為空右子樹為空sub_root = sub_root-left;shorter = true;delete to_delete; / Remove to_delete from tree.return success;else if (sub_root-left = NULL) /左子樹為空左子樹為空sub_root =

48、sub_root-right;shorter = true;delete to_delete; / Remove to_delete from tree.return success;11/23/2021數(shù)據(jù)結構與程序設計 62else /左右子樹都不為空左右子樹都不為空 / Neither subtree is empty.to_delete = sub_root-left; / Move left to find predecessor.Binary_node *parent = sub_root; / parent of to_deletewhile (to_delete-right !

49、= NULL) / to_delete is not the predecessor.parent = to_delete;to_delete = to_delete-right; /sub_root-data = to_delete-data; / Move data from to_delete to root. new_data = to_delete-data;sub_record = new_data; /記錄刪除的數(shù)據(jù)值記錄刪除的數(shù)據(jù)值 /else分支，完成刪除任務的替換。分支，完成刪除任務的替換。 /在刪除點在刪除點x的左右子樹都存在時，此時刪除的是前驅(qū)點的左右子樹都存在時，此時

50、刪除的是前驅(qū)點w。11/23/2021數(shù)據(jù)結構與程序設計 63if (new_data data) / remove in left subtree.result = avl_remove(sub_root-left, new_data, shorter);if(sub_record.the_key()!=0)sub_root-data = sub_record; / Move data from to_delete to root. if (shorter = true)switch (sub_root-get_balance( ) / Change balance factors.case

51、 left_higher:sub_root-set_balance(equal_height);break;case equal_height:sub_root-set_balance(right_higher);shorter = false;break;case right_higher:shorter = right_balance2(sub_root);break; 11/23/2021數(shù)據(jù)結構與程序設計 64if (new_data sub_root-data) / remove in right subtree.result = avl_remove(sub_root-right,

52、 new_data, shorter);if(sub_record.the_key()!=0)sub_root-data = sub_record; / Move data from to_delete to root. if (shorter = true)switch (sub_root-get_balance( ) / Change balance factors.case left_higher:shorter = left_balance2(sub_root);break;case equal_height:sub_root-set_balance(left_higher);shor

53、ter = false;break;case right_higher:sub_root-set_balance(equal_height);break; return result; 11/23/2021數(shù)據(jù)結構與程序設計 65 right_balance2template bool AVL_tree : right_balance2(Binary_node * &sub_root)/* Pre: sub root points to a subtree of an AVL tree , doubly unbalanced on the right.Post: The AVL pro

54、perties have been restored to the subtree.Uses: Methods of struct AVL node ; functions rotate_right ,rotate_left . */bool shorter;Binary_node * &right_tree = sub_root-right;switch (right_tree-get_balance( ) case right_higher: / single rotation leftsub_root-set_balance(equal_height);right_tree-se

55、t_balance(equal_height);rotate_left(sub_root); shorter = true;break;11/23/2021數(shù)據(jù)結構與程序設計 66case equal_height: / single rotation left R-型，左轉后高度不變型，左轉后高度不變right_tree-set_balance(left_higher);rotate_left(sub_root); shorter = false;break; right_balance211/23/2021數(shù)據(jù)結構與程序設計 67case left_higher: / double rot

56、ation leftBinary_node *sub_tree = right_tree-left;switch (sub_tree-get_balance( ) case equal_height:sub_root-set_balance(equal_height);right_tree-set_balance(equal_height); break;case left_higher:sub_root-set_balance(equal_height);right_tree-set_balance(right_higher); break; right_balance211/23/2021數(shù)據(jù)結構與程序設計 68case right_higher:sub_root-set_balance(left_higher);right_tree-set_balance(equal_height); break; sub_tree-set_balance(equal_height);rotate_right(right_tree);rotate_left(sub_root); shorter = true;break; return shorter; right_balance211/23/2021數(shù)據(jù)