AVL树的复杂程度真是比二叉搜索树高了整整一个数量级——它的原理并不难弄懂,但要把它用代码实现出来还真的有点费脑筋。下面我们来看看:
AVL树本质上还是一棵二叉搜索树(因此读者可以看到我后面的代码是继承自二叉搜索树的),它的特点是:
-
本身首先是一棵二叉搜索树。
-
带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。
例如:
5 5
/ \ / \
2 6 2 6
/ \ \ / \
1 4 7 1 4
/ /
3 3
上图中,左边的是AVL树,而右边的不是。因为左边的树的每个结点的左右子树的高度之差的绝对值都最多为1,而右边的树由于结点6没有子树,导致根结点5的平衡因子为2。
有人也许要问:为什么要有AVL树呢?它有什么作用呢?
我们先来看看二叉搜索树吧(因为AVL树本质上是一棵二叉搜索树),假设有这么一种极端的情况:二叉搜索树的结点为1、2、3、4、5,也就是:
1
\
2
\
3
\
4
\
5
聪明的你是不是发现什么了呢?呵呵,显而易见——这棵二叉搜索树其实等同于一个链表了,也就是说,它在查找上的优势已经全无了——在这种情况下,查找一个结点的时间复杂度是O(N)!
好,那么假如是AVL树(别忘了AVL树还是二叉搜索树),则会是:
2
/ \
1 4
/ \
3 5
可以看出,AVL树的查找平均时间复杂度要比二叉搜索树低——它是O(logN)。也就是说,在大量的随机数据中AVL树的表现要好得多。
假设有一个结点的平衡因子为2(在AVL树中,最大就是2,因为结点是一个一个地插入到树中的,一旦出现不平衡的状态就会立即进行调整,因此平衡因子最大不可能超过2),那么就需要进行调整。由于任意一个结点最多只有两个儿子,所以当高度不平衡时,只可能是以下四种情况造成的:
-
对该结点的左儿子的左子树进行了一次插入。
-
对该结点的左儿子的右子树进行了一次插入。
-
对该结点的右儿子的左子树进行了一次插入。
-
对该结点的右儿子的右子树进行了一次插入。
情况1和4是关于该点的镜像对称,同样,情况2和3也是一对镜像对称。因此,理论上只有两种情况,当然了,从编程的角度来看还是四种情况。
第一种情况是插入发生在“外边”的情况(即左-左的情况或右-右的情况),该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况(即左-右的情况或右-左的情况),该情况要通过稍微复杂些的双旋转来处理。
关于旋转的具体理论分析和例子请参阅教科书,我实在不想在这里重新打一次了……就此省略65535个字,原谅我吧,出来混,迟早要还的。
二叉树的代码实现如下:
#ifndef __AVL_TREE_H__
#define __AVL_TREE_H__
#include "../../bstree/src/bstree.h"
template<typename T>
class CAVLTree : public CBSTree<T>
{
private:
CBTNode<T>* Insert(const T &data, CBTNode<T> *p);
public:
CBTNode<T>* SingleRotateWithLeft(CBTNode<T> *p);
CBTNode<T>* DoubleRotateWithLeft(CBTNode<T> *p);
CBTNode<T>* SingleRotateWithRight(CBTNode<T> *p);
CBTNode<T>* DoubleRotateWithRight(CBTNode<T> *p);
CBTNode<T>* Insert(const T &data);
CBTNode<T>* Delete(const T &data);
};
template<typename T>
inline CBTNode<T>* CAVLTree<T>::SingleRotateWithLeft(CBTNode<T> *p)
{
CBTNode<T> *p2;
p2 = p->left;
p->left = p2->right;
p2->right = p;
p2->parent = p->parent;
p->parent = p2;
if (p->left)
p->left->parent = p;
if (p == m_pNodeRoot)
m_pNodeRoot = p2;
return p2;
}
template<typename T>
inline CBTNode<T>* CAVLTree<T>::DoubleRotateWithLeft(CBTNode<T> *p)
{
p->left = SingleRotateWithLeft(p->left);
return SingleRotateWithLeft(p);
}
template<typename T>
inline CBTNode<T>* CAVLTree<T>::SingleRotateWithRight(CBTNode<T> *p)
{
CBTNode<T> *p2;
p2 = p->right;
p->right = p2->left;
p2->left = p;
p2->parent = p->parent;
p->parent = p2;
if (p->right)
p->right->parent = p;
if (p == m_pNodeRoot)
m_pNodeRoot = p2;
return p2;
}
template<typename T>
inline CBTNode<T>* CAVLTree<T>::DoubleRotateWithRight(CBTNode<T> *p)
{
p->right = SingleRotateWithLeft(p->right);
return SingleRotateWithRight(p);
}
template<typename T>
inline CBTNode<T>* CAVLTree<T>::Insert(const T &data)
{
return Insert(data, m_pNodeRoot);
}
template<typename T>
inline CBTNode<T>* CAVLTree<T>::Insert(const T &data, CBTNode<T> *p)
{
if (NULL == p)
{
p = new CBTNode<T>;
if (NULL == p)
return NULL;
else
{
p->data = data;
p->left = NULL;
p->right = NULL;
if (NULL == m_pNodeRoot)
{
m_pNodeRoot = p;
m_pNodeRoot->parent = NULL;
}
}
}
else if (data < p->data)
{
p->left = Insert(data, p->left);
if (p->left)
p->left->parent = p;
if (2 == (GetDepth(p->left) - GetDepth(p->right)))
{
if (data < p->left->data)
p = SingleRotateWithLeft(p);
else
p = DoubleRotateWithLeft(p);
}
}
else if (data > p->data)
{
p->right = Insert(data, p->right);
if (p->right)
p->right->parent = p;
if (2 == (GetDepth(p->right) - GetDepth(p->left)))
{
if (data > p->right->data)
p = SingleRotateWithRight(p);
else
p = DoubleRotateWithRight(p);
}
}
return p;
}
template<typename T>
inline CBTNode<T>* CAVLTree<T>::Delete(const T &data)
{
return NULL;
}
#endif
测试代码:
#include "avltree.h"
int main()
{
CAVLTree<int> avltree;
#ifdef _DEBUG
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif
avltree.Insert(1);
avltree.Insert(2);
avltree.Insert(3);
avltree.Insert(4);
}
我的AVL树是从二叉搜索树继承而来的(还记得我的二叉搜索树又是从二叉树继承来的吗?^_^)。另外,由于水平的关系,我没有写出Delete()函数来,因此如果您使用了Delete(),那是不会有效果的。-_-b...
插入的核心思路是通过递归(又是递归!)找到合适的位置,插入新结点,然后看新结点是否平衡(平衡因子是否为2),如果不平衡的话,就分成两种大情况以及两种小情况:
-
在结点的左儿子(data < p->data)
-
在结点的右儿子(data > p->data)
代码已经写得很清楚了,我就不多废话了,关键在于动手去调试,这样才能弄明白。值得说明的是,当进行了旋转之后,必定会有结点的“父结点”是需要更新的,例如:
2
/ \
1 4
/ \
3 5
\
6
上图是调整前的,下图是调整后的:
4
/ \
2 5
/ \ \
1 3 6
可以看出,根结点2不平衡,是由于它的右儿子的右子树插入了新的结点6造成的。因此,这属于“外边”的情况,要进行一次单旋转。于是我们就把结点4调整上来作为根结点,再把结点2作为4的左儿子,最后把结点2的右儿子修改为原来的结点4的左儿子。
调整后的parent指针变化规律如下:
-
调整前的右儿子(调整后它就变为父亲了)的parent指针应该指向调整前的父亲(调整后它就变成左儿子了)的parent指针。
-
调整前的父亲(调整后它就变成左儿子了)的parent指针应该指向调整前的右儿子(调整后它就变成父亲了)。
-
调整前的父亲的右儿子的parent指针应该指向调整前的右儿子的左儿子。
很难理解是吗?我来联系到上图说明:
-
调整前的右儿子是结点4,调整后,它的parent指针应该指向调整前它的父亲的parent指针,也就是NULL,因为调整前结点4的父亲是结点2,而结点2是根结点,其parent指针为NULL。
-
调整前的父亲是结点2,调整后,它的parent指针应该指向调整前的右儿子(结点4)。
-
调整前的父亲的右儿子(也就是调整后的结点2的右儿子)应该指向调整前的右儿子(结点4)的左儿子(结点3)。
这是SingleRotateWithRight()里面对parent指针的处理,SingleRotateWithLeft()里面的道理也是相通的,只是顺序有点不同。
呵呵,希望没把您弄晕。^_^
AVL树就讲到这里了,如果您有兴趣,可以把Delete()函数写完,并请给我一份以便我学习。
分享到:
相关推荐
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
AVL 树是一种平衡二叉搜索树,AVL 树有一个特点,所有节点的平衡因子不能大于 1,即所有节点的左子树与右子树的深度差只能为-1,0,1。根据这个概念,判断 AVL 树 就是去判断一棵二叉树是否是二叉搜索树,并且是否...
红黑树和AVL树的代码实现,并显示树的形状,同时红黑树还可以输出个路径以及黑高度
数据结构课程设计 图像化界面演示AVL树的插入、删除、查找操作,支持旋转的单步和自动演示
AVL树的简介,方便初学的读者了解AVL树。
数据结构中avl树的实现,包含avl树的插入,删除节点,并以括号表示法输出结果
AVL树的C语言实现
AVL树 平衡二叉树 的各种方法:查找、删除、插入等
学习AVL树的算法实现,使用c++在vc6.0中进行相应的算法实现,对正在学习算法的孩子有帮助
包括插入,删除等操作的AVL树,C++实现
这两个源文件主要实现了基于C++语言编写的AVL树,将AVL树的所有操作都实现了。测试平台为Linux,现将AVL树的源码奉上。
该程序通过C++实现了AVL树的一些基础操作:1.编写AVL树判别程序,并判别一个二叉搜索树是否为AVL树;2.实现AVL树的ADT,包括其上的基本操作:结点的加入和删除;3.实现基本操作的动态演示(图形演示);最重要的是,该...
AVL树的删除程序,包括完整的源代码和可执行程序
对输入的avl树判断其是否为avl树,并在其上插入删除元素,并把二叉查找树转换为avl树
利用avl树实现hash表,自测通过。下载代码直接编译,即可运行。
这个头文件里实现了AVL树的建立、左单旋转、右单旋转、双旋转的功能,还有输出AVL的功能。
讲述数据结构中的AVL树的生成,查询,删除插入等操作,完美的数据结构课程设计,拥有试验程序和实验报告,值得拥有。
数据结构中的avl树 c++的具体实现 实现思想是先对输入的数据进行排序,然后进行处理 主要是对北大上机的
avl树的实现: avl树是每个节点的左子树和右子树的高度最多差1的二叉查找树.一棵高度为h的avl树最少节点数由S(h) = S(h-1)+S(h-2)+1得到.avl树要保证任一节点的左右子树的高度之差的绝对值不能超过1(空树的高定义为1...
详细完整的AVL树C++源代码,其中还包括预定义的栈、队列和标准二叉树类。