java树插入root_[Java]AVL树插入：单旋、双旋

目录

代码出处

各种实现

概念说明

算法说明

测试运行

代码修改

完整源码

代码出处

各种实现

Java实现

C&＃43;&＃43;11

Data Structures and Algorithm Analysis in C&＃43;&＃43; (Fourth Edition)

CS-7 Text

https://users.cs.fiu.edu/~weiss/dsaa_c&＃43;&＃43;4/code/

g&＃43;&＃43; -std&＃61;c&＃43;&＃43;0x TestAvlTree.cpp

g&＃43;&＃43; -std&＃61;c&＃43;&＃43;0x TestIntCell.cpp IntCell.cpp

C

概念说明

AVL树

https://en.wikipedia.org/wiki/AVL_tree

In an AVL tree, the heights of the two child subtrees of any node differ by at most one

在AVL树种&＃xff0c;任意两棵子树的高度不能超过1&＃xff1b;

路径 path 、长度 length、 高度height 与 深度depth

The root node has depth zero, leaf nodes have height zero.

根结点的深度是0&＃xff0c;叶子结点的高度是0&＃xff1b;

t.insert( nodes[i] );

t.preorder();

}

}

新增preorder()相关&＃xff1a;前序序列输出AVL树&＃xff0c;带空格表示层次结构

/**

* Print the tree contents in preorder.

*/

public void preorder()

{

if( isEmpty() )

System.out.println( "Empty tree" );

else

preorder( root , 0 );

System.out.println();

}

/**

* Internal method to print a subtree in preorder.

* &＃64;param t the node that roots the tree.

*/

private void preorder( AvlNode t, int blanks)

{

if( t !&＃61; null )

{

System.out.println();

for(int i &＃61; 0 ;i

System.out.print(" ");

System.out.print( t.element );

preorder( t.left, blanks&＃43;1 );

preorder( t.right, blanks&＃43;1 );

}

}

完整源码 AvlTree.java

// AvlTree class

//

// CONSTRUCTION: with no initializer

//

// ******************PUBLIC OPERATIONS*********************

// void insert( x ) --> Insert x

// void remove( x ) --> Remove x (unimplemented)

// boolean contains( x ) --> Return true if x is present

// boolean remove( x ) --> Return true if x was present

// Comparable findMin( ) --> Return smallest item

// Comparable findMax( ) --> Return largest item

// boolean isEmpty( ) --> Return true if empty; else false

// void makeEmpty( ) --> Remove all items

// void printTree( ) --> Print tree in sorted order

// ******************ERRORS********************************

// Throws UnderflowException as appropriate

/**

* Implements an AVL tree.

* Note that all "matching" is based on the compareTo method.

* &＃64;author Mark Allen Weiss

*/

public class AvlTree>

{

/**

* Construct the tree.

*/

public AvlTree( )

{

root &＃61; null;

}

/**

* Insert into the tree; duplicates are ignored.

* &＃64;param x the item to insert.

*/

public void insert( AnyType x )

{

root &＃61; insert( x, root );

}

/**

* Remove from the tree. Nothing is done if x is not found.

* &＃64;param x the item to remove.

*/

public void remove( AnyType x )

{

root &＃61; remove( x, root );

}

/**

* Internal method to remove from a subtree.

* &＃64;param x the item to remove.

* &＃64;param t the node that roots the subtree.

* &＃64;return the new root of the subtree.

*/

private AvlNode remove( AnyType x, AvlNode t )

{

if( t &＃61;&＃61; null )

return t; // Item not found; do nothing

int compareResult &＃61; x.compareTo( t.element );

if( compareResult <0 )

t.left &＃61; remove( x, t.left );

else if( compareResult > 0 )

t.right &＃61; remove( x, t.right );

else if( t.left !&＃61; null && t.right !&＃61; null ) // Two children

{

t.element &＃61; findMin( t.right ).element;

t.right &＃61; remove( t.element, t.right );

}

else

t &＃61; ( t.left !&＃61; null ) ? t.left : t.right;

return balance( t );

}

/**

* Find the smallest item in the tree.

* &＃64;return smallest item or null if empty.

*/

public AnyType findMin( )

{

if( isEmpty( ) )

throw new UnderflowException( );

return findMin( root ).element;

}

/**

* Find the largest item in the tree.

* &＃64;return the largest item of null if empty.

*/

public AnyType findMax( )

{

if( isEmpty( ) )

throw new UnderflowException( );

return findMax( root ).element;

}

/**

* Find an item in the tree.

* &＃64;param x the item to search for.

* &＃64;return true if x is found.

*/

public boolean contains( AnyType x )

{

return contains( x, root );

}

/**

* Make the tree logically empty.

*/

public void makeEmpty( )

{

root &＃61; null;

}

/**

* Test if the tree is logically empty.

* &＃64;return true if empty, false otherwise.

*/

public boolean isEmpty( )

{

return root &＃61;&＃61; null;

}

/**

* Print the tree contents in sorted order.

*/

public void printTree( )

{

if( isEmpty( ) )

System.out.println( "Empty tree" );

else

printTree( root );

}

/**

* Print the tree contents in preorder.

*/

public void preorder()

{

if( isEmpty() )

System.out.println( "Empty tree" );

else

preorder( root , 0 );

System.out.println();

}

private static final int ALLOWED_IMBALANCE &＃61; 1;

// Assume t is either balanced or within one of being balanced

private AvlNode balance( AvlNode t )

{

if( t &＃61;&＃61; null )

return t;

if( height( t.left ) - height( t.right ) > ALLOWED_IMBALANCE )

if( height( t.left.left ) >&＃61; height( t.left.right ) )

t &＃61; rotateWithLeftChild( t );

else

t &＃61; doubleWithLeftChild( t );

else

if( height( t.right ) - height( t.left ) > ALLOWED_IMBALANCE )

if( height( t.right.right ) >&＃61; height( t.right.left ) )

t &＃61; rotateWithRightChild( t );

else

t &＃61; doubleWithRightChild( t );

t.height &＃61; Math.max( height( t.left ), height( t.right ) ) &＃43; 1;

return t;

}

public void checkBalance( )

{

checkBalance( root );

}

private int checkBalance( AvlNode t )

{

if( t &＃61;&＃61; null )

return -1;

if( t !&＃61; null )

{

int hl &＃61; checkBalance( t.left );

int hr &＃61; checkBalance( t.right );

if( Math.abs( height( t.left ) - height( t.right ) ) > 1 ||

height( t.left ) !&＃61; hl || height( t.right ) !&＃61; hr )

System.out.println( "OOPS!!" );

}

return height( t );

}

/**

* Internal method to insert into a subtree.

* &＃64;param x the item to insert.

* &＃64;param t the node that roots the subtree.

* &＃64;return the new root of the subtree.

*/

private AvlNode insert( AnyType x, AvlNode t )

{

if( t &＃61;&＃61; null )

return new AvlNode<>( x, null, null );

int compareResult &＃61; x.compareTo( t.element );

if( compareResult <0 )

t.left &＃61; insert( x, t.left );

else if( compareResult > 0 )

t.right &＃61; insert( x, t.right );

else

; // Duplicate; do nothing

return balance( t );

}

/**

* Internal method to find the smallest item in a subtree.

* &＃64;param t the node that roots the tree.

* &＃64;return node containing the smallest item.

*/

private AvlNode findMin( AvlNode t )

{

if( t &＃61;&＃61; null )

return t;

while( t.left !&＃61; null )

t &＃61; t.left;

return t;

}

/**

* Internal method to find the largest item in a subtree.

* &＃64;param t the node that roots the tree.

* &＃64;return node containing the largest item.

*/

private AvlNode findMax( AvlNode t )

{

if( t &＃61;&＃61; null )

return t;

while( t.right !&＃61; null )

t &＃61; t.right;

return t;

}

/**

* Internal method to find an item in a subtree.

* &＃64;param x is item to search for.

* &＃64;param t the node that roots the tree.

* &＃64;return true if x is found in subtree.

*/

private boolean contains( AnyType x, AvlNode t )

{

while( t !&＃61; null )

{

int compareResult &＃61; x.compareTo( t.element );

if( compareResult <0 )

t &＃61; t.left;

else if( compareResult > 0 )

t &＃61; t.right;

else

return true; // Match

}

return false; // No match

}

/**

* Internal method to print a subtree in sorted order.

* &＃64;param t the node that roots the tree.

*/

private void printTree( AvlNode t )

{

if( t !&＃61; null )

{

printTree( t.left );

System.out.println( t.element );

printTree( t.right );

}

}

/**

* Internal method to print a subtree in preorder.

* &＃64;param t the node that roots the tree.

*/

private void preorder( AvlNode t, int blanks)

{

if( t !&＃61; null )

{

System.out.println();

for(int i &＃61; 0 ;i

System.out.print(" ");

System.out.print( t.element );

preorder( t.left, blanks&＃43;1 );

preorder( t.right, blanks&＃43;1 );

}

}

/**

* Return the height of node t, or -1, if null.

*/

private int height( AvlNode t )

{

return t &＃61;&＃61; null ? -1 : t.height;

}

/**

* Rotate binary tree node with left child.

* For AVL trees, this is a single rotation for case 1.

* Update heights, then return new root.

*/

private AvlNode rotateWithLeftChild( AvlNode k2 )

{

AvlNode k1 &＃61; k2.left;

k2.left &＃61; k1.right;

k1.right &＃61; k2;

k2.height &＃61; Math.max( height( k2.left ), height( k2.right ) ) &＃43; 1;

k1.height &＃61; Math.max( height( k1.left ), k2.height ) &＃43; 1;

return k1;

}

/**

* Rotate binary tree node with right child.

* For AVL trees, this is a single rotation for case 4.

* Update heights, then return new root.

*/

private AvlNode rotateWithRightChild( AvlNode k1 )

{

AvlNode k2 &＃61; k1.right;

k1.right &＃61; k2.left;

k2.left &＃61; k1;

k1.height &＃61; Math.max( height( k1.left ), height( k1.right ) ) &＃43; 1;

k2.height &＃61; Math.max( height( k2.right ), k1.height ) &＃43; 1;

return k2;

}

/**

* Double rotate binary tree node: first left child

* with its right child; then node k3 with new left child.

* For AVL trees, this is a double rotation for case 2.

* Update heights, then return new root.

*/

private AvlNode doubleWithLeftChild( AvlNode k3 )

{

k3.left &＃61; rotateWithRightChild( k3.left );

return rotateWithLeftChild( k3 );

}

/**

* Double rotate binary tree node: first right child

* with its left child; then node k1 with new right child.

* For AVL trees, this is a double rotation for case 3.

* Update heights, then return new root.

*/

private AvlNode doubleWithRightChild( AvlNode k1 )

{

k1.right &＃61; rotateWithLeftChild( k1.right );

return rotateWithRightChild( k1 );

}

private static class AvlNode

{

// Constructors

AvlNode( AnyType theElement )

{

this( theElement, null, null );

}

AvlNode( AnyType theElement, AvlNode lt, AvlNode rt )

{

element &＃61; theElement;

left &＃61; lt;

right &＃61; rt;

height &＃61; 0;

}

AnyType element; // The data in the node

AvlNode left; // Left child

AvlNode right; // Right child

int height; // Height

}

/** The tree root. */

private AvlNode root;

// Test program

public static void main( String [ ] args )

{

AvlTree t &＃61; new AvlTree<>( );

int[] nodes &＃61; {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};

for( int i &＃61; 0; i

{

System.out.println( "INSERT: " &＃43; nodes[i] );

t.insert( nodes[i] );

t.preorder();

}

}

}

完整源码 TestAvlTree.cpp

#ifndef AVL_TREE_H

#define AVL_TREE_H

#include "dsexceptions.h"

#include

#include

using namespace std;

// AvlTree class

//

// CONSTRUCTION: zero parameter

//

// ******************PUBLIC OPERATIONS*********************

// void insert( x ) --> Insert x

// void remove( x ) --> Remove x (unimplemented)

// bool contains( x ) --> Return true if x is present

// Comparable findMin( ) --> Return smallest item

// Comparable findMax( ) --> Return largest item

// boolean isEmpty( ) --> Return true if empty; else false

// void makeEmpty( ) --> Remove all items

// void printTree( ) --> Print tree in sorted order

// ******************ERRORS********************************

// Throws UnderflowException as warranted

template

class AvlTree

{

public:

AvlTree( ) : root{ nullptr }

{ }

AvlTree( const AvlTree & rhs ) : root{ nullptr }

{

root &＃61; clone( rhs.root );

}

AvlTree( AvlTree && rhs ) : root{ rhs.root }

{

rhs.root &＃61; nullptr;

}

~AvlTree( )

{

makeEmpty( );

}

/**

* Deep copy.

*/

AvlTree & operator&＃61;( const AvlTree & rhs )

{

AvlTree copy &＃61; rhs;

std::swap( *this, copy );

return *this;

}

/**

* Move.

*/

AvlTree & operator&＃61;( AvlTree && rhs )

{

std::swap( root, rhs.root );

return *this;

}

/**

* Find the smallest item in the tree.

* Throw UnderflowException if empty.

*/

const Comparable & findMin( ) const

{

if( isEmpty( ) )

throw UnderflowException{ };

return findMin( root )->element;

}

/**

* Find the largest item in the tree.

* Throw UnderflowException if empty.

*/

const Comparable & findMax( ) const

{

if( isEmpty( ) )

throw UnderflowException{ };

return findMax( root )->element;

}

/**

* Returns true if x is found in the tree.

*/

bool contains( const Comparable & x ) const

{

return contains( x, root );

}

/**

* Test if the tree is logically empty.

* Return true if empty, false otherwise.

*/

bool isEmpty( ) const

{

return root &＃61;&＃61; nullptr;

}

/**

* Print the tree contents in sorted order.

*/

void printTree( ) const

{

if( isEmpty( ) )

cout <<"Empty tree" <

else

printTree( root );

}

/**

* Make the tree logically empty.

*/

void makeEmpty( )

{

makeEmpty( root );

}

/**

* Insert x into the tree; duplicates are ignored.

*/

void insert( const Comparable & x )

{

insert( x, root );

}

/**

* Insert x into the tree; duplicates are ignored.

*/

void insert( Comparable && x )

{

insert( std::move( x ), root );

}

/**

* Remove x from the tree. Nothing is done if x is not found.

*/

void remove( const Comparable & x )

{

remove( x, root );

}

private:

struct AvlNode

{

Comparable element;

AvlNode *left;

AvlNode *right;

int height;

AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h &＃61; 0 )

: element{ ele }, left{ lt }, right{ rt }, height{ h } { }

AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h &＃61; 0 )

: element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { }

};

AvlNode *root;

/**

* 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 &＃61;&＃61; nullptr )

t &＃61; new AvlNode{ x, nullptr, nullptr };

else if( x element )

insert( x, t->left );

else if( t->element

insert( x, t->right );

balance( t );

}

/**

* 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( Comparable && x, AvlNode * & t )

{

if( t &＃61;&＃61; nullptr )

t &＃61; new AvlNode{ std::move( x ), nullptr, nullptr };

else if( x element )

insert( std::move( x ), t->left );

else if( t->element

insert( std::move( x ), t->right );

balance( t );

}

/**

* Internal method to remove from a subtree.

* x is the item to remove.

* t is the node that roots the subtree.

* Set the new root of the subtree.

*/

void remove( const Comparable & x, AvlNode * & t )

{

if( t &＃61;&＃61; nullptr )

return; // Item not found; do nothing

if( x element )

remove( x, t->left );

else if( t->element

remove( x, t->right );

else if( t->left !&＃61; nullptr && t->right !&＃61; nullptr ) // Two children

{

t->element &＃61; findMin( t->right )->element;

remove( t->element, t->right );

}

else

{

AvlNode *oldNode &＃61; t;

t &＃61; ( t->left !&＃61; nullptr ) ? t->left : t->right;

delete oldNode;

}

balance( t );

}

static const int ALLOWED_IMBALANCE &＃61; 1;

// Assume t is balanced or within one of being balanced

void balance( AvlNode * & t )

{

if( t &＃61;&＃61; nullptr )

return;

if( height( t->left ) - height( t->right ) > ALLOWED_IMBALANCE )

if( height( t->left->left ) >&＃61; height( t->left->right ) )

rotateWithLeftChild( t );

else

doubleWithLeftChild( t );

else

if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE )

if( height( t->right->right ) >&＃61; height( t->right->left ) )

rotateWithRightChild( t );

else

doubleWithRightChild( t );

t->height &＃61; max( height( t->left ), height( t->right ) ) &＃43; 1;

}

/**

* Internal method to find the smallest item in a subtree t.

* Return node containing the smallest item.

*/

AvlNode * findMin( AvlNode *t ) const

{

if( t &＃61;&＃61; nullptr )

return nullptr;

if( t->left &＃61;&＃61; nullptr )

return t;

return findMin( t->left );

}

/**

* Internal method to find the largest item in a subtree t.

* Return node containing the largest item.

*/

AvlNode * findMax( AvlNode *t ) const

{

if( t !&＃61; nullptr )

while( t->right !&＃61; nullptr )

t &＃61; t->right;

return t;

}

/**

* Internal method to test if an item is in a subtree.

* x is item to search for.

* t is the node that roots the tree.

*/

bool contains( const Comparable & x, AvlNode *t ) const

{

if( t &＃61;&＃61; nullptr )

return false;

else if( x element )

return contains( x, t->left );

else if( t->element

return contains( x, t->right );

else

return true; // Match

}

/****** NONRECURSIVE VERSION*************************

bool contains( const Comparable & x, AvlNode *t ) const

{

while( t !&＃61; nullptr )

if( x element )

t &＃61; t->left;

else if( t->element

t &＃61; t->right;

else

return true; // Match

return false; // No match

}

*****************************************************/

/**

* Internal method to make subtree empty.

*/

void makeEmpty( AvlNode * & t )

{

if( t !&＃61; nullptr )

{

makeEmpty( t->left );

makeEmpty( t->right );

delete t;

}

t &＃61; nullptr;

}

/**

* Internal method to print a subtree rooted at t in sorted order.

*/

void printTree( AvlNode *t ) const

{

if( t !&＃61; nullptr )

{

printTree( t->left );

cout <element <

printTree( t->right );

}

}

/**

* Internal method to clone subtree.

*/

AvlNode * clone( AvlNode *t ) const

{

if( t &＃61;&＃61; nullptr )

return nullptr;

else

return new AvlNode{ t->element, clone( t->left ), clone( t->right ), t->height };

}

// Avl manipulations

/**

* Return the height of node t or -1 if nullptr.

*/

int height( AvlNode *t ) const

{

return t &＃61;&＃61; nullptr ? -1 : t->height;

}

int max( int lhs, int rhs ) const

{

return lhs > rhs ? lhs : rhs;

}

/**

* Rotate binary tree node with left child.

* For AVL trees, this is a single rotation for case 1.

* Update heights, then set new root.

*/

void rotateWithLeftChild( AvlNode * & k2 )

{

AvlNode *k1 &＃61; k2->left;

k2->left &＃61; k1->right;

k1->right &＃61; k2;

k2->height &＃61; max( height( k2->left ), height( k2->right ) ) &＃43; 1;

k1->height &＃61; max( height( k1->left ), k2->height ) &＃43; 1;

k2 &＃61; k1;

}

/**

* Rotate binary tree node with right child.

* For AVL trees, this is a single rotation for case 4.

* Update heights, then set new root.

*/

void rotateWithRightChild( AvlNode * & k1 )

{

AvlNode *k2 &＃61; k1->right;

k1->right &＃61; k2->left;

k2->left &＃61; k1;

k1->height &＃61; max( height( k1->left ), height( k1->right ) ) &＃43; 1;

k2->height &＃61; max( height( k2->right ), k1->height ) &＃43; 1;

k1 &＃61; k2;

}

/**

* Double rotate binary tree node: first left child.

* with its right child; then node k3 with new left child.

* For AVL trees, this is a double rotation for case 2.

* Update heights, then set new root.

*/

void doubleWithLeftChild( AvlNode * & k3 )

{

rotateWithRightChild( k3->left );

rotateWithLeftChild( k3 );

}

/**

* Double rotate binary tree node: first right child.

* with its left child; then node k1 with new right child.

* For AVL trees, this is a double rotation for case 3.

* Update heights, then set new root.

*/

void doubleWithRightChild( AvlNode * & k1 )

{

rotateWithLeftChild( k1->right );

rotateWithRightChild( k1 );

}

};

#endif