数据结构与程序设计(27)AVL Tree

1、11/23/2021数据结构与程序设计 110.4 Height Balance: AVL Treesn10.3 节创建的二叉查找树左右子树高度不能节创建的二叉查找树左右子树高度不能保证总是近似平衡。例如保证总是近似平衡。例如8个节点时，个节点时，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数据结构与程序设计 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数据结构与程序设计 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数据结构与程序设计 4Height Balance: AVL Trees11/23/2021数据结构与程序设计 5Height Balance: AVL Trees11/23/2021数据结构与

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数据结构与程序设计 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数据结构与程序设计 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数据结构与程序设计 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); /此处发生动态绑定，调用的是此处发生动态绑定，调用的是子类子类AVL_Node中中setBanlance方法的实现。方法的实现。11/23/2021数据结构与程序设计 10AVL Trees Node实现实现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数据结构与程序设计 11AVL Trees Node实现实现template void AVL_node : set_balance(Balance_factor b)balance = b;template Balance_factor AVL_node : get_balance( ) constreturn balance;11/23/2021数据结构与程序设计 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数据结构与程序设计 13Binary Tree Node 实现实现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数据结构与程序设计 14Binary Tree Node 实现实现template void Binary_node : set_balance(Balance_factor b)template Balance_

12、factor Binary_node : get_balance( ) constreturn equal_height;11/23/2021数据结构与程序设计 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的对象时，调用的是父类中的对象时，调用的是父类中get_b

13、alance()方法的实现。方法的实现。nLeft指向的是指向的是AVL_node的对象时，调用的是的对象时，调用的是AVL_node中中get_balance()方法的实现。方法的实现。nget_balance( )为虚函数，支持动态绑定。为虚函数，支持动态绑定。11/23/2021数据结构与程序设计 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数据结构与程序设计 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数据结构与程序设计 1810.4.2 Insertions into an AVL tree11/23/2021数据结构与程序设计 1910.4.2 AVL树插入的方法n向AVL树中插入新节点的方法与二分查找树插入新节点的方法基本相同：n 首先按照二分查找树构建的方法，向AVL树中插入新节点。（10.2.3 P452）n在新节点插入之后，从树叶向根部依次分析树的平衡因子是否被破坏了，如果被破坏则需要立即按照一定的方法重新调整树的结构。11/23/2021数据结构与程序设计 20Insertions i

17、nto an AVL tree如图所示，在插入新节点如图所示，在插入新节点u之后，之后，K的平衡因子被破坏，此的平衡因子被破坏，此时需要进行调整。左旋，具体的旋转方法在后面介绍。时需要进行调整。左旋，具体的旋转方法在后面介绍。问题：怎么样判断节点的平衡因子是否被破坏？问题：怎么样判断节点的平衡因子是否被破坏？11/23/2021数据结构与程序设计 21Insertions into an AVL treen问题：怎么样判断节点问题：怎么样判断节点n的平衡因子是否被破的平衡因子是否被破坏？坏？n方法：先判断在节点方法：先判断在节点n的左子树还是右子树有插入的左子树还是右子树有插入操作且该子树的高

18、度是否改变（即高度增加操作且该子树的高度是否改变（即高度增加1）。）。n如果左子树有插入操作，且高度改变如果左子树有插入操作，且高度改变n如果节点的平衡因子为如果节点的平衡因子为 - 变为变为 / 。n如果节点的平衡因子为如果节点的平衡因子为 /,变为变为 /，且需要调整。，且需要调整。n如果节点的平衡因子为如果节点的平衡因子为, 变为变为- 。n如果右子树有插入操作，且高度有改变如果右子树有插入操作，且高度有改变n如果节点的平衡因子为如果节点的平衡因子为 - 变为变为 。n如果节点的平衡因子为如果节点的平衡因子为 ,变为变为 ，且需要调整。，且需要调整。n如果节点的平衡因子为如果节点的平衡因

19、子为/, 变为变为- 。11/23/2021数据结构与程序设计 22Insertions into an AVL tree插入节点插入节点P时，时，m的平衡因子被破坏，现在需要调整结构。的平衡因子被破坏，现在需要调整结构。11/23/2021数据结构与程序设计 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中插入一个新节点中插入一个新节

21、点new_data. /taller表示插入是否使得以表示插入是否使得以root为根的树高度增加。为根的树高度增加。11/23/2021数据结构与程序设计 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数据结构与程序设计 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数据结构与程序设计 26在在Subroot的左子树插入节点后的情况的左子树插入节点后的情况分析：分析：h+1hcase left_higherleft_balance(su

24、b_root)hhcase equal_heighttaller = truehcase right_higherh+1sub_root11/23/2021数据结构与程序设计 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数据结构与程序设计 28h+1hcase left_higherhhcase equal_heighttaller = truehcase right_higherright_balance(sub_root);h+1sub_r

26、oot在在Subroot的右子树插入节点后的右子树插入节点后的情况分析：的情况分析：11/23/2021数据结构与程序设计 29P480 2 Rotations 旋转操作旋转操作n如果节点的平衡因子被破坏，用什么方法调整平衡。n方法：需要根据破坏平衡的原因来调整。n破坏平衡的原因有四种：nRR型，RL型，LL型，LR型。n其中RR与LL雷同，RL与LR雷同。n下面重点介绍RR型的调整和RL型的调整。11/23/2021数据结构与程序设计 30P480 2 Rotations 旋转操作旋转操作11/23/2021数据结构与程序设计 31第一种情况：第一种情况：case right_higher:

27、11/23/2021数据结构与程序设计 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数据结构

29、与程序设计 33第二种情况：第二种情况：case left_higher:11/23/2021数据结构与程序设计 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数据结构与程序设计 35当右子树过高于左子树当右子树过高于左子树2层时的调整层时的调整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数据结构与程序设计 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数据结构与程序设计 37case left_higher:11/23/2021数据结构与程序设计 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层时的调整层时的调整11/23/2021数据结构与程序设计 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数据结构与程序设计 40Insertions into an AVL tree插入节点插入节点P时，时，m的平衡因子被破坏，现在需要调整结构。的平衡因子被破坏，现在需要调整结构。11/23/2021数据结构与程序设计 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数据结构与程序设计 42AVL Trees-Main1122312314Rotate_left11/23/2021数据结构与程序设计 43AVL Trees-Main24153452631Rotate_leftRotate_left11/23/2021数据结构与程序设计 44AVL Trees-Main462731546273158Rotate_left11/23/2021数据结构与程序设计

41、45AVL Trees-Main462831597Rotate_left11/23/2021数据结构与程序设计 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数据结构与程序设计 47AVL Trees-Main9988978976Rotate_right11/23/2021数据结构与程序设计 48AVL Trees-Main89675685974Rotate_rightRotate_right11/23/2021数据结构与程序设计 49AVL Trees-Main684953768495372Rotate_right11/23/2021数据结构与程序设计 50AVL Trees-Main684952731Rotate_right11/23/2021数据结构与程序设计 5110.4.3 AVL的删除操作n向AVL树中删除节点的方法与二分查找

43、树删除节点的方法基本相同：n 首先按照二分查找树删除的方法，找到删除的节点。n在节点删除之后，从删除点所在的位置向根部依次分析树的平衡因子是否被破坏了，如果被破坏则需要立即按照一定的方法重新调整树的结构。（调整方法与插入操作相同）11/23/2021数据结构与程序设计 52平衡因子的分析（1）11/23/2021数据结构与程序设计 53平衡因子的分析（2）11/23/2021数据结构与程序设计 54平衡因子的分析（3）11/23/2021数据结构与程序设计 55Example：Remove P487删除P以后的结果是？11/23/2021数据结构与程序设计 56Example：Remove P

44、487第一步：调整节点第一步：调整节点o11/23/2021数据结构与程序设计 57Example：Remove P487第二步：调整节点第二步：调整节点m， LR型的结构，需要先左旋，再右旋型的结构，需要先左旋，再右旋11/23/2021数据结构与程序设计 58Example：Remove P48711/23/2021数据结构与程序设计 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数据结构与程序设计 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数据结构与程序设计 61else if (new_data = sub_ro

47、ot-data) /删除节点，操作与二分查找树相同删除节点，操作与二分查找树相同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数据结构与程序设计 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; /记录删除的数据值记录删除的数据值 /else分支，完成删除任务的替换。分支，完成删除任务的替换。 /在删除点在删除点x的左右子树都存在时，此时删除的是前驱点的左右子树都存在时，此时

50、删除的是前驱点w。11/23/2021数据结构与程序设计 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数据结构与程序设计 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数据结构与程序设计 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数据结构与程序设计 66case equal_height: / single rotation left R-型，左转后高度不变型，左转后高度不变right_tree-set_balance(left_higher);rotate_left(sub_root); shorter = false;break; right_balance211/23/2021数据结构与程序设计 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数据结构与程序设计 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数据