DSQiu
- 浏览: 1397429 次
- 性别:
- 来自: 广州
-
文章分类
最新评论
-
sdgxxtc：
[quo[color=red]te][/color]
C#使用OleDb读取Excel，生成SQL语句 -
zcs302567601：
博主，你好，一直都有个问题没有搞明白，就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻：
感谢楼主！
有向强连通和网络流大讲堂——史无前例求解最大流（最小割）、最小费用最大流 -
cp1993518：
感谢！从你的博客里学到了很多
Unity日志工具——封装，跳转 -
cp1993518：
学习了~，话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
平衡二叉树（AVL）原理透析和编码解密
本文内容框架：
§1 AVL树定义
§2 AVL树平衡化旋转
§3 AVL树插入删除
§4 AVL树高度分析
§5 小结
§1 AVL树定义
1 AVL树的定义（附件上有完整的AVL树实现）
高度平衡的二叉搜索树
一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。
高度不平衡的二叉搜索树 高度平衡的二叉搜索树
结点的平衡因子balance (balance factor)
１、每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子balance 。
２、根据AVL树的定义，任一结点的平衡因子只能取 -1，0和 1。
３、如果一个结点的平衡因子的绝对值大于1，则这棵二叉搜索树就失去了平衡，不再是AVL树。
４、如果一棵二叉搜索树是高度平衡的，它就成为 AVL树。如果它有n个结点，其高度可保持在O(log2n)，平均搜索长度也可保持在O(log2n)。
AVL树的结点定义
#ifndef __BIN_TREE_NODE_H__
#define __BIN_TREE_NODE_H__
#define LH 1 // 左高
#define EH 0 // 等高
#define RH -1 // 右高
// 二叉平衡树结点类
template <class ElemType>
struct BinAVLTreeNode
{
// 数据成员:
ElemType data; // 数据域
int bf; // 结点的平衡因子
BinAVLTreeNode<ElemType> *leftChild; // 左孩子指针域
BinAVLTreeNode<ElemType> *rightChild; // 右孩子指针域
// 构造函数:
BinAVLTreeNode(); // 无参数的构造函数
BinAVLTreeNode(const ElemType &val, // 已知数据元素值,平衡因子和指向左右孩子的指针构造一个结点
int bFactor = 0,
BinAVLTreeNode<ElemType> *lChild = NULL,
BinAVLTreeNode<ElemType> *rChild = NULL);
};
// 二叉平衡树结点类的实现部分
template <class ElemType>
BinAVLTreeNode<ElemType>::BinAVLTreeNode()
// 操作结果：构造一个叶结点
{
bf = 0; // 平衡因子
leftChild = rightChild = NULL; // 叶结点左右孩子为空
}
template <class ElemType>
BinAVLTreeNode<ElemType>::BinAVLTreeNode(const ElemType &val, int bFactor,
BinAVLTreeNode<ElemType> *lChild,
BinAVLTreeNode<ElemType> *rChild)
// 操作结果：构造一个数据域为val,平衡因子为bFactor,左孩子为lChild,右孩子为rChild的结点
{
data = val; // 数据元素值
bf = bFactor; // 平衡因子
leftChild = lChild; // 左孩子
rightChild = rChild; // 右孩子
}
#endif
AVL树的类定义
#ifndef __BINNARY_TREE_H__
#define __BINNARY_TREE_H__
#include "lk_queue.h" // 链队列
#include "lk_stack.h" // 链栈
#include "bin_avl_tree_node.h" // 二叉平衡树结点类
enum StatusCode {SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR,
NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED};
// 二叉平衡树类
template <class ElemType, class KeyType>
class BinaryAVLTree
{
protected:
// 二叉平衡树的数据成员:
BinAVLTreeNode<ElemType> *root;
// 辅助函数:
BinAVLTreeNode<ElemType> *CopyTreeHelp(BinAVLTreeNode<ElemType> *copy); // 复制二叉平衡树
void DestroyHelp(BinAVLTreeNode<ElemType> * &r); // 销毁以r为根二叉平衡树
void PreOrderHelp(BinAVLTreeNode<ElemType> *r, void (*Visit)(const ElemType &)) const; // 先序遍历
void InOrderHelp(BinAVLTreeNode<ElemType> *r, void (*Visit)(const ElemType &)) const; // 中序遍历
void PostOrderHelp(BinAVLTreeNode<ElemType> *r, void (*Visit)(const ElemType &)) const; // 后序遍历
int HeightHelp(const BinAVLTreeNode<ElemType> *r) const; // 返回二叉平衡树的高
int NodeCountHelp(const BinAVLTreeNode<ElemType> *r) const;// 返回二叉平衡树的结点个数
BinAVLTreeNode<ElemType> *ParentHelp(BinAVLTreeNode<ElemType> *r,
const BinAVLTreeNode<ElemType> *cur) const; // 返回cur的双亲
BinAVLTreeNode<ElemType> *SearchHelp(const KeyType &key, BinAVLTreeNode<ElemType> *&f) const;
// 查找关键字为key的数据元素
BinAVLTreeNode<ElemType> *SearchHelp(const KeyType &key, BinAVLTreeNode<ElemType> *&f,
LinkStack<BinAVLTreeNode<ElemType> *> &s); // 返回指向关键字为key的元素的指针,用f返回其双亲
void LeftRotate(BinAVLTreeNode<ElemType> *&subRoot);
// 对以subRoot为根的二叉树作左旋处理,处理之后subRoot指向新的树根结点,也就是旋转处理前的右子
// 树的根结点
void RightRotate(BinAVLTreeNode<ElemType> *&subRoot);
// 对以subRoot为根的二叉树作右旋处理,处理之后subRoot指向新的树根结点,也就是旋转处理前的左子
// 树的根结点
void InsertLeftBalance(BinAVLTreeNode<ElemType> *&subRoot);
// 对以subRoot为根的二叉树插入时作左平衡处理,处理后subRoot指向新的树根结点
void InsertRightBalance(BinAVLTreeNode<ElemType> *&subRoot);
// 对以subRoot为根的二叉树插入时作右平衡处理,处理后subRoot指向新的树根结点
void InsertBalance(const ElemType &elem, LinkStack< BinAVLTreeNode<ElemType> *> &s);
// 从插入结点elem根据查找路径进行回溯,并作平衡处理
void DeleteLeftBalance(BinAVLTreeNode<ElemType> *&subRoot, bool &isShorter);
// 对以subRoot为根的二叉树删除时作左平衡处理,处理后subRoot指向新的树根结点
void DeleteRightBalance(BinAVLTreeNode<ElemType> *&subRoot, bool &isShorter);
// 对以subRoot为根的二叉树删除时作右平衡处理,处理后subRoot指向新的树根结点
void DeleteBalance(const KeyType &key, LinkStack<BinAVLTreeNode<ElemType> *> &s);
// 从删除结点根据查找路径进行回溯,并作平衡处理
void DeleteHelp(const KeyType &key, BinAVLTreeNode<ElemType> *&p,
LinkStack< BinAVLTreeNode<ElemType> *> &s); // 删除p指向的结点
public:
// 二叉平衡树方法声明及重载编译系统默认方法声明:
BinaryAVLTree(); // 无参数的构造函数
virtual ~BinaryAVLTree(); // 析构函数
BinAVLTreeNode<ElemType> *GetRoot() const; // 返回二叉平衡树的根
bool Empty() const; // 判断二叉平衡树是否为空
StatusCode GetElem(BinAVLTreeNode<ElemType> *cur, ElemType &e) const;
// 用e返回结点数据元素值
StatusCode SetElem(BinAVLTreeNode<ElemType> *cur, const ElemType &e);
// 将结cur的值置为e
void InOrder(void (*Visit)(const ElemType &)) const; // 二叉平衡树的中序遍历
void PreOrder(void (*Visit)(const ElemType &)) const; // 二叉平衡树的先序遍历
void PostOrder(void (*Visit)(const ElemType &)) const; // 二叉平衡树的后序遍历
void LevelOrder(void (*Visit)(const ElemType &)) const; // 二叉平衡树的层次遍历
int NodeCount() const; // 求二叉平衡树的结点个数
BinAVLTreeNode<ElemType> *Search(const KeyType &key) const;// 查找关键字为key的数据元素
bool Insert(const ElemType &e); // 插入数据元素e
bool Delete(const KeyType &key); // 删除关键字为key的数据元素
BinAVLTreeNode<ElemType> *LeftChild(const BinAVLTreeNode<ElemType> *cur) const;
// 返回二叉平衡树结点cur的左孩子
BinAVLTreeNode<ElemType> *RightChild(const BinAVLTreeNode<ElemType> *cur) const;
// 返回二叉平衡树结点cur的右孩子
BinAVLTreeNode<ElemType> *Parent(const BinAVLTreeNode<ElemType> *cur) const;
// 返回二叉平衡树结点cur的双亲
int Height() const; // 求二叉平衡树的高
BinaryAVLTree(const ElemType &e); // 建立以e为根的二叉平衡树
BinaryAVLTree(const BinaryAVLTree<ElemType, KeyType> ©); // 复制构造函数
BinaryAVLTree(BinAVLTreeNode<ElemType> *r); // 建立以r为根的二叉平衡树
BinaryAVLTree<ElemType, KeyType> &operator=(const BinaryAVLTree<ElemType, KeyType>& copy); // 赋值语句重载
};
§2 AVL树平衡化旋转
2 平衡化旋转
１、如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。
此时必须调整树的结构，使之平衡化。
２、平衡化旋转有两类：
３、每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。
４、如果在某一结点发现高度不平衡，停止回溯。
５、从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
６、 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。
７、如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
 |
 |
 |
 |
| 右单旋转 | 左单旋转 | 左右双旋转 | 右左双旋转 |
(1)如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。
(2)沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上，需要做左单旋转。
(3)以结点C为旋转轴，让结点A反时针旋转。
左单旋转的算法
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::LeftRotate(BinAVLTreeNode<ElemType> *&subRoot)
// 操作结果: 对以subRoot为根的二叉树作左旋处理,处理之后subRoot指向新的树根结点,
// 也就是旋转处理前的右子树的根结点
{
BinAVLTreeNode<ElemType> *ptrRChild;
ptrRChild = subRoot->rightChild; // ptrRChild指向subRoot右孩子
subRoot->rightChild = ptrRChild->leftChild; // ptrRChild的左子树链接为subRoot的右子树
ptrRChild->leftChild = subRoot; // subRoot链接为ptrRChild的左孩子
subRoot = ptrRChild; // subRoot指向新的根结点
}
(1)在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到 -2，造成了不平衡。
(2) 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。
(3) 以结点B为旋转轴，将结点A顺时针旋转。
右单旋转的算法
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::RightRotate(BinAVLTreeNode<ElemType> *&subRoot)
// 操作结果: 对以subRoot为根的二叉树作右旋处理,处理之后subRoot指向新的树根结点,
// 也就是旋转处理前的左子树的根结点
{
BinAVLTreeNode<ElemType> *pLChild;
pLChild = subRoot->leftChild; // pLChild指向subRoot左孩子
subRoot->leftChild = pLChild->rightChild; // pLChild的右子树链接为subRoot的左子树
pLChild->rightChild = subRoot; // subRoot链接为pLChild的右孩子
subRoot = pLChild; // subRoot指向新的根结点
}
(1)在子树F或G中插入新结点，该子树的高度增1。结点A的平衡因子变为 -2，发生了不平衡。
(2) 从结点A起沿插入路径选取3个结点A、B和E，它们位于一条形如“?”的折线上，因此需要进行先左后右的双旋转。
(3)首先以结点E为旋转轴，将结点B反时针旋转，以E代替原来B的位置，做左单旋转。
(4) 再以结点E为旋转轴，将结点A顺时针旋转，做右单旋转。使之平衡化。
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::InsertLeftBalance(BinAVLTreeNode<ElemType> *&subRoot)
// 操作结果: 对以subRoot为根的二叉树插入时作左平衡处理,插入结点在subRoot左子树上,处理后
// subRoot指向新的树根结点
{
BinAVLTreeNode<ElemType> *ptrLChild, *ptrLRChild;
ptrLChild = subRoot->leftChild; // ptrLChild指向subRoot左孩子
switch (ptrLChild->bf)
{ // 根据subRoot的左子树的平衡因子作相应的平衡处理
case LH: // 插入结点在subRoot的左孩子的左子树上,作单右旋处理
subRoot->bf = ptrLChild->bf = EH;// 平衡因子都为0
RightRotate(subRoot); // 右旋
break;
case RH: // 插入结点在subRoot的左孩子的右子树上,作先左旋后右旋处理
ptrLRChild = ptrLChild->rightChild;// ptrLRChild指向subRoot的左孩子的右子树的根
switch (ptrLRChild->bf)
{ // 修改subRoot及左孩子的平衡因子
case LH: // 插入结点在ptrLRChild的左子树上
subRoot->bf = RH;
ptrLChild->bf = EH;
break;
case EH: // 插入前ptrLRChild为空,ptrLRChild指向插入结点
subRoot->bf = ptrLChild->bf = EH;
break;
case RH: // 插入结点在ptrLRChild的左子树上
subRoot->bf = EH;
ptrLChild->bf = LH;
break;
}
ptrLRChild->bf = 0;
LeftRotate(subRoot->leftChild); // 对subRoot左子树作左旋处理
RightRotate(subRoot); // 对subRoot作右旋处理
}
}
(1)右左双旋转是左右双旋转的镜像。
(2) 在子树F或G中插入新结点，该子树高度增1。结点A的平衡因子变为2，发生了不平衡。
(3) 从结点A起沿插入路径选取3个结点A、C和D，它们位于一条形如“?”的折线上，需要进行先右后左的双旋转。
(4)首先做右单旋转：以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置。
(5) 再做左单旋转：以结点D为旋转轴，将结点A反时针旋转，恢复树的平衡。
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::InsertRightBalance(BinAVLTreeNode<ElemType> *&subRoot)
// 操作结果: 对以subRoot为根的二叉树插入时作右平衡处理,插入结点在subRoot左子树上,处理后
// subRoot指向新的树根结点
{
BinAVLTreeNode<ElemType> *ptrRChild, *ptrRLChild;
ptrRChild = subRoot->rightChild; // ptrRChild指向subRoot右孩子
switch (ptrRChild->bf)
{ // 根据subRoot的右子树的平衡因子作相应的平衡处理
case RH: // 插入结点在subRoot的右孩子的右子树上,作单左旋处理
subRoot->bf = ptrRChild->bf = EH;// 平衡因子都为0
LeftRotate(subRoot); // 左旋
break;
case LH: // 插入结点在subRoot的右孩子的左子树上,作先右旋后左旋处理
ptrRLChild = ptrRChild->leftChild;// ptrRLChild指向subRoot的右孩子的左子树的根
switch (ptrRLChild->bf)
{ // 修改subRoot及右孩子的平衡因子
case RH: // 插入结点在ptrRLChild的右子树上
subRoot->bf = LH;
ptrRChild->bf = EH;
break;
case EH: // 插入前ptrRLChild为空,ptrRLChild指向插入结点
subRoot->bf = ptrRChild->bf = EH;
break;
case LH: // 插入结点在ptrRLChild的左子树上
subRoot->bf = EH;
ptrRChild->bf = RH;
break;
}
ptrRLChild->bf = 0;
RightRotate(subRoot->rightChild);// 对subRoot右子树作右旋处理
LeftRotate(subRoot); // 对subRoot作左旋处理
}
}
§3 AVL树插入删除
3 AVL树的插入和删除
1、在向一棵本来是高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值 |balance| > 1，则出现了不平衡，需要做平衡化处理。
2、在AVL树上定义了重载操作“>>”和“<<”，以及中序遍历的算法。利用这些操作可以执行AVL树的建立和结点数据的输出。
3、 算法从一棵空树开始，通过输入一系列对象的关键码，逐步建立AVL树。在插入新结点时使用了前面所给的算法进行平衡旋转。
例，输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和调整过程如下。
1、下面的算法将通过递归方式将新结点作为叶结点插入并逐层修改各结点的平衡因子。
2、 在发现不平衡时立即执行相应的平衡化旋转操作，使得树中各结点重新平衡化。
3、 在程序中，用变量success记载新结点是否存储分配成功，并用它作为函数的返回值。
4、算法从树的根结点开始，递归向下找插入位置。在找到插入位置(空指针)后，为新结点动态分配存储空间，将它作为叶结点插入，并置success为1，再将taller置为1，以表明插入成功。在退出递归沿插入路径向上返回时做必要的调整。
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::InsertBalance(const ElemType &e,
LinkStack<BinAVLTreeNode<ElemType> *> &s)
// 操作结果: 从插入元素e根据查找路径进行回溯,并作平衡处理
{
bool isTaller = true;
while (!s.Empty() && isTaller)
{
BinAVLTreeNode<ElemType> *ptrCurNode, *ptrParent;
s.Pop(ptrCurNode); // 取出待平衡的结点
if (s.Empty())
{ // ptrCurNode已为根结点,ptrParent为空
ptrParent = NULL;
}
else
{ // ptrCurNode不为根结点,取出双亲ptrParent
s.Top(ptrParent);
}
if (e < ptrCurNode->data)
{ // e插入在ptrCurNode的左子树上
switch (ptrCurNode->bf)
{ // 检查ptrCurNode的平衡度
case LH: // 插入后ptrCurNode->bf=2, 作左平衡处理
if (ptrParent == NULL)
{ // 已回溯到根结点
InsertLeftBalance(ptrCurNode);
root = ptrCurNode; // 转换后ptrCurNode为新根
}
else if (ptrParent->leftChild == ptrCurNode)
{ // ptrParent左子树作平衡处理
InsertLeftBalance(ptrParent->leftChild);
}
else
{ // ptrParent右子树作平衡处理
InsertLeftBalance(ptrParent->rightChild);
}
isTaller = false;
break;
case EH: // 插入后ptrCurNode->bf=LH
ptrCurNode->bf = LH;
break;
case RH: // 插入后ptrCurNode->bf=EH
ptrCurNode->bf = EH;
isTaller = false;
break;
}
}
else
{ // e插入在ptrCurNode的右子树上
switch (ptrCurNode->bf)
{ // 检查ptrCurNode的平衡度
case RH: // 插入后ptrCurNode->bf=-2, 作右平衡处理
if (ptrParent == NULL)
{ // 已回溯到根结点
InsertRightBalance(ptrCurNode);
root = ptrCurNode; // 转换后ptrCurNode为新根
}
else if (ptrParent->leftChild == ptrCurNode)
{ // ptrParent左子树作平衡处理
InsertRightBalance(ptrParent->leftChild);
}
else
{ // ptrParent右子树作平衡处理
InsertRightBalance(ptrParent->rightChild);
}
isTaller = false;
break;
case EH: // 插入后ptrCurNode->bf=RH
ptrCurNode->bf = RH;
break;
case LH: // 插入后ptrCurNode->bf=EH
ptrCurNode->bf = EH;
isTaller = false;
break;
}
}
}
}
template <class ElemType, class KeyType>
bool BinaryAVLTree<ElemType, KeyType>::Insert(const ElemType &e)
// 操作结果: 插入数据元素e
{
BinAVLTreeNode<ElemType> *f;
LinkStack< BinAVLTreeNode<ElemType> *> s;
if (SearchHelp(e, f, s) == NULL)
{ // 查找失败, 插入成功
BinAVLTreeNode<ElemType> *p; // 插入的新结点
p = new BinAVLTreeNode<ElemType>(e);// 生成插入结点
p->bf = 0;
if (Empty())
{ // 空二叉树,新结点为根结点
root = p;
}
else if (e < f->data)
{ // e更小,插入结点为f的左孩子
f->leftChild = p;
}
else
{ // e更大,插入结点为f的右孩子
f->rightChild = p;
}
InsertBalance(e, s);// 插入结点后作平衡处理
return true;
}
else
{ // 查找成功, 插入失败
return false;
}
}
１、如果被删结点x最多只有一个子女，那么问题比较简单。如果被删结点x有两个子女，首先搜索 x 在中序次序下的直接前驱 y (同样可以找直接后继)。再把 结点y 的内容传送给结点x，现在问题转移到删除结点 y。 把结点y当作被删结点x。
２、 将结点x从树中删去。因为结点x最多有一个子女，我们可以简单地把x的双亲结点中原来指向x的指针改指到这个子女结点；如果结点x没有子女，x双亲结点的相应指针置为NULL。然后将原来以结点x为根的子树的高度减1，
３、必须沿x通向根的路径反向追踪高度的变化对路径上各个结点的影响。
４、 用一个布尔变量 shorter 来指明子树的高度是否被缩短。在每个结点上要做的操作取决于 shorter 的值和结点的 balance，有时还要依赖子女的 balance 。
５、 布尔变量 shorter 的值初始化为True。然后对于从 x 的双亲到根的路径上的各个结点 p，在 shorter 保持为 True 时执行下面的操作。如果 shorter 变成False，算法终止。
６、case 1 : 当前结点p的balance为0。如果它的左子树或右子树被缩短，则它的 balance改为1或-1，同时 shorter 置为False。
７、case 2 : 结点p的balance不为0，且较高的子树被缩短，则p的balance改为0，同时 shorter 置为True。
８、case 3 : 结点p的balance不为0，且较矮的子树又被缩短，则在结点p发生不平衡。需要进行平衡化旋转来恢复平衡。令p的较高的子树的根为 q (该子树未被缩短)，根据q的balance ，有如下3种平衡化操作。
９、case 3a : 如果q的balance为0，执行一个单旋转来恢复结点p的平衡，置shorter为False。
１０、 case 3b : 如果q的balance与p的balance相同，则执行一个单旋转来恢复平衡，结点p和q的balance均改为0，同时置shorter为True。
１１、case 3c : 如果p与q的balance相反，则执行一个双旋转来恢复平衡，先围绕 q 转再围绕 p 转。新的根结点的balance置为0，其它结点的balance相应处理，同时置shorter为True。
１２、 在case 3a, 3b和3c的情形中，旋转的方向取决于是结点p的哪一棵子树被缩短。
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::DeleteLeftBalance(BinAVLTreeNode<ElemType> *&
subRoot, bool &isShorter)
// 操作结果: 对以subRoot为根的二叉树删除时作左平衡处理, 删除subRoot的左子树上的结点，处
// 理后subRoot指向新的树根结点
{
BinAVLTreeNode<ElemType> *ptrRChild, *ptrRLChild;
ptrRChild = subRoot->rightChild; // ptrRChild指向subRoot右孩子
switch (ptrRChild->bf)
{ // 根据subRoot的右子树的平衡因子作相应的平衡处理
case RH: // 右高，作单左旋转
subRoot->bf = ptrRChild->bf = EH; // 平衡因子都为0
LeftRotate(subRoot); // 左旋
isShorter = true;
break;
case EH: // 等高，作单左旋转
subRoot->bf = RH;
ptrRChild->bf = LH;
LeftRotate(subRoot); // 左旋
isShorter = false;
break;
case LH: // 左高,先右旋后左旋
ptrRLChild = ptrRChild->leftChild; // ptrRLChild指向subRoot的右孩子的左子树的根
switch (ptrRLChild->bf)
{ // 修改subRoot及右孩子的平衡因子
case LH:
subRoot->bf = EH;
ptrRChild->bf = RH;
isShorter = true;
break;
case EH:
subRoot->bf = ptrRChild->bf = EH;
isShorter = false;
break;
case RH:
subRoot->bf = LH;
ptrRChild->bf = EH;
isShorter = true;
break;
}
ptrRLChild->bf = 0;
RightRotate(subRoot->rightChild); // 对subRoot右子树作右旋处理
LeftRotate(subRoot); // 对subRoot作左旋处理
}
}
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::DeleteRightBalance(BinAVLTreeNode<ElemType> *
&subRoot, bool &isShorter)
// 操作结果: 对以subRoot为根的二叉树删除时作右平衡处理, 删除subRoot的右子树上的结点，处
// 理后subRoot指向新的树根结点
{
BinAVLTreeNode<ElemType> *ptrLChild, *ptrLRChild;
ptrLChild = subRoot->leftChild; // ptrLChild指向subRoot左孩子
switch (ptrLChild->bf)
{ // 根据subRoot的左子树的平衡因子作相应的平衡处理
case LH: // 右高，作单右旋转
subRoot->bf = ptrLChild->bf = EH;// 平衡因子都为0
RightRotate(subRoot); // 右旋
isShorter = true;
break;
case EH: // 等高，作单右旋转
subRoot->bf = LH;
ptrLChild->bf = RH; // 平衡因子都为0
RightRotate(subRoot); // 右旋
isShorter = false;
break;
case RH: // 左高,先左旋后右旋
ptrLRChild = ptrLChild->rightChild;// ptrLRChild指向subRoot的左孩子的右子树的根
switch (ptrLRChild->bf)
{ // 修改subRoot及左孩子的平衡因子
case LH:
subRoot->bf = RH;
ptrLChild->bf = EH;
isShorter = true;
break;
case EH:
subRoot->bf = ptrLChild->bf = EH;
isShorter = false;
break;
case RH:
subRoot->bf = EH;
ptrLChild->bf = LH;
isShorter = true;
break;
}
ptrLRChild->bf = 0;
LeftRotate(subRoot->leftChild); // 对subRoot左子树作左旋处理
RightRotate(subRoot); // 对subRoot作右旋处理
}
}
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::DeleteBalance(const KeyType &key,
LinkStack<BinAVLTreeNode<ElemType> *> &s)
// 操作结果: 从删除结点根据查找路径进行回溯,并作平衡处理
{
bool isShorter = true;
while (!s.Empty() && isShorter)
{
BinAVLTreeNode<ElemType> *ptrCurNode, *ptrParent;
s.Pop(ptrCurNode); // 取出待平衡的结点
if (s.Empty())
{ // ptrCurNode已为根结点,ptrParent为空
ptrParent = NULL;
}
else
{ // ptrCurNode不为根结点,取出双亲ptrParent
s.Top(ptrParent);
}
if (key < ptrCurNode->data)
{ // 删除ptrCurNode的左子树上的结点
switch (ptrCurNode->bf)
{ // 检查ptrCurNode的平衡度
case LH: // 左高
ptrCurNode->bf = EH;
break;
case EH: // 等高
ptrCurNode->bf = RH;
isShorter = false;
break;
case RH: // 右高
if (ptrParent == NULL)
{ // 已回溯到根结点
DeleteLeftBalance(ptrCurNode, isShorter);
root = ptrCurNode; // 转换后ptrCurNode为新根
}
else if (ptrParent->leftChild == ptrCurNode)
{ // ptrParent左子树作平衡处理
DeleteLeftBalance(ptrParent->leftChild, isShorter);
}
else
{ // ptrParent右子树作平衡处理
DeleteLeftBalance(ptrParent->rightChild, isShorter);
}
break;
}
}
else
{ // 删除ptrCurNode的右子树上的结点
switch (ptrCurNode->bf)
{ // 检查ptrCurNode的平衡度
case RH: // 右高
ptrCurNode->bf = EH;
break;
case EH: // 等高
ptrCurNode->bf = LH;
isShorter = false;
break;
case LH: // 左高
if (ptrParent == NULL)
{ // 已回溯到根结点
DeleteLeftBalance(ptrCurNode, isShorter);
root = ptrCurNode; // 转换后ptrCurNode为新根
}
else if (ptrParent->leftChild == ptrCurNode)
{ // ptrParent左子树作平衡处理
DeleteLeftBalance(ptrParent->leftChild, isShorter);
}
else
{ // ptrParent右子树作平衡处理
DeleteLeftBalance(ptrParent->rightChild, isShorter);
}
break;
}
}
}
}
template <class ElemType, class KeyType>
void BinaryAVLTree<ElemType, KeyType>::DeleteHelp(const KeyType &key,
BinAVLTreeNode<ElemType> *&p, LinkStack< BinAVLTreeNode<ElemType> *> &s)
// 操作结果: 删除p指向的结点
{
BinAVLTreeNode<ElemType> *tmpPtr, *tmpF;
if (p->leftChild == NULL && p->rightChild == NULL)
{ // p为叶结点
delete p;
p = NULL;
DeleteBalance(key, s);
}
else if (p->leftChild == NULL)
{ // p只有左子树为空
tmpPtr = p;
p = p->rightChild;
delete tmpPtr;
DeleteBalance(key, s);
}
else if (p->rightChild == NULL)
{ // p只有右子树非空
tmpPtr = p;
p = p->leftChild;
delete tmpPtr;
DeleteBalance(key, s);
}
else
{ // p左右子非空
tmpF = p;
s.Push(tmpF);
tmpPtr = p->leftChild;
while (tmpPtr->rightChild != NULL)
{ // 查找p在中序序列中直接前驱tmpPtr及其双亲tmpF,tmpPtr无右子树为空
tmpF = tmpPtr;
s.Push(tmpF);
tmpPtr = tmpPtr->rightChild;
}
p->data = tmpPtr->data;// 将tmpPtr指向结点的元素值赋值给tmpF指向结点的元素值
// 删除tmpPtr指向的结点
if (tmpF->rightChild == tmpPtr)
{ // 删除tmpF的右孩子
DeleteHelp(key, tmpF->rightChild, s);
}
else
{ // 删除tmpF的左孩子
DeleteHelp(key, tmpF->leftChild, s);
}
}
}
template <class ElemType, class KeyType>
bool BinaryAVLTree<ElemType, KeyType>::Delete(const KeyType &key)
// 操作结果: 删除关键字为key的结点
{
BinAVLTreeNode<ElemType> *p, *f;
LinkStack< BinAVLTreeNode<ElemType> *> s;
p = SearchHelp(key, f, s);
if ( p == NULL)
{ // 查找失败, 删除失败
return false;
}
else
{ // 查找成功, 插入失败
if (f == NULL)
{ // 被删除结点为根结点
DeleteHelp(key, root, s);
}
else if (key < f->data)
{ // key更小,删除f的左孩子
DeleteHelp(key, f->leftChild, s);
}
else
{ // key更大,插入f的右孩子
DeleteHelp(key, f->rightChild, s);
}
return true;
}
}
§4 AVL树高度分析
4 AVL树的高度分析
１、设在新结点插入前AVL树的高度为h，结点个数为n，则插入一个新结点的时间是O(h)。对于AVL树来说，h多大？
２、设 Nh 是高度为 h 的AVL树的最小结点数。根的一棵子树的高度为 h-1，另一棵子树的高度为 h-2，这两棵子树也是高度平衡的。因此有 N-1 = 0 (空树) N0 = 1 (仅有根结点) Nh = Nh-1 + Nh-2 +1 , h > 0
３、可以证明，对于 h 不等于 0，有 Nh = Fh+3 -1 成立。
４、有n个结点的AVL树的高度不超过 
５、在AVL树删除一个结点并做平衡化旋转所需时间为 O(log2n)。
６、 二叉搜索树适合于组织在内存中的较小的索引(或目录)。对于存放在外存中的较大的文件系统，用二叉搜索树来组织索引不太合适。
７、 在文件检索系统中大量使用的是用B_树或B+树做文件索引。
§5 小结
本篇博文已经详细讲解了AVL树数据结构的所有内容，可以说是及其详尽，网络上史无前例，应该可以有一个深入的了解（附件是完成的代码实现）。如果你有任何建议或者批评和补充，请留言指出，不胜感激，更多参考请移步互联网。
参考：
①http://www.nctvu.cn/kejian/sjjg/7.6.htm
②唐宁九等： 数据结构与算法（C++版）
- AVL完整实现.zip (11.6 KB)
- 下载次数: 9
1
顶
顶
0
踩
踩
分享到：
发表评论
-
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3477在C# 调用Delegate.Create ... -
数组问题集结号
2012-12-06 22:01 0数组是最简单的数据结构，数组问题作为公司招聘的笔试和面试题目 ... -
算法问题分析笔记
2012-12-05 11:59 01.Crash Balloon Zhejiang Univer ... -
Java基础进阶整理
2012-11-26 09:59 2259Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2572《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法（BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4033尊重他人的劳动，支持原创 本篇博文，D.S.Q ... -
基本技术——贪心法、分治法、动态规划三大神兵
2012-11-03 19:30 0基本技术——贪心法、分治法、动态规划三大神兵 -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:12 35489优先队列三大利器——二项堆、斐波那契堆、Pairing ... -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:01 3优先队列三大利器——二项堆、斐波那契堆、Pairing 堆 ... -
排序算法群星豪华大汇演
2012-10-30 00:09 3030排序算法群星豪华大汇演 排序算法相对简单些，但是由于 ... -
分布排序（distribution sorts）算法大串讲
2012-10-29 15:33 4568分布排序（distribution sorts）算法大串讲 ... -
归并排序（merge sorts）算法大串讲
2012-10-29 10:04 8219归并排序（merge sorts）算法大串讲 ... -
交换排序（exchange sorts）算法大串讲
2012-10-29 00:22 4309交换排序（exchange sorts）算法大串讲 本 ... -
选择排序（selection sorts）算法大串讲
2012-10-28 12:55 3596选择排序（selection sorts）算法大串讲 本文内 ... -
插入排序（insertion sorts）算法大串讲
2012-10-28 11:30 2650插入排序（insertion sorts ... -
伸展树（Splay Tree）尽收眼底
2012-10-27 15:11 5411伸展树（Splay Tree）尽收眼底 本文内容 ... -
红黑树（Red-Black Tree）不在话下
2012-10-26 20:54 2121红黑树（Red-Black Tree） 红黑树定义 红黑树 ...
相关推荐
AVL管理数据 struct branch{ unsigned int data; /* actual data */ struct branch * l_chld, * r_chld; /* left & right child */ short bc; /* balance coefficient */ }; #define avl_entry (T, P, M) (T *)...
二叉树的应用：二叉排序树BST和平衡二叉树AVL的构造实验报告
java数据结构与算法之平衡二叉树AVL树的设计与实现分析.doc
NULL 博文链接：https://709002341.iteye.com/blog/2258678
将平衡二叉树的增删改查集成到了一起，提供友好的界面。
平衡二叉树（Balanced Binary Tree）又被称为AVL树。具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法。 实验目的： 二叉排序树的实现...
查找算法，平衡二叉树，大话数据结构里面的。
平衡二叉树Java实现，平衡二叉树Java实现，平衡二叉树Java实现，平衡二叉树Java实现，
首先实现BST二叉搜索树，在BST的基础上做出AVL树，有插入、删除、查询、调整平衡的功能，而且可以和BST比较的过程。By Michael Zhou
用JAVASCRIPT+VML实现平衡二叉树里增加节点删除节点的功能，目的是把二叉树的平衡算法记录在这里（备忘）。 目前只做了增加删除节点时二叉树自动平衡，保证这棵树什么时候都是平衡状态；如何将一棵不平衡的二叉树...
关于平衡二叉树的学习笔记，并提供二叉树平衡、插入及删除的代码、提供一个简单的打印二叉树结构的函数（打印对齐不是很好），方便代码调试。
主要介绍了平衡二叉树AVL操作模板,需要的朋友可以参考下
本程序封装了平衡二叉树（AVL）的基本操作，实现了非递归插入，删除 查找的基本操作。测试通过了一些极端情况，并通过测试。尚未发现的bug，欢迎指正。
2015广工数据结构实验--平衡二叉树(包含源码和实验报告
主要介绍了C语言数据结构之平衡二叉树（AVL树）实现方法,结合实例形式分析了C语言平衡二叉树的相关定义与使用技巧,需要的朋友可以参考下
平衡二叉树，AVL算法，c++实现..................
平衡二叉树c++模版，此模版採用二叉链表实现，是本人一个通宵搞出来的。可以提供时间复杂度在nlgn的排序，也可以提供lgn的查询。是一个很不错的数据结构，可是以和其它的现在比较新的一些数据结构比美。虽然有人对其...
二叉树和平衡二叉树(B树)的C#实现源码 二叉树和平衡二叉树(B树)的C#实现源码 二叉树和平衡二叉树(B树)的C#实现源码