数据结构与程序设计(27).ppt

《数据结构与程序设计(27).ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计(27).ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与程序设计(27)教师：鲍钰12/28/20221数据结构与程序设计 教师：鲍钰Height Balance:AVL TreesnDefinition: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 left and right subtrees are again AVL trees.12/28/20222数据结构与程序设计 教师：鲍钰Height Balan

2、ce: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 the right subtree.12/28/20223数据结构与程序设计 教师：鲍钰Height Balance:AVL TreesnIn drawing diagram

3、s,we shall show a left-higher node by/,a node whose balance factor is equal by,and a right-higher node by.12/28/20224数据结构与程序设计 教师：鲍钰Height Balance:AVL Trees12/28/20225数据结构与程序设计 教师：鲍钰Height Balance:AVL Trees12/28/20226数据结构与程序设计 教师：鲍钰Height Balance:AVL Trees12/28/20227数据结构与程序设计 教师：鲍钰Height Balance:AVL

4、 TreesnWe employ an enumerated data type to record balance factors:enum Balance_factor left_higher,equal_height,right_higher;nAVL nodes are structures derived from binary search tree nodes with balance factors included.12/28/20228数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesn#include Binary_node.cppntempl

5、ate nstruct AVL_node:public Binary_node n/additional data member:nBalance_factor balance;n/constructors:nAVL_node();nAVL_node(const Record&x);n/overridden virtual functions:nvoid set_balance(Balance_factor b);nBalance_factor get_balance()const;n;12/28/20229数据结构与程序设计 教师：鲍钰Height Balance:AVL TreesnAVL

6、_node:AVL_node()nleft=NULL;nright=NULL;nbalance=equal_height;nntemplate nAVL_node:AVL_node(const Record&x)ndata=x;nleft=NULL;nright=NULL;nbalance=equal_height;n12/28/202210数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nvoid AVL_node:set_balance(Balance_factor b)nnbalance=b;nntemplate nBalance_fac

7、tor AVL_node:get_balance()constnnreturn balance;n12/28/202211数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesnenum Balance_factor left_higher,equal_height,right_higher;ntemplate nstruct Binary_node n/data members:nEntry data;nBinary_node*left;nBinary_node*right;n/constructors:nBinary_node();nBinary_node(cons

8、t Entry&x);n/virtual methods:nvirtual void set_balance(Balance_factor b);nvirtual Balance_factor get_balance()const;n;12/28/202212数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nBinary_node:Binary_node()nleft=NULL;nright=NULL;nntemplate nBinary_node:Binary_node(const Entry&x)ndata=x;nleft=NULL;nri

9、ght=NULL;n12/28/202213数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nvoid Binary_node:set_balance(Balance_factor b)nnntemplate nBalance_factor Binary_node:get_balance()constnnreturn equal_height;n12/28/202214数据结构与程序设计 教师：鲍钰Height Balance:AVL TreesnWe often invoke these methods(set_balance,get_bal

10、ance)through pointers to nodes,such as left-get_balance().But left could(for the compiler)point to any Binary_node,not just to an AVL_node,and these methods are declared only for AVL node.nWe therefore declare the Binary_node versions of set_balance and get_balance as virtual methods,selected at run

11、 time.12/28/202215数据结构与程序设计 教师：鲍钰Insertions into an AVL tree12/28/202216数据结构与程序设计 教师：鲍钰Insertions into an AVL tree12/28/202217数据结构与程序设计 教师：鲍钰Insertions into an AVL tree12/28/202218数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesn#include Search_tree.cppntemplate nclass AVL_tree:public Search_tree npublic:nEr

12、ror_code insert(const Record&new_data);nError_code remove(Record&old_data);12/28/202219数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesnprivate:/Add auxiliary function prototypes here.nError_code avl_insert(Binary_node*&sub_root,const Record&new_data,bool&taller);nvoid rotate_left(Binary_node*&sub_root);nvoi

13、d rotate_right(Binary_node*&sub_root);nvoid right_balance(Binary_node*&sub_root);nvoid left_balance(Binary_node*&sub_root);n/add for removenError_code avl_remove(Binary_node*&sub_root,Record&new_data,bool&shorter);nbool right_balance2(Binary_node*&sub_root);nbool left_balance2(Binary_node*&sub_root)

14、;n;12/28/202220数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nError_code AVL_tree:insert(const Record&new_data)n/*Post:If the key of new data is already in the AVL tree,a code of duplicate_error is returned.Otherwise,a code of success is returned and the Record new data is inserted into the tree

15、in such a way that the properties of an AVL tree are preserved.nUses:avl_insert.*/nnbool taller;/Has the tree grown in height?nreturn avl_insert(root,new_data,taller);n12/28/202221数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nError_code AVL_tree:avl_insert(Binary_node*&sub_root,nconst Record&new

16、_data,bool&taller)nnError_code result=success;nif(sub_root=NULL)nsub_root=new AVL_node(new_data);ntaller=true;n nelse if(new_data=sub_root-data)nresult=duplicate_error;ntaller=false;n 12/28/202222数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesnelse if(new_data data)/Insert in left subtree.nresult=avl_insert

17、(sub_root-left,new_data,taller);nif(taller=true)nswitch(sub_root-get_balance()/Change balance factors.ncase left_higher:nleft_balance(sub_root);ntaller=false;/Rebalancing always shortens the tree.nbreak;ncase equal_height:nsub_root-set_balance(left_higher);nbreak;ncase right_higher:nsub_root-set_bal

18、ance(equal_height);ntaller=false;nbreak;n n 12/28/202223数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesh+1hcase left_higherleft_balance(sub_root)hhcase equal_heighttaller=truehcase right_higherh+1sub_root12/28/202224数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesnelse /Insert in right subtree.nresult=avl_insert(sub

19、_root-right,new_data,taller);nif(taller=true)nswitch(sub_root-get_balance()ncase left_higher:nsub_root-set_balance(equal_height);ntaller=false;nbreak;ncase equal_height:nsub_root-set_balance(right_higher);nbreak;ncase right_higher:nright_balance(sub_root);ntaller=false;/Rebalancing always shortens t

20、he tree.nbreak;n n nreturn result;n 12/28/202225数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesh+1hcase left_higherhhcase equal_heighttaller=truehcase right_higherright_balance(sub_root);h+1sub_root12/28/202226数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nvoid AVL_tree:rotate_left(Binary_node*&sub_root)

21、n/*Pre:sub_root points to a subtree of the AVL tree.This subtree has a nonemptynright subtree.nPost:sub_root is reset to point to its former right child,and the former sub_rootnnode is the left child of the new sub_root node.*/nnif(sub_root=NULL|sub_root-right=NULL)/impossible casesncout WARNING:pro

22、gram error detected in rotate left endl;nelse nBinary_node*right_tree=sub_root-right;nsub_root-right=right_tree-left;nright_tree-left=sub_root;nsub_root=right_tree;n n12/28/202227数据结构与程序设计 教师：鲍钰12/28/202228数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nvoid AVL_tree:rotate_right(Binary_node*&sub_

23、root)n/*Pre:sub_root points to a subtree of the AVL tree.This subtree has a nonemptynleft subtree.nPost:sub_root is reset to point to its former left child,and the former sub_rootnnode is the right child of the new sub_root node.*/nnif(sub_root=NULL|sub_root-left=NULL)/impossible casesncout WARNING:

24、program error detected in rotate right endl;nelse nBinary_node*left_tree=sub_root-left;nsub_root-left=left_tree-right;nleft_tree-right=sub_root;nsub_root=left_tree;n n12/28/202229数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nvoid AVL_tree:right_balance(Binary_node*&sub_root)n/*Pre:sub root point

25、s to a subtree of an AVL tree,doubly unbalanced on the right.nPost:The AVL properties have been restored to the subtree.nUses:Methods of struct AVL node;functions rotate_right,rotate_left.*/nnBinary_node*&right_tree=sub_root-right;nswitch(right_tree-get_balance()ncase right_higher:/single rotation l

26、eftnsub_root-set_balance(equal_height);nright_tree-set_balance(equal_height);nrotate_left(sub_root);nbreak;ncase equal_height:/impossible case because taller=truencout WARNING:program error in right balance endl;12/28/202230数据结构与程序设计 教师：鲍钰case right_higher:12/28/202231数据结构与程序设计 教师：鲍钰Height Balance:A

27、VL Treesncase left_higher:/double rotation leftnBinary_node*sub_tree=right_tree-left;nswitch(sub_tree-get_balance()ncase equal_height:nsub_root-set_balance(equal_height);nright_tree-set_balance(equal_height);nbreak;ncase left_higher:/T2 is h,T3 is h-1nsub_root-set_balance(equal_height);nright_tree-s

28、et_balance(right_higher);nbreak;ncase right_higher:/T2 is h-1,T3 is hnsub_root-set_balance(left_higher);nright_tree-set_balance(equal_height);nbreak;n nsub_tree-set_balance(equal_height);nrotate_right(right_tree);nrotate_left(sub_root);nbreak;n n12/28/202232数据结构与程序设计 教师：鲍钰case left_higher:12/28/2022

29、33数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nvoid AVL_tree:left_balance(Binary_node*&sub_root)n/*Pre:sub root points to a subtree of an AVL tree,doubly unbalanced on the left.nPost:The AVL properties have been restored to the subtree.nUses:Methods of struct AVL node;functions rotate_right,rot

30、ate_left.*/nnBinary_node*&left_tree=sub_root-left;nswitch(left_tree-get_balance()ncase left_higher:/single rotation leftnsub_root-set_balance(equal_height);nleft_tree-set_balance(equal_height);nrotate_right(sub_root);nbreak;ncase equal_height:/impossible casencout WARNING:program error in right bala

31、nce endl;n 12/28/202234数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesncase right_higher:/double rotation leftnBinary_node*sub_tree=left_tree-right;nswitch(sub_tree-get_balance()ncase equal_height:nsub_root-set_balance(equal_height);nleft_tree-set_balance(equal_height);nbreak;ncase right_higher:nsub_root-se

32、t_balance(equal_height);nleft_tree-set_balance(left_higher);nbreak;ncase left_higher:nsub_root-set_balance(right_higher);nleft_tree-set_balance(equal_height);nbreak;n nsub_tree-set_balance(equal_height);nrotate_left(left_tree);nrotate_right(sub_root);nbreak;n n 12/28/202235数据结构与程序设计 教师：鲍钰AVL Trees-M

33、ainnvoid main()nAVL_tree mytree;nfor(int i=1;i10;i+)nmytree.insert(Record(i);ncoutPreorder:endl;nmytree.preorder(print);ncoutendl;ncoutinorder:endl;nmytree.inorder(print);ncoutendl;ncoutPostorder:endl;nmytree.postorder(print);ncoutendlendl;n12/28/202236数据结构与程序设计 教师：鲍钰AVL Trees-Main1122312314Rotate_l

34、eft12/28/202237数据结构与程序设计 教师：鲍钰AVL Trees-Main24153452631Rotate_leftRotate_left12/28/202238数据结构与程序设计 教师：鲍钰AVL Trees-Main462731546273158Rotate_left12/28/202239数据结构与程序设计 教师：鲍钰AVL Trees-Main462831597Rotate_left12/28/202240数据结构与程序设计 教师：鲍钰AVL Trees-MainnAVL_tree mytree2;nfor(i=9;i0;i-)nmytree2.insert(Recor

35、d(i);ncoutPreorder:endl;nmytree2.preorder(print);ncoutendl;ncoutinorder:endl;nmytree2.inorder(print);ncoutendl;ncoutPostorder:endl;nmytree2.postorder(print);ncoutendlendl;nncin.get();n12/28/202241数据结构与程序设计 教师：鲍钰AVL Trees-Main9988978976Rotate_right12/28/202242数据结构与程序设计 教师：鲍钰AVL Trees-Main89675685974R

36、otate_rightRotate_right12/28/202243数据结构与程序设计 教师：鲍钰AVL Trees-Main684953768495372Rotate_right12/28/202244数据结构与程序设计 教师：鲍钰AVL Trees-Main684952731Rotate_right12/28/202245数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nError_code AVL_tree:remove(Record&new_data)n/*Post:If the key of new data is not in t

37、he AVL tree,a 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.nUses:avl_remove.*/nnbool shorter=true;/Has the tree shorter in height?nreturn avl_remove(root,new_dat

38、a,shorter);n12/28/202246数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nError_code AVL_tree:avl_remove(Binary_node*&sub_root,nRecord&new_data,bool&shorter)nnError_code result=success;n Record sub_record;nif(sub_root=NULL)nshorter=false;nreturn not_present;n 12/28/202247数据结构与程序设计 教师：鲍钰Height Balanc

39、e:AVL Treesnelse if(new_data=sub_root-data)nBinary_node*to_delete=sub_root;n/Remember node to delete at end.nif(sub_root-right=NULL)nsub_root=sub_root-left;nshorter=true;ndelete to_delete;/Remove to_delete from tree.nreturn success;nnelse if(sub_root-left=NULL)nsub_root=sub_root-right;nshorter=true;

40、ndelete to_delete;/Remove to_delete from tree.nreturn success;n12/28/202248数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesnelse /Neither subtree is empty.nto_delete=sub_root-left;n /Move left to find predecessor.nBinary_node*parent=sub_root;n /parent of to_deletenwhile(to_delete-right!=NULL)n /to_delete is

41、not the predecessor.nparent=to_delete;nto_delete=to_delete-right;n n/sub_root-data=to_delete-data;/Move data from to_delete to root.nnew_data=to_delete-data;nsub_record=new_data;nn12/28/202249数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesnif(new_data data)/remove in left subtree.nresult=avl_remove(sub_root

42、-left,new_data,shorter);nif(sub_record.the_key()!=0)sub_root-data=sub_record;n /Move data from to_delete to root.nif(shorter=true)nswitch(sub_root-get_balance()/Change balance factors.ncase left_higher:nsub_root-set_balance(equal_height);nbreak;ncase equal_height:nsub_root-set_balance(right_higher);

43、nshorter=false;nbreak;ncase right_higher:nshorter=right_balance2(sub_root);nbreak;n n 12/28/202250数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesnif(new_data sub_root-data)/remove in right subtree.nresult=avl_remove(sub_root-right,new_data,shorter);nif(sub_record.the_key()!=0)sub_root-data=sub_record;n /Mov

44、e data from to_delete to root.nif(shorter=true)nswitch(sub_root-get_balance()/Change balance factors.ncase left_higher:nshorter=left_balance2(sub_root);nbreak;ncase equal_height:nsub_root-set_balance(left_higher);nshorter=false;nbreak;ncase right_higher:nsub_root-set_balance(equal_height);nbreak;n n

45、 nreturn result;n 12/28/202251数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nbool AVL_tree:right_balance2(Binary_node*&sub_root)n/*Pre:sub root points to a subtree of an AVL tree,doubly unbalanced on the right.nPost:The AVL properties have been restored to the subtree.nUses:Methods of struct AVL

46、node;functions rotate_right,rotate_left.*/nnbool shorter;nBinary_node*&right_tree=sub_root-right;nswitch(right_tree-get_balance()ncase right_higher:/single rotation leftnsub_root-set_balance(equal_height);nright_tree-set_balance(equal_height);nrotate_left(sub_root);nshorter=true;nbreak;12/28/202252数

47、据结构与程序设计 教师：鲍钰Height Balance:AVL Treesncase equal_height:/single rotation leftnright_tree-set_balance(left_higher);nrotate_left(sub_root);nshorter=false;nbreak;n 12/28/202253数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesncase left_higher:/double rotation leftnBinary_node*sub_tree=right_tree-left;nswitch(su

48、b_tree-get_balance()ncase equal_height:nsub_root-set_balance(equal_height);nright_tree-set_balance(equal_height);nbreak;ncase left_higher:nsub_root-set_balance(equal_height);nright_tree-set_balance(right_higher);nbreak;12/28/202254数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesncase right_higher:nsub_root-s

49、et_balance(left_higher);nright_tree-set_balance(equal_height);nbreak;n nsub_tree-set_balance(equal_height);nrotate_right(right_tree);nrotate_left(sub_root);nshorter=true;nbreak;n nreturn shorter;n12/28/202255数据结构与程序设计 教师：鲍钰Height Balance:AVL Treesntemplate nbool AVL_tree:left_balance2(Binary_node*&s

50、ub_root)n/*Pre:sub root points to a subtree of an AVL tree,doubly unbalanced on the left.nPost:The AVL properties have been restored to the subtree.nUses:Methods of struct AVL node;functions rotate_right,rotate_left.*/n12/28/202256数据结构与程序设计 教师：鲍钰Main-Book P487nvoid main()nAVL_tree mytree;nmytree.ins