1. 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)
#define LH +1 /* 左高 */
#define EH 0 /* 等高 */
#define RH -1 /* 右高 */
/// 平衡二叉樹
typedef struct BiTNode {
int data; // 數(shù)據(jù)
int bf; // 平衡因子
struct BiTNode *lchild, *rchild; // 左右孩子指針
} BiTNode, *BiTree;
2. 左旋右旋
這里以右旋為例是牢，P斷開了左指針系宫，L斷開右指針乌庶；L空出來(lái)的右指針指向P，P空出來(lái)的左指針指向：
右旋
/// 左旋
void R_Rotate(BiTree *p) {
BiTree L = (*p)->lchild; // L是p的左子樹
(*p)->lchild = L->rchild; // L的右子樹作為p的左子樹
L->rchild = *p; // 將p作為L(zhǎng)的右子樹
*p = L; // 將L替換原有p的根結(jié)點(diǎn)位置
}
/// 右旋
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的根結(jié)點(diǎn)位置
}
3. 左失衡右失衡
/// 左失衡
void LeftBalance(BiTree *T) {
BiTree Tl = (*T)->lchild;
BiTree Lr;
switch (Tl->bf) {
case LH: // 新結(jié)點(diǎn)插入在T的左孩子的左子樹上
(*T)->bf = Tl->bf = EH; // 調(diào)整后平衡
R_Rotate(T); // 進(jìn)行右旋
break;
case RH: // 新結(jié)點(diǎn)插入在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); // 對(duì)T的左子樹作左旋平衡處理
R_Rotate(T); // 對(duì)T作右旋平衡處理
break;
}
}
/// 右失衡
void RightBalance(BiTree *T) {
BiTree Tr = (*T)->rchild;
BiTree Rl;
switch (Tr->bf) {
case RH: // 新結(jié)點(diǎn)插入在T的右孩子的右子樹上
(*T)->bf = Tr->bf = EH; // 調(diào)整后平衡
L_Rotate(T); // 進(jìn)行左旋
break;
case LH: // 新結(jié)點(diǎn)插入在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); // 對(duì)T的右子樹作右旋平衡處理
L_Rotate(T); // 對(duì)T作左旋平衡處理
break;
}
}
4. 插入結(jié)點(diǎn)
/// 插入結(jié)點(diǎn)
/// @param T AVL樹
/// @param data 被插入數(shù)據(jù)
/// @param taller 是否"長(zhǎng)高"
Status InsertAVL(BiTree *T, int data, Status *taller) {
if (!*T) { // 空結(jié)點(diǎn)
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = data;
(*T)->lchild = (*T)->rchild = NULL; // 新結(jié)點(diǎn)沒(méi)有左右子樹
(*T)->bf = EH;
*taller = TRUE; // 新結(jié)點(diǎn)默認(rèn)"長(zhǎng)高"
} else {
if (data == (*T)->data) { // 已存在和data有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入
*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:
// 原本左、右子樹等高拣度，現(xiàn)因左子樹增高而使樹增高
(*T)->bf = LH;
*taller = TRUE;
break;
case RH:
// 原本右子樹比左子樹高碎绎，現(xiàn)左右子樹等高
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
} else { // 大則在右子樹插入
if (!InsertAVL(&(*T)->rchild, data, taller)) // 插入失敗
return FALSE;
// 插入成功
if (*taller) {
switch ((*T)->bf) {
case LH:
// 原本左子樹比右子樹高，現(xiàn)左右子樹等高
(*T)->bf = EH;
*taller = FALSE;
break;
case EH:
// 原本左抗果、右子樹等高筋帖，現(xiàn)因右子樹增高而使樹增高
(*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 最后一個(gè)被訪問(wèn)結(jié)點(diǎn)的指針引用
///
/// 若指針p指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)則返回FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) {
if (!T) { // 空結(jié)點(diǎn)
*p = f; // 查詢失敗，指回雙親結(jié)點(diǎn)
return FALSE;
} else if (key == T->data) { // 根節(jié)點(diǎn)查詢成功
*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;
}
