# AVL树 - C语言实现（五）

## 1 AVL树

AVL树的平衡条件：每个节点的左子树和右子树的高度最多差1

## 3 C语言实现

### 3.1 Insert例程

``````typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
struct AvlNode{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;//节点高度
}``````
``````/* * 获取节点高度 */
static int
Height(Position P){
if(P == NULL){
return -1;
}
return P -> Height;
}``````
``````/**
* 插入例程
* 输入参数：插入元素，树根节点
* 返回参数：树根节点
*/
AvlTree
Insert(ElementType X,AvlTree T){
if(T == NULL){
/*
* 一般情况为递归调用的最后一层，执行插入操作
*/
T = malloc(sizeof(struct AvlNode));
if(T == NULL){
//内存不足异常
}else{
T -> Element = X;
T -> Left = T -> Right = NULL;
T -> Height = 0;
}
}else if(X < T -> Element){
/*
* 往左边递归插入
*/
T -> Left = Insert(X,T -> Left);
//插入完成判断当前节点下的左子树与右子树的高度差，确定不平衡点
if(Height(T -> Left) - Height(T -> Right) == 2){
//中间节点（T的左边节点）大于插入点元素，单旋
if(X < T -> Left -> Element){
T = SingleRotateWithLeft(T);
}else{
T = dubbleRotateWithLeft(T);
}
}
}else if(X > T -> Element){
/*
* 往右边递归插入
*/
T -> Right = Insert(X,T -> Right);
if(Height(T -> Right) - Height(T -> Left) == 2){
if(X > T -> Right -> Element){
T = SingleRotateWithRight(T);
}else{
T = dubbleRotateWithRight(T);
}
}
}

//返回T的高度，T的两儿子树中最大高度 + 1
T -> Height = Max(Height(T -> Left),Height(T -> Right)) + 1；
return T;
}``````
``````/* * 单旋 */
static Position
SingleRotateWithLeft(Postion k1){
Position k2 = k1 -> Left;
k1 -> Left = k2 -> Right;
k2 -> Right = k1;

k1 -> Height = Max(Height(k1 -> Left),Height(k1 -> Right)) + 1;
k2 -> Height = Max(Height(k2 -> Left),Height(k1)) + 1;

return k2;
}``````
``````/* * 双旋分解成两次单旋 */
static Position
DoubleRotateWithLeft(Postion k3){
//对k3的左子树进行单旋操作
k3 -> Left = SingleRotateWithRight(k3 -> Left);

//对k3进行单旋
return SingleRotateWithLeft(k3);
}``````

### 3.2 Delete例程

``````AvlTree
Delete(ElementType X,AvlTree T){
Position temp;
if(T == NULL){
// 元素未找到异常
}else if(X < T -> Element){
T -> Left = Delete(X,T -> Left);
// 判断目标节点是否不平衡
if(Height(T -> Right) - Height(T -> Left) == 2){
/* 若不平衡，则比较目标节点（T节点）的右节点的，左、右儿子树的高度 */
/* 若右儿子树高度大于左儿子树高度，单旋操作 */
/* 若左儿子树高度大于右儿子树高度，双旋操作 */
/* 若左、右儿子树高度相等，单旋、双旋都可（默认单旋）*/
if(Height(T -> Right -> Right) < Height(T -> Right -> Left) ){
T = DoubleRotateWithRight(T);
}else{
T = SingleRotateWithRight(T);
}
}

}else if(X > T -> Element){
T -> Right = Delete(X,T -> Right);
// 判断目标节点是否不平衡
if(Height(T -> Left) - Height(T -> Right) == 2){
if(Height(T -> Left -> Right) > Height(T -> Left -> Left) ){
T = DoubleRotateWithLeft(T);
}else{
T = SingleRotateWithLeft(T);
}
}
}else if((T -> Left != NULL) && (T -> Right != NULL)){
/* 目标节点匹配到元素X，且有两个儿子树 */

//找到目标节点右子树的最小节点
temp = FindMin(T -> Right);
//最小节点的元素覆盖目标节点元素
T -> ELement = temp -> Element;
//递归调用，删除右子树中的最小节点
T -> Right = Delete(T -> Element,T -> Right);
// 判断目标节点是否不平衡
if(Height(T -> Left) - Height(T -> Right) == 2){
if(Height(T -> Left -> Right) > Height(T -> Left -> Left) ){
T = DoubleRotateWithLeft(T);
}else{
T = SingleRotateWithLeft(T);
}
}
}else{
/* 目标节点匹配到元素X，且有一个儿子树，或没有儿子树 */
/* 目标节点最多只有一个儿子树，因此左子树高度为-1，右子树高度必为0 */
/* 所以该目标节点处，不会发生不平衡情况 */

temp = T;
if(T -> Left == NULL){
T = T -> Right;
}else if(T -> Right == NULL){
T = T -> Left;
}
free(temp);
}
// 计算高度
T -> Height = Max(Height(T -> Left),Height(T -> Right)) + 1;
return T;
}``````
原文作者：AVL树
原文地址: https://blog.csdn.net/xsp_happyboy/article/details/82113818
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。