數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(27)AVL Tree

1、11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 4Height Balance: AVL Trees11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 5Height Balance: AVL Trees11/23/2021數(shù)據(jù)結(jié)構(gòu)與

4、程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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)用的是父類中g(shù)et_b

13、alance()方法的實現(xiàn)。方法的實現(xiàn)。nLeft指向的是指向的是AVL_node的對象時，調(diào)用的是的對象時，調(diào)用的是AVL_node中中g(shù)et_balance()方法的實現(xiàn)。方法的實現(xiàn)。nget_balance( )為虛函數(shù)，支持動態(tài)綁定。為虛函數(shù)，支持動態(tài)綁定。11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 1810.4.2 Insertions into an AVL tree11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 1910.4.2 AVL樹插入的方法n向AVL樹中插入新節(jié)點的方法與二分查找樹插入新節(jié)點的方法基本相同：n 首先按照二分查找樹構(gòu)建的方法，向AVL樹中插入新節(jié)點。（10.2.3 P452）n在新節(jié)點插入之后，從樹葉向根部依次分析樹的平衡因子是否被破壞了，如果被破壞則需要立即按照一定的方法重新調(diào)整樹的結(jié)構(gòu)。11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 20Insertions i

17、nto an AVL tree如圖所示，在插入新節(jié)點如圖所示，在插入新節(jié)點u之后，之后，K的平衡因子被破壞，此的平衡因子被破壞，此時需要進行調(diào)整。左旋，具體的旋轉(zhuǎn)方法在后面介紹。時需要進行調(diào)整。左旋，具體的旋轉(zhuǎn)方法在后面介紹。問題：怎么樣判斷節(jié)點的平衡因子是否被破壞？問題：怎么樣判斷節(jié)點的平衡因子是否被破壞？11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 22Insertions into an AVL tree插入節(jié)點插入節(jié)點P時，時，m的平衡因子被破壞，現(xiàn)在需要調(diào)整結(jié)構(gòu)。的平衡因子被破壞，現(xiàn)在需要調(diào)整結(jié)構(gòu)。11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 29P480 2 Rotations 旋轉(zhuǎn)操作旋轉(zhuǎn)操作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ù)結(jié)構(gòu)與程序設(shè)計 30P480 2 Rotations 旋轉(zhuǎn)操作旋轉(zhuǎn)操作11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 31第一種情況：第一種情況：case right_higher:

27、11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)

29、與程序設(shè)計 33第二種情況：第二種情況：case left_higher:11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 35當(dāng)右子樹過高于左子樹當(dāng)右子樹過高于左子樹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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 37case left_higher:11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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;當(dāng)左子樹過高于右子樹當(dāng)左子樹過高于右子樹2層時的調(diào)整層時的調(diào)整11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 40Insertions into an AVL tree插入節(jié)點插入節(jié)點P時，時，m的平衡因子被破壞，現(xiàn)在需要調(diào)整結(jié)構(gòu)。的平衡因子被破壞，現(xiàn)在需要調(diào)整結(jié)構(gòu)。11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 42AVL Trees-Main1122312314Rotate_left11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 43AVL Trees-Main24153452631Rotate_leftRotate_left11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 44AVL Trees-Main462731546273158Rotate_left11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計

41、45AVL Trees-Main462831597Rotate_left11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 47AVL Trees-Main9988978976Rotate_right11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 48AVL Trees-Main89675685974Rotate_rightRotate_right11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 49AVL Trees-Main684953768495372Rotate_right11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 50AVL Trees-Main684952731Rotate_right11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 5110.4.3 AVL的刪除操作n向AVL樹中刪除節(jié)點的方法與二分查找

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

44、487第一步：調(diào)整節(jié)點第一步：調(diào)整節(jié)點o11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 57Example：Remove P487第二步：調(diào)整節(jié)點第二步：調(diào)整節(jié)點m， LR型的結(jié)構(gòu)，需要先左旋，再右旋型的結(jié)構(gòu)，需要先左旋，再右旋11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 58Example：Remove P48711/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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分支，完成刪除任務(wù)的替換。分支，完成刪除任務(wù)的替換。 /在刪除點在刪除點x的左右子樹都存在時，此時刪除的是前驅(qū)點的左右子樹都存在時，此時

50、刪除的是前驅(qū)點w。11/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 66case equal_height: / single rotation left R-型，左轉(zhuǎn)后高度不變型，左轉(zhuǎn)后高度不變right_tree-set_balance(left_higher);rotate_left(sub_root); shorter = false;break; right_balance211/23/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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ù)結(jié)構(gòu)與程序設(shè)計 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ù)