一、概念

AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。
它是最先发明的自平衡二叉查找树,也被称为高度平衡树。相比于"二叉查找树",它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。
如果在AVL树中插入或删除节点后,使得高度之差大于1。此时,AVL树的平衡状态就被破坏,它就不再是一棵二叉树;为了让它重新维持在一个平衡状态,就需要对其进行旋转处理。学AVL树,重点的地方也就是它的旋转算法;

二、AVL树的实现

1. 节点

1.1 AVL树节点

template <class T>
class AVLTreeNode{
public:
T key; // 关键字(键值)
int height; // 高度
AVLTreeNode *left; // 左孩子
AVLTreeNode *right; // 右孩子 AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode *r):
key(value), height(),left(l),right(r) {}
};

AVLTreeNode是AVL树的节点类,它包括的几个组成对象:
(01) key -- 是关键字,是用来对AVL树的节点进行排序的。
(02) left -- 是左孩子。
(03) right -- 是右孩子。
(04) height -- 是高度。

1.2 AVL树

template <class T>
class AVLTree {
private:
AVLTreeNode<T> *mRoot; // 根结点 public:
AVLTree();
~AVLTree(); // 获取树的高度
int height();
// 获取树的高度
int max(int a, int b); // 前序遍历"AVL树"
void preOrder();
// 中序遍历"AVL树"
void inOrder();
// 后序遍历"AVL树"
void postOrder(); // (递归实现)查找"AVL树"中键值为key的节点
AVLTreeNode<T>* search(T key);
// (非递归实现)查找"AVL树"中键值为key的节点
AVLTreeNode<T>* iterativeSearch(T key); // 查找最小结点:返回最小结点的键值。
T minimum();
// 查找最大结点:返回最大结点的键值。
T maximum(); // 将结点(key为节点键值)插入到AVL树中
void insert(T key); // 删除结点(key为节点键值)
void remove(T key); // 销毁AVL树
void destroy(); // 打印AVL树
void print();
private:
// 获取树的高度
int height(AVLTreeNode<T>* tree) ; // 前序遍历"AVL树"
void preOrder(AVLTreeNode<T>* tree) const;
// 中序遍历"AVL树"
void inOrder(AVLTreeNode<T>* tree) const;
// 后序遍历"AVL树"
void postOrder(AVLTreeNode<T>* tree) const; // (递归实现)查找"AVL树x"中键值为key的节点
AVLTreeNode<T>* search(AVLTreeNode<T>* x, T key) const;
// (非递归实现)查找"AVL树x"中键值为key的节点
AVLTreeNode<T>* iterativeSearch(AVLTreeNode<T>* x, T key) const; // 查找最小结点:返回tree为根结点的AVL树的最小结点。
AVLTreeNode<T>* minimum(AVLTreeNode<T>* tree);
// 查找最大结点:返回tree为根结点的AVL树的最大结点。
AVLTreeNode<T>* maximum(AVLTreeNode<T>* tree); // LL:左左对应的情况(左单旋转)。
AVLTreeNode<T>* leftLeftRotation(AVLTreeNode<T>* k2); // RR:右右对应的情况(右单旋转)。
AVLTreeNode<T>* rightRightRotation(AVLTreeNode<T>* k1); // LR:左右对应的情况(左双旋转)。
AVLTreeNode<T>* leftRightRotation(AVLTreeNode<T>* k3); // RL:右左对应的情况(右双旋转)。
AVLTreeNode<T>* rightLeftRotation(AVLTreeNode<T>* k1); // 将结点(z)插入到AVL树(tree)中
AVLTreeNode<T>* insert(AVLTreeNode<T>* &tree, T key); // 删除AVL树(tree)中的结点(z),并返回被删除的结点
AVLTreeNode<T>* remove(AVLTreeNode<T>* &tree, AVLTreeNode<T>* z); // 销毁AVL树
void destroy(AVLTreeNode<T>* &tree); // 打印AVL树
void print(AVLTreeNode<T>* tree, T key, int direction);
};

AVLTree是AVL树对应的类。它包含AVL树的根节点mRoot和AVL树的基本操作接口。需要说明的是:AVLTree中重载了许多函数。重载的目的是区分内部接口和外部接口,例如insert()函数而言,insert(tree, key)是内部接口,而insert(key)是外部。

1.3 树的高度

/*
* 获取树的高度
*/
template <class T>
int AVLTree<T>::height(AVLTreeNode<T>* tree)
{
if (tree != NULL)
return tree->height; return ;
} template <class T>
int AVLTree<T>::height()
{
return height(mRoot);
}

1.4 比较大小

/*
* 比较两个值的大小
*/
template <class T>
int AVLTree<T>::max(int a, int b)
{
return a>b ? a : b;
}

2. 旋转

如果在AVL树中进行插入或删除节点后,可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态:LL(左左),LR(左右),RR(右右)和RL(右左)。下面给出它们的示意图:

AVL树的实现——c++-LMLPHP

上图中的4棵树都是"失去平衡的AVL树",从左往右的情况依次是:LL、LR、RL、RR。除了上面的情况之外,还有其它的失去平衡的AVL树,如下图:

AVL树的实现——c++-LMLPHP

上面的两张图都是为了便于理解,而列举的关于"失去平衡的AVL树"的例子。总的来说,AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一,它们都由各自的定义:

(1) LL:LeftLeft,也称为"左左"。插入或删除一个节点后,根节点的左子树的左子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面LL情况中,由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(2) LR:LeftRight,也称为"左右"。插入或删除一个节点后,根节点的左子树的右子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面LR情况中,由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(3) RL:RightLeft,称为"右左"。插入或删除一个节点后,根节点的右子树的左子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面RL情况中,由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

(4) RR:RightRight,称为"右右"。插入或删除一个节点后,根节点的右子树的右子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面RR情况中,由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

3. 旋转对应的方法

3.1. LL的情况

LL失去平衡的情况,可以通过一次旋转让AVL树恢复平衡。如下图:

AVL树的实现——c++-LMLPHP

图中左边是旋转之前的树,右边是旋转之后的树。从中可以发现,旋转之后的树又变成了AVL树,而且该旋转只需要一次即可完成。
对于LL旋转,你可以这样理解为:LL旋转是围绕"失去平衡的AVL根节点"进行的,也就是节点k2;而且由于是LL情况,即左左情况,就用手抓着"左孩子,即k1"使劲摇。将k1变成根节点,k2变成k1的右子树,"k1的右子树"变成"k2的左子树"。

LL旋转代码:

/*
* LL:左左对应的情况(左单旋转)。
*
* 返回值:旋转后的根节点
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::leftLeftRotation(AVLTreeNode<T>* k2)
{
AVLTreeNode<T>* k1; k1 = k2->left;
k2->left = k1->right;
k1->right = k2; k2->height = max( height(k2->left), height(k2->right)) + ;
k1->height = max( height(k1->left), k2->height) + ; return k1;
}

3.2. RR的旋转

理解了LL之后,RR就相当容易理解了。RR是与LL对称的情况!RR恢复平衡的旋转方法如下:

AVL树的实现——c++-LMLPHP

图中左边是旋转之前的树,右边是旋转之后的树。RR旋转也只需要一次即可完成。

代码:

/*
* RR:右右对应的情况(右单旋转)。
*
* 返回值:旋转后的根节点
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::rightRightRotation(AVLTreeNode<T>* k1)
{
AVLTreeNode<T>* k2; k2 = k1->right;
k1->right = k2->left;
k2->left = k1; k1->height = max( height(k1->left), height(k1->right)) + ;
k2->height = max( height(k2->right), k1->height) + ; return k2;
}

3.3. LR的旋转

LR失去平衡的情况,需要经过两次旋转才能让AVL树恢复平衡。如下图:

AVL树的实现——c++-LMLPHP

第一次旋转是围绕"k1"进行的"RR旋转",第二次是围绕"k3"进行的"LL旋转"。

代码:

/*
* LR:左右对应的情况(左双旋转)。
*
* 返回值:旋转后的根节点
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::leftRightRotation(AVLTreeNode<T>* k3)
{
k3->left = rightRightRotation(k3->left); return leftLeftRotation(k3);
}

3.4. RL的旋转

RL是与LR的对称情况!RL恢复平衡的旋转方法如下:

AVL树的实现——c++-LMLPHP

第一次旋转是围绕"k3"进行的"LL旋转",第二次是围绕"k1"进行的"RR旋转"。

代码:

/*
* RL:右左对应的情况(右双旋转)。
*
* 返回值:旋转后的根节点
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::rightLeftRotation(AVLTreeNode<T>* k1)
{
k1->right = leftLeftRotation(k1->right); return rightRightRotation(k1);
}

4. 插入节点

/*
* 将结点插入到AVL树中,并返回根节点
*
* 参数说明:
* tree AVL树的根结点
* key 插入的结点的键值
* 返回值:
* 根节点
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::insert(AVLTreeNode<T>* &tree, T key)
{
if (tree == NULL)
{
// 新建节点
tree = new AVLTreeNode<T>(key, NULL, NULL);
if (tree==NULL)
{
cout << "ERROR: create avltree node failed!" << endl;
return NULL;
}
}
else if (key < tree->key) // 应该将key插入到"tree的左子树"的情况
{
tree->left = insert(tree->left, key);
// 插入节点后,若AVL树失去平衡,则进行相应的调节。
if (height(tree->left) - height(tree->right) == )
{
if (key < tree->left->key)
tree = leftLeftRotation(tree);
else
tree = leftRightRotation(tree);
}
}
else if (key > tree->key) // 应该将key插入到"tree的右子树"的情况
{
tree->right = insert(tree->right, key);
// 插入节点后,若AVL树失去平衡,则进行相应的调节。
if (height(tree->right) - height(tree->left) == )
{
if (key > tree->right->key)
tree = rightRightRotation(tree);
else
tree = rightLeftRotation(tree);
}
}
else //key == tree->key)
{
cout << "添加失败:不允许添加相同的节点!" << endl;
} tree->height = max( height(tree->left), height(tree->right)) + ; return tree;
} template <class T>
void AVLTree<T>::insert(T key)
{
insert(mRoot, key);
}

5. 删除节点

/*
* 删除结点(z),返回根节点
*
* 参数说明:
* tree AVL树的根结点
* z 待删除的结点
* 返回值:
* 根节点
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::remove(AVLTreeNode<T>* &tree, AVLTreeNode<T>* z)
{
// 根为空 或者 没有要删除的节点,直接返回NULL。
if (tree==NULL || z==NULL)
return NULL; if (z->key < tree->key) // 待删除的节点在"tree的左子树"中
{
tree->left = remove(tree->left, z);
// 删除节点后,若AVL树失去平衡,则进行相应的调节。
if (height(tree->right) - height(tree->left) == )
{
AVLTreeNode<T> *r = tree->right;
if (height(r->left) > height(r->right))
tree = rightLeftRotation(tree);
else
tree = rightRightRotation(tree);
}
}
else if (z->key > tree->key)// 待删除的节点在"tree的右子树"中
{
tree->right = remove(tree->right, z);
// 删除节点后,若AVL树失去平衡,则进行相应的调节。
if (height(tree->left) - height(tree->right) == )
{
AVLTreeNode<T> *l = tree->left;
if (height(l->right) > height(l->left))
tree = leftRightRotation(tree);
else
tree = leftLeftRotation(tree);
}
}
else // tree是对应要删除的节点。
{
// tree的左右孩子都非空
if ((tree->left!=NULL) && (tree->right!=NULL))
{
if (height(tree->left) > height(tree->right))
{
// 如果tree的左子树比右子树高;
// 则(01)找出tree的左子树中的最大节点
// (02)将该最大节点的值赋值给tree。
// (03)删除该最大节点。
// 这类似于用"tree的左子树中最大节点"做"tree"的替身;
// 采用这种方式的好处是:删除"tree的左子树中最大节点"之后,AVL树仍然是平衡的。
AVLTreeNode<T>* max = maximum(tree->left);
tree->key = max->key;
tree->left = remove(tree->left, max);
}
else
{
// 如果tree的左子树不比右子树高(即它们相等,或右子树比左子树高1)
// 则(01)找出tree的右子树中的最小节点
// (02)将该最小节点的值赋值给tree。
// (03)删除该最小节点。
// 这类似于用"tree的右子树中最小节点"做"tree"的替身;
// 采用这种方式的好处是:删除"tree的右子树中最小节点"之后,AVL树仍然是平衡的。
AVLTreeNode<T>* min = maximum(tree->right);
tree->key = min->key;
tree->right = remove(tree->right, min);
}
}
else
{
AVLTreeNode<T>* tmp = tree;
tree = (tree->left!=NULL) ? tree->left : tree->right;
delete tmp;
}
} return tree;
} template <class T>
void AVLTree<T>::remove(T key)
{
AVLTreeNode<T>* z; if ((z = search(mRoot, key)) != NULL)
mRoot = remove(mRoot, z);
}

本文来自http://www.cnblogs.com/skywang12345/p/3577360.html

05-11 23:03