Ch04 Trees课件.pptVIP

§4 AVL Trees 〖Example〗 Input the months Mar Mar 0 ?1 May May 0 Nov Nov 0 ?1 ?2 May 0 ?1 Nov 0 0 ?2 ?1 Mar 0 0 0 ? The trouble maker Nov is in the right subtree’s right subtree of the trouble finder Mar. Hence it is called an RR rotation. In general: A ?1 B 0 BL BR AL RR Insertion RR Rotation A ?2 B ?1 BL BR AL BL B 0 A AL BR 0 A is not necessarily the root of the tree Single rotation §4 AVL Trees Aug May 0 ?1 Nov 0 0 ?2 ?1 Mar 0 1 1 Aug 0 Apr Apr 0 1 2 2 LL Rotation May 0 ?1 Nov 0 0 ?2 ?1 Aug 0 1 1 ?1 Mar 0 0 Apr 0 In general: A 1 B 0 BR BL AR LL Insertion A 2 B 1 BR BL AR LL Rotation B 0 A AR BL BR 0 §4 AVL Trees May 0 ?1 Nov 0 0 ?2 ?1 Aug 0 1 1 ?1 Mar 0 0 Apr 0 Jan Jan 0 1 ?1 2 LR Rotation Mar 0 ?1 May 0 ?1 ?2 ?1 Aug 0 1 0 ?1 Jan 0 0 Apr 0 Nov 0 In general: A 1 B 0 BL AR C 0 CR CL LR Insertion A 2 B ?1 BL AR C ?1 CR CL OR LR Rotation BL AR C 0 A ?1 or 0 CR B 0 or 1 CL OR Double Rotation §4 AVL Trees Dec July Mar 0 ?1 May 0 ?1 ?2 ?1 Aug 0 1 1 ?1 Jan 0 Apr 0 Nov 0 July 0 Dec 0 Feb Feb 0 ?1 1 ?2 2 RL Rotation July 0 Dec 0 ?1 Aug 0 1 ?2 ?1 Jan 0 1 0 ?1 Feb 0 0 Apr 0 Mar 0 ?1 May 0 ?1 ?2 ?1 1 Nov 0 In general: A 1 B 0 BR AL C 0 CL CR RL Insertion A ?2 B 1 BR AL C ?1 CL CR OR RL Rotation BR AL C 0 A 0 or 1 CL B ?1 or 0 CR OR §4 AVL Trees July 0 Dec 0 ?1 Aug 0 1 ?2 ?1 Jan 0 1 0 ?1 Feb 0 0 Apr 0 Mar 0 ?1 May 0 ?1 ?2 ?1 1 Nov 0 June Oct Sept June 0 ?1 ?1 ?1 2 Nov 0 Dec 0 ?1 Aug 1 ?2 ?1 Feb 0 1 July ?1 Apr 0 Mar 0 May ?1 June 0 Jan 0 Oct 0 ?1 ?2 ?1 ?1 Oct 0 Dec 0 ?1 Aug 1 ?2 ?1 Feb 0 1 July ?1 Apr 0 Mar 0 Nov 0 June 0 Jan 0 May 0 Sept 0 ?1 ?1 ?1 ?1 Note: Several bf’s might be changed even if we don’t need to reconstruct the tree. Another option is to keep a height field for each node. §4 AVL Trees /** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( const Comparable x, AvlNode * t ) { if( t == NULL )