1. 基础数据结构
#define LH +1 /* 左高 */
#define EH 0 /* 等高 */
#define RH -1 /* 右高 */
/// 平衡二叉树
typedef struct BiTNode {
int data; // 数据
int bf; // 平衡因子
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
2. 左旋右旋
这里以右旋为例,P断开了左指针,L断开右指针;L空出来的右指针指向P,P空出来的左指针指向:
右旋/// 左旋
void R_Rotate(BiTree *p) {
BiTree L = (*p)->lchild; // L是p的左子树
(*p)->lchild = L->rchild; // L的右子树作为p的左子树
L->rchild = *p; // 将p作为L的右子树
*p = L; // 将L替换原有p的根结点位置
}
/// 右旋
void L_Rotate(BiTree *p) {
BiTree R = (*p)->rchild; // R是p的右子树
(*p)->rchild = R->lchild; // R的左子树作为R的右子树
R->lchild = *p; // 将p作为R的左子树
*p = R; // 将R替换原有p的根结点位置
}
3. 左失衡右失衡
/// 左失衡
void LeftBalance(BiTree *T) {
BiTree Tl = (*T)->lchild;
BiTree Lr;
switch (Tl->bf) {
case LH: // 新结点插入在T的左孩子的左子树上
(*T)->bf = Tl->bf = EH; // 调整后平衡
R_Rotate(T); // 进行右旋
break;
case RH: // 新结点插入在T的左孩子的右子树上
Lr = Tl->rchild; // Lr指向T的左孩子的右子树
// 修改T及其左孩子的平衡因子
switch (Lr->bf) {
case LH:
Tl->bf = RH;
(*T)->bf = EH;
break;
case EH:
Tl->bf = (*T)->bf = EH;
break;
case RH:
Tl->bf = EH;
(*T)->bf = LH;
break;
}
Lr->bf = EH;
L_Rotate(&(*T)->lchild); // 对T的左子树作左旋平衡处理
R_Rotate(T); // 对T作右旋平衡处理
break;
}
}
/// 右失衡
void RightBalance(BiTree *T) {
BiTree Tr = (*T)->rchild;
BiTree Rl;
switch (Tr->bf) {
case RH: // 新结点插入在T的右孩子的右子树上
(*T)->bf = Tr->bf = EH; // 调整后平衡
L_Rotate(T); // 进行左旋
break;
case LH: // 新结点插入在T的右孩子的左子树上
Rl = Tr->lchild; // Ll指向T的右孩子的左子树
// 修改T及其左孩子的平衡因子
switch (Rl->bf) {
case LH:
Tr->bf = EH;
(*T)->bf = RH;
break;
case EH:
Tr->bf = (*T)->bf = EH;
break;
case RH:
Tr->bf = LH;
(*T)->bf = EH;
break;
}
Rl->bf = EH;
R_Rotate(&(*T)->rchild); // 对T的右子树作右旋平衡处理
L_Rotate(T); // 对T作左旋平衡处理
break;
}
}
4. 插入结点
/// 插入结点
/// @param T AVL树
/// @param data 被插入数据
/// @param taller 是否"长高"
Status InsertAVL(BiTree *T, int data, Status *taller) {
if (!*T) { // 空结点
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = data;
(*T)->lchild = (*T)->rchild = NULL; // 新结点没有左右子树
(*T)->bf = EH;
*taller = TRUE; // 新结点默认"长高"
} else {
if (data == (*T)->data) { // 已存在和data有相同关键字的结点则不再插入
*taller = FALSE;
return FALSE;
}
if (data < (*T)->data) { // 小则在左子树插入
if (!InsertAVL(&(*T)->lchild, data, taller)) // 插入失败
return FALSE;
// 插入成功
if (*taller) {
switch ((*T)->bf) {
case LH:
// 原本左子树比右子树高,需要作左平衡处理
LeftBalance(T);
*taller = FALSE;
break;
case EH:
// 原本左、右子树等高,现因左子树增高而使树增高
(*T)->bf = LH;
*taller = TRUE;
break;
case RH:
// 原本右子树比左子树高,现左右子树等高
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
} else { // 大则在右子树插入
if (!InsertAVL(&(*T)->rchild, data, taller)) // 插入失败
return FALSE;
// 插入成功
if (*taller) {
switch ((*T)->bf) {
case LH:
// 原本左子树比右子树高,现左右子树等高
(*T)->bf = EH;
*taller = FALSE;
break;
case EH:
// 原本左、右子树等高,现因右子树增高而使树增高
(*T)->bf = RH;
*taller = TRUE;
break;
case RH:
// 原本右子树比左子树高,需要作右平衡处理
RightBalance(T);
*taller = FALSE;
break;
}
}
}
}
return TRUE;
}
5. 查询
查询和二叉搜索树相同。
/// 递归查找二叉排序树T中,是否存在key
/// @param T AVL树
/// @param key 被查询值
/// @param f 指针f指向T的双亲,初始值为NULL
/// @param p 最后一个被访问结点的指针引用
///
/// 若指针p指向查找路径上访问的最后一个结点则返回FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) {
if (!T) { // 空结点
*p = f; // 查询失败,指回双亲结点
return FALSE;
} else if (key == T->data) { // 根节点查询成功
*p = T;
return TRUE;
} else if (key < T->data) { // 查询值跟小,则在左子树中找
return SearchBST(T->lchild, key, T, p);
} else { // 查询值更大,则在右子树中找
return SearchBST(T->rchild, key, T, p);
}
return TRUE;
}
网友评论