《数据结构和算法》——平衡二叉树
平衡二叉树：对比于二叉排序树对于时间复杂度的不可控制，平衡二叉树有个更加稳定的时间复杂度。我们构建了一个左右子树平衡的二叉树，使每个节点的左、右二叉树的深度差值不超过1，便于遍历。构建过程：在构建时，除了需要按照排序二叉树的构建原则，使节点的左子树的数据小于节点的数据，节点右子树的数据大于节点的数据。同时，在添加数据时，我们需要对二叉树每个节点进行一个判定，若出现一个节点的平衡因子<=-2，则将该部分进行一次左旋转，若平衡因子大于2，则进行一次右旋转。需要注意的是，若出现几个节点的平衡因子正负号不同，则需要对平衡因子正负不同的几个节点的子树进行旋转，而不能只对几个节点统一只做一次大的旋转。
代码实现：我们利用递归的办法，先根据二叉排序树的规则将新的数据插入二叉树，然后判断一次“长高”部分的节点的平衡因子是否失衡，若失衡我们则需要对失衡部分进行旋转。先对节点进行平衡因子的调整和判断，若节点的左（右）子树的平衡因子不为0，我们只需要做一次旋转即可，否则需要进行两次旋转
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
class Bitnode
{
public:
int data;
int bf=0;
Bitnode *lchild = NULL, *rchild = NULL;
};
void L_rotate(Bitnode *&P)
{
Bitnode *L=P->lchild;
P->rchild = L->lchild;
L->rchild = P;
}
void R_rotate(Bitnode *&P)
{
Bitnode *L = P->rchild;
P->lchild = L->rchild;
L->lchild = P;
}
void LeftB(Bitnode *&T)
{
Bitnode *L = T->lchild, *Lr = NULL;
switch (L->bf)
{
case 1:
T->bf = L->bf = 0;
R_rotate(T);
break;
case -1:
Lr = L->rchild;
switch (Lr->bf)
{
case 1:
T->bf = -1;
L->bf = 0;
break;
case 0:
T->bf = L->bf = 0;
break;
case -1:
T->bf = 0;
L->bf = 1;
break;
}
Lr->bf = 0;
L_rotate(T->lchild);
R_rotate(T);
}
}
void RightB(Bitnode *&T)
{
Bitnode *R = T->rchild, *Rl = NULL;
switch (R->bf)
{
case 1:
T->bf = R->bf = 0;
L_rotate(T);
break;
case -1:
Rl = R->lchild;
switch (Rl->bf)
{
case 1:
T->bf = -1;
R->bf = 0;
break;
case 0:
T->bf = R->bf = 0;
break;
case -1:
T->bf = 0;
R->bf = 1;
break;
}
Rl->bf = 0;
R_rotate(T->lchild);
L_rotate(T);
}
}
int InsertAVL(Bitnode *&T,int e,int *is)
{
if (T == NULL)
{
T = new Bitnode;
T->data = e;
*is = true;
return true;
}
else
{
if (e == T->data)
{
*is = false;
return false;
}
if (e < T->data)
{
if (!InsertAVL(T->lchild, e, is))
{
return false;
}
else
{
if (*is)
{
switch (T->bf)
{
case 1:
LeftB(T);//左旋节点
*is = false;
break;
case 0:
T->bf = 1;
*is = true;
break;
case -1:
T->bf = 0;
*is = false;
break;
}
}
}
}
else
{
if (!InsertAVL(T->rchild, e, is))
{
return false;
}
if (*is)
{
switch (T->bf)
{
case -1:
RightB(T);
*is = false;
break;
case 0:
T->bf = -1;
*is = true;
break;
case 1:
T->bf = 0;
*is = false;
break;
}
}
}
}
}
页:
[1]