AVL樹的C++實現

第一棵平衡二叉查找樹又被稱為AVL樹，以它的發現者Adelson-Velskii和Landis命名的。
它廣泛說明了平衡二叉查找樹中使用的各種思想。就是具有附加平衡條件的二叉查找樹。
任一平衡條件必須是易於維護，並確保樹的深度是O(logN)。最簡單的思想是要求左子樹和
右子樹具有同樣的高度。但是這個要求太嚴格了，維持平衡的同時插入數據項太困難。
而AVL樹在這方面找到了一個良好的折中點。
AVL樹具有以下性質
1、它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1

2、左右兩個子樹都是一棵平衡二叉樹

這裡用C++實現了平衡二叉樹的插入和刪除操作，對於查詢沒有給出具體的實現，查詢的實現應該不難，感興趣的讀者可以自行實現

內容都在代碼裡

#include<iostream>
using std::ostream;
class AVLTreeNode
{
private:
int value;
AVLTreeNode* lchild;
AVLTreeNode* rchild;
AVLTreeNode* parent;

friend class AVLTree;
friend ostream& operator<<(ostream& os,const AVLTree&);
public:
AVLTreeNode();
~AVLTreeNode();
};
class AVLTree
{
private:
AVLTreeNode* root;
public:
AVLTree();
~AVLTree();
void insert(int data);
void insert(int datas[],int num);
void remove(int);
void remove(int[],int);
AVLTreeNode* getRoot();
private:
void rightRotate(AVLTreeNode*);  //右旋
void leftRotate(AVLTreeNode*); //左旋
/*測試所用*/
bool check_tree(AVLTreeNode*);
int getHeight(AVLTreeNode*);
/*插入之後對樹進行調整*/
void insertUpdate(AVLTreeNode*,int);
/*刪除之後對樹進行調整*/
void removeUpdate(AVLTreeNode*,int);
friend ostream& operator<<(ostream& os,const AVLTree&);
};

ostream& operator<<(ostream& os,const AVLTree&);

下面是.cpp文件內容部分。測試數據的顯示量有點大，根據需要可進行調整。在插入數據和刪除數組的方法中有測試打印語句部分，可根據需要進行修改

#include"averge_tree.h"
#include<vector>
using std::vector;
using std::endl;
using std::cout;
/*
AVLTreeNode類的函數實現
*/
AVLTreeNode::AVLTreeNode()
{
lchild=rchild=parent=NULL;
}
/*析構時采取級聯的方式*/
AVLTreeNode::~AVLTreeNode()
{
delete lchild;
delete rchild;
}
/*AVLTree類的函數實現*/
AVLTree::AVLTree()
{
root=NULL;
}
AVLTree::~AVLTree()
{
delete root;
}
AVLTreeNode* AVLTree::getRoot()
{
return root;
}
void AVLTree::insert(int datas[], int num)
{
for(int i=0;i<num;i++)
{
/*cout<<"........................................................................"<<endl;
cout<<"before insert "<<datas[i]<<endl;
cout<<*this<<endl;
insert(datas[i]);
cout<<"after insert "<<datas[i]<<endl;
cout<<*this<<endl;
if(check_tree(root))
{
cout<<"check passed "<<endl;
}
else
{
cout<<"check failed "<<endl;
break;
}*/
insert(datas[i]);
}
}
/*
插入後，可能對從這個插入節點向上到根的這條路徑中的某個節點平衡造成影響
因此，需要找出這個節點，並且對這個節點進行調整
*/
void AVLTree::insert(int data)
{
if(!root) //空樹
{
root=new AVLTreeNode;
root->parent=NULL;
root->lchild=root->rchild=NULL;
root->value=data;
}
else
{
AVLTreeNode* p=root;//用p指向要被插入的節點
AVLTreeNode* temp=data>p->value?p->rchild:p->lchild;
while(temp)
{
p=temp;
temp=data>p->value?p->rchild:p->lchild; //若值相同，是放在左邊
}
AVLTreeNode* newNode=new AVLTreeNode;
newNode->rchild=newNode->lchild=NULL;
newNode->parent=p;
newNode->value=data;
if(data>p->value)
p->rchild=newNode;
else
p->lchild=newNode;
/*
向上查找到第一個需要調整的節點
*/
p=p->parent;
int v;
if(p)
v=abs(getHeight(p->lchild)-getHeight(p->rchild));
while(p&&v<=1)
{
p=p->parent;
if(p)
v=abs(getHeight(p->lchild)-getHeight(p->rchild));
}
//如果發現有節點受影響，那麼需要對這個找到的第一個節點做調整
if(p)
{
insertUpdate(p,data);
}

}
}
/*
node代表從插入點向上找到的第一個不平衡點