AVL树的C++实现

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代表从插入点向上找到的第一个不平衡点