Documents

Avl

Categories
Published
of 20
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Related Documents
Share
Description
avl
Transcript
   Brad Appleton Software Tools Developer     E-mail:  bradapp@enteract.com  WWW: www.enteract.com/~bradapp/ AVL Trees: Tutorial and C++ Implementation Copyright © 1989-1997 by Brad Appleton All right! re!er ed.   #he $ollowing di!c%!!ion i! part o$ a $reely a ailable p%blic domain A&'tree library written in C((. #he $%ll C(( !o%rce code di!trib%tion may be $o%nd in AvlTrees.tar.gz  )*1+B g,ipped tar $ile.a plain old +0 C er!ion i! a ailable in libavl.tar.gz  )*+B g,ipped tar $ile2 AVL Trees An A&' tree i! a !pecial type o$ binary tree that i! alway! 3partially3 balanced. #he criteria that i! %!ed to determine the 3le el3 o$ 3balanced-ne!!3 i! the di$$erence between the height! o$ !%btree! o$ a root in the tree. #he 3height3 o$ tree i! the 3n%mber o$ le el!3 in the tree. 4r to be more $ormal the height o$ a tree i! de$ined a! $ollow!5 1.#he height o$ a tree with no element! i! 6 *.#he height o$ a tree with 1 element i! 1 .#he height o$ a tree with  1 element i! e%al to 1 ( the height o$ it! talle!t !%btree. An A&' tree i! a binary tree in which the di$$erence between the height o$ the right and le$t !%btree! )or the root node i! ne er more than one. #he idea behind maintaining the 3A&'-ne!!3 o$ an A&' tree i! that whene er we in!ert or delete an item i$ we ha e 3 iolated3 the 3A&'-ne!!3 o$ the tree in anyway we m%!t then re!tore it by per$orming a !et o$ manip%lation! )called 3rotation!3 on the tree. #he!e rotation! come in two $la or!5 !ingle rotation! and do%ble rotation! )and each $la or ha! it! corre!ponding 3le$t3 and 3right3 er!ion!.  An e:ample o$ a !ingle rotation i! a! $ollow!5 ;%ppo!e < ha e a tree that loo=! li=e thi!5 c / b  >ow < in!ert the item 3a3 and get the re!%lting binary tree5 c / b / a  >ow thi! re!%lting tree iolate! the 3A&' criteria3 the le$t !%btree ha! a height o$ * b%t the right !%btree ha! a height o$ 6 !o the di$$erence in the two height! i! 3*3 )which i! greater than 1. ;4 what we do i! per$orm a 3!ingle rotation3 )or 00 $or a !ingle right rotation or '' $or a !ingle le$t rotation on the tree )by rotating the 3c3 element down cloc=wi!e to the right to tran!$orm it into the $ollowing tree5 b / \ a c #hi! tree i! now balanced. An e:ample o$ a 3do%ble rotation3 )or 0' $or a do%ble right rotation or '0 $or a do%ble le$t rotation i! the $ollowing5 ;%ppo!e < ha e a tree that loo=! li=e thi!5 a \ c  >ow < in!ert the item 3b3 and get the re!%lting binary tree5 a \ c / b #hi! re!%lting tree al!o iolate! the 3A&' criteria3 !o we $i: it by $ir!t rotating 3c3 down to the right )!o we get 3a-b-c3 and then rotating 3a3 down to the le$t !o that the tree i! tran!$ormed into thi!5 b / \ a c  <n order to detect when a 3 iolation3 o$ the A&' criteria occ%r! we need to ha e each node =eep trac= o$ the di$$erence in height between it! right and le$t !%btree!. ?e call thi!3di$$erence3 the 3balance3 $actor and de$ine it to be the height o$ the right !%btree min%! the height o$ the le$t !%btree o$ a tree. ;o a! long a! the 3balance3 $actor o$ each node i! ne er 1 or -1 we ha e an A&' tree. A! !oon a! the balance $actor o$ a node become! * )or -* we need to per$orm one or more rotation! to en!%re that the re!%ltant tree !ati!$ie! the A&' criteria. Implementing AVL Trees in C++ Be$ore we begin o%r A&' tree implementation in C(( let! a!!%me we ha e a template cla!! named 3Comparable3 de$ined a! $ollow!5 // cmp_t is an enumeration type indicating the result of a // comparison. enum cmp_t { MI_!M # $%& // less than '(_!M # )& // e*ual to MA+_!M # % // greater than ,- // !lass !omparable corresponds to an arbitrary comparable element // ith a 0eyfield that has an ordering relation. The template parameter // 1eyType is the type of the 0eyfield // template 2class 1eyType3 class !omparable { private4 1eyType my1ey- public4 !omparable51eyType 0ey6 4 my1ey50ey6 {,- // 7se default copy$ctor& assignment& 8 destructor // !ompare this item against the given 0ey 8 return the result cmp_t !ompare51eyType 0ey6 const- // 9et the 0ey$field of an item 1eyType 1ey56 const { return my1ey- , ,- 'i=e the 3Comparable3 cla!! o%r A&' tree will al!o be a template cla!! parameteri,ed by a +ey#ype5 // !lass Avlode represents a node in an A:; tree. The template parameter // 1eyType is the type of the 0eyfield // template 2class 1eyType3 class Avlode { private4 !omparable21eyType3 < my=ata- // =ata field   Avlode21eyType3 < my>ubtree?@- // >ubtree pointers short myBal- // Balance factor // ... many details omitted ,- Calculating New Balances After a Rotation #o calc%late the new balance! a$ter a !ingle le$t rotation a!!%me we ha e the $ollowing ca!e5 A B / \ / \ / \ / \ a B ##3 A c / \ / \ / \ / \ b c a b #he le$t i! what the tree loo=ed li=e B40 the rotation and the right i! what the tree loo=! li=e a$ter the rotation. Capital letter! are %!ed to denote !ingle node! and lowerca!e letter! are %!ed to denote !%btree!. #he 3balance3 o$ a tree i! the height o$ it! right !%btree le!! the height o$ it! le$t !%btree. #here$ore we can calc%late the new balance! o$ 3A3 and 3B3 a! $ollow! ) ht   i! the height $%nction5 eBal5A6 # ht5b6 $ ht5a6 CldBal5A6 # ht5B6 $ ht5a6 # 5 % D maE 5ht5b6& ht5c66 6 $ ht5a6 !%btracting the !econd e%ation $rom the $ir!t yield!5 eBal5A6 $ CldBal5A6 # ht5b6 $ 5 % D maE 5ht5b6& ht5c66 6 D ht5a6 $ ht5a6 canceling o%t the ht)a term! and adding 4ldBal)A to both !ide! yield!5 eBal5A6 # CldBal5A6 $ % $ 5maE 5ht5b6& ht5c66 $ ht5b6 6  >oting that ma:): y - , D ma:):-, y-, we get5 eBal5A6 # CldBal5A6 $ % $ 5maE 5ht5b6 $ ht5b6& ht5c6 $ ht5b66 6 B%t ht)c - ht)b i! 4ldBal)B !o we get5 eBal5A6 # CldBal5A6 $ % $ 5maE 5)& CldBal5B66 6 # CldBal5A6 $ % $ maE 5)& CldBal5B66 #h%! $or A we get the e%ation5
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks