【1】为什么需要平衡二叉树？
矛盾是推进事物向前发展的源动力。
那么平衡二叉树是从哪里来？肯定是有矛盾存在的。请看下面的分析：
【2】什么是平衡二叉树？
平衡二叉树的基本认识：
【3】平衡二叉树的构建原理
平衡二叉树的形成肯定是有一定规律可循的，那么平衡二叉树的“生长”原理是什么呢？
请看程老师下面的构建示例以及详细讲解：
关于平衡二叉树的旋转分为以下四种情况：
【4】平衡二叉树的实现
平衡二叉树的实现代码如下：
#include <iostream>
using namespace std; template<class Type>
class AVLtree; template<class Type>
class TNode
{
friend class AVLtree<Type>;
private:
Type data;
int balance; // 平衡因子
TNode<Type> *leftChild, *rightChild;
public:
TNode(const Type &x = Type(),TNode<Type> *left = NULL,TNode<Type> *right = NULL)
: data(x)
, leftChild(left)
, rightChild(right)
, balance()
{}
}; template<class Type>
class AVLtree
{
private:
TNode<Type> *root;
private:
void RightBalance(TNode<Type> * &r,bool &action);
void LeftBalance(TNode<Type> *&r,bool &action);
void Insert(TNode<Type> * &root,const Type &x,bool &action);
void LeftLeft(TNode<Type> * &r);
void RightRight(TNode<Type> * &r);
void LeftRight(TNode<Type> *&r);
void RightLeft(TNode<Type> *&r);
TNode<Type> *Parent(TNode<Type> *p,TNode<Type> *cur);
TNode<Type> *FindNodeNext(TNode<Type> *cur);
void DeleTNode(TNode<Type> *&cur,TNode<Type> *par);
void Remove(TNode<Type> * &r,const Type &x,bool &action);
void InOrder(TNode<Type> *p);
public:
AVLtree();
void Insert(const Type &bt);
TNode<Type> *Parent(TNode<Type> *cur);
void Remove(const Type &x);
void InOrder();
}; // 右平衡处理过程
template<class Type>
void AVLtree<Type>::RightBalance(TNode<Type> * &r, bool &action)
{
TNode<Type> *rightsub = r->rightChild, *leftsub = NULL;
switch (rightsub->balance) //判断右子树的平衡因子
{
case -: // RR型
r->balance = ;
rightsub->balance = ;
RightRight(r); //RR型处理
action = false;
break;
case :
break;
case : // RL型
leftsub = rightsub->leftChild;
switch (leftsub->balance) // 判断左子树的平衡因子
{
case : // RL型
r->balance = ;
rightsub->balance = ;
leftsub->balance = ;
break;
case : // RLL型
r->balance = ;
leftsub->balance = ;
rightsub->balance = -;
break;
case -: // RLR型
rightsub->balance = ;
leftsub->balance = ;
r->balance= -;
break;
}
RightLeft(r); // RL折线型转换处理
action = false;
break;
}
}
// 折线型LR处理
template<class Type>
void AVLtree<Type>::LeftRight(TNode<Type> *&r)
{
RightRight(r->leftChild); // 转换为LL型(一条直线)
LeftLeft(r); // LL型处理
}
// 折线型RL处理
template<class Type>
void AVLtree<Type>::RightLeft(TNode<Type> *&r)
{
LeftLeft(r->rightChild); // 先转换为RR型(一条直线)
RightRight(r); // RR型处理
}
// 1. 把RL转换为RR 2. LL型处理
template<class Type>
void AVLtree<Type>::LeftLeft(TNode<Type> * &r)
{
TNode<Type> *cur = r; // cur暂存r
r = r->leftChild; // 改变r就是改变根
cur->leftChild = r->rightChild;// 改变暂存cur 实现衔接
r->rightChild = cur; // 根的右子树置为cur
}
// 1. 把LR转换为LL 2. RR型处理
template<class Type>
void AVLtree<Type>::RightRight(TNode<Type> * &r)
{
TNode<Type> *cur = r; // cur暂存r
r = r->rightChild; // 改变r就是改变根
cur->rightChild = r->leftChild;// 改变暂存cur 实现衔接
r->leftChild = cur; // 根的左子树置为cur
}
// 左平衡处理过程
template<class Type>
void AVLtree<Type>::LeftBalance(TNode<Type> *&r, bool &action)
{
TNode<Type> *leftsub = r->leftChild;
TNode<Type> *rightsub = leftsub->rightChild;
switch (leftsub->balance)
{
case :// LL型
leftsub->balance = ;
r->balance = ;
LeftLeft(r);
action = false;
break;
case :
action = false;
break;
case -:// LR型
switch (rightsub->balance)
{
case :// LR型
r->balance = ;
rightsub->balance = ;
leftsub->balance = ;
break;
case -:// LRR型
r->balance = ;
rightsub->balance = ;
leftsub->balance = ;
break;
case :// LRL型
rightsub->balance = ;
leftsub->balance = ;
r->balance = -;
break;
}
LeftRight(r); // LR折线型转换处理
action = false;
break;
}
}
// Insert主函数
template<class Type>
void AVLtree<Type>::Insert(TNode<Type> * & root, const Type &x, bool &action)
{
if (NULL == root)
{
root = new TNode<Type>(x);
return;
}
else if (x > root->data)
{
Insert(root->rightChild, x, action);
if (action) // 右子树插入成功
{
switch (root->balance) // 需要重置根的平衡因子
{
case : // 表示左子树已经存在，现再插入右子树成功
root->balance = ; //平衡因子置0
break;
case : // 表示之前平衡，现再插入右子树成功
root->balance = -; //平衡因子置1
break;
case -: // 表示右子树已经存在，现再插入右子树成功
RightBalance(root, action); //右平衡
break;
}
}
}
else if (x < root->data)
{
Insert(root->leftChild, x, action);
if (action) // 左子树插入成功
{
switch (root->balance) // 需要重置根的平衡因子
{
case : // 平衡左子树
LeftBalance(root, action);
break;
case :
root->balance = ;
break;
case -:
root->balance = ;
action = false;
break;
}
}
}
else
cout << "数据" << x << "重复！" << endl;
}
// 查找当前节点的父节点
template<class Type>
TNode<Type> *AVLtree<Type>::Parent(TNode<Type> *p, TNode<Type> *cur)
{
if (NULL == p || NULL == cur|| p == cur)
return NULL;
if (cur == p->leftChild || cur == p->rightChild)
return p; if (p->data < cur->data)
return Parent(p->rightChild, cur);
else
return Parent(p->leftChild, cur);
}
// 查找当前结点的后继 (先序遍历的后继)
template<class Type>
TNode<Type> *AVLtree<Type>::FindNodeNext(TNode<Type> *cur)
{
if (NULL == cur)
return NULL;
TNode<Type> *p = cur->rightChild;
while (p->leftChild != NULL)
{
p = p->leftChild;
}
return p;
}
//////////////////////////////////////////////////////////////////////
/////////////////////////////////删除节点
template<class Type>
void AVLtree<Type>::DeleTNode(TNode<Type> *&cur, TNode<Type> *par)
{
if (NULL == cur)
return;
// 情况一：删除的是根节点，那么它的父节点必定为NULL
if (NULL == par)
{ // cur可能是根结点，并且树仅仅只有一个根
if (NULL == cur->rightChild && NULL == cur->leftChild)
{
delete cur;
cur = NULL;
return;
}
// 单分支的树
if (NULL == cur->rightChild)
{ // 右子树不存在
TNode<Type> *p = cur;
cur = cur->leftChild;
delete p;
p = NULL;
return;
}
if (NULL == cur->leftChild)
{ // 左子树不存在
TNode<Type> *q = cur;
cur = cur->rightChild;
delete q;
q = NULL;
return;
}
}
// 情况二：删除的属于双分支的节点
if (cur->leftChild != NULL && cur->rightChild != NULL)
{
TNode<Type> *p = FindNodeNext(cur); // 锁定先序遍历的后继
// 情况一：
if (cur->rightChild == p)
{ // 说明右子树仅仅只有一个节点
cur->balance += ; // 删除之后平衡因子改变
cur->data = p->data; // 填充数据，意味着改变删除对象
cur->rightChild = p->rightChild; // 衔接数据
delete p; //删除节点p
p = NULL;
return;
}
// 情况二：
// 否则
TNode<Type> *q = Parent(p); // 找到父节点
if (q->balance != ) // 不等于0，说明删除后会影响根结点的平衡因子
cur->balance += ; // 调整根节点的平衡因子
// 否则
q->balance -= ; // 删除的是左节点，所以加一
cur->data = p->data; // 填充数据，意味着改变删除对象 q->leftChild = p->rightChild; // 衔接数据 // 最后才可以动手删除节点 删除节点 释放内存
delete p;
p = NULL;
return;
}
// 情况三：单分支(其中包括了叶子节点的情况)
if (NULL == cur->leftChild)
{
TNode<Type> *p = cur;
if (cur == par->leftChild)
par->leftChild = cur->rightChild; // 衔接数据
else
par->rightChild = cur->rightChild; // 衔接数据 delete p;
p = NULL;
return;
}
if (NULL == cur->rightChild)
{
TNode<Type> *q = cur;
if (cur == par->leftChild)
par->leftChild = cur->leftChild;
else
par->rightChild = cur->leftChild; delete q;
q = NULL;
return;
}
}
// 删除过程的主函数
template<class Type>
void AVLtree<Type>::Remove(TNode<Type> * &r, const Type &x, bool &action)
{
if (NULL == r)
return;
if (x == r->data)
{
TNode<Type> *cur = r; // 确定数据的节点信息
TNode<Type> *par = Parent(r);// 确定当前结点的父节点
DeleTNode(r, par); // 删除当前指针
return;
}
else if (x > r->data)
{ // 右边查找
Remove(r->rightChild, x, action);
if (action)
{
switch (r->balance)
{
case -: // 若原来为1，现在删除了右节点，应该为0
r->balance = ;
break;
//若原来为-1，现在又再右枝上删除了节点，
//树一定不平衡，需要左平衡调整
case :
LeftBalance(r, action);
action = false;
break;
case : // 若原来为0，现在删除了右节点，应该为-1
r->balance = ;
action = false;
break;
}
}
}
else if (x < r->data)
{
Remove(r->leftChild, x, action);
if (action)
{
switch (r->balance)
{
case -:// 若原来为1，现在又再左枝上删除了节点，
// 树一定不平衡，需要右平衡调整
RightBalance(r, action);
break;
case :// 若原来为-1，现在删除了左节点，应该为0
r->balance = ;
break;
case :// 若原来为0，现在删除了左节点，应该为1
r->balance = -;
action = false;
break;
}
}
}
} template<class Type>
AVLtree<Type>::AVLtree(): root(NULL)
{}
template<class Type>
void AVLtree<Type>::Insert(const Type &bt)
{
bool action = true;
Insert(root, bt, action);
}
template<class Type>
TNode<Type> *AVLtree<Type>::Parent(TNode<Type> *cur)
{
return Parent(root, cur);
}
template<class Type>
void AVLtree<Type>::Remove(const Type &x)
{
bool action = true;
Remove(root, x, action);
}
template<class Type>
void AVLtree<Type>::InOrder(TNode<Type> *p)
{
if (p != NULL)
{
InOrder(p->leftChild);
cout << p->data << " ";
InOrder(p->rightChild);
}
}
template<class Type>
void AVLtree<Type>::InOrder()
{
InOrder(root);
cout << endl;
}
Good Good Study, Day Day Up.
顺序 选择 循环 总结