AVL树

AVL树概述

AVL树(Adelson-Velsky and Landis Tree),得名与其发明者G. M. Adelson-Velsky和Evgenii Landis,是最早被发明的自平衡二叉查找树.在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树.

由于一般的二叉查找树,在极端情况下会退化成类似线性链表的结构,即变成一颗左斜树或右斜树,如图:

查找时间复杂度降低为O(n).使用平衡树可以解决这个问题,AVL树就是一种平衡树,其满足以下的几种性质:

1. AVL树本身是一棵二叉搜索树
2. 每一棵子树都是AVL树
3. 平衡条件:每个节点的左右子树的高度之差(平衡因子)的绝对值不超过1,即平衡因子为1,0,-1的节点认为是平衡的.换句话说,任意节点的左右子树的最大高度之差为1.
4. 查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)

前置知识

树的旋转

树的旋转用于调整子树的位置.

左(右)旋可以将根节点的左(右)子树移动到根的位置,将根节点"旋转"到原来左(右)子树的位置.

旋转约定

旋转伪代码

旋转前后仍然满足是一棵二叉搜索树,因此可以写出旋转的伪代码:

typedef struct AVLNode{
    AVLNode *left,*right;
    // 其他成员
}AVLNode;
AVLNode *right_rotate(AVLNode *node) {
    // 三步操作
    // 注意left的右子树的位置变化
    AVLNode *left = node->left;
    node->left = left->right;
    left->right = node;

    return left;
}
AVLNode *left_rotate(AVLNode *node) {
    // 三步操作
    // 注意right的左子树的位置变化
    AVLNode *right = node->right;
    node->right = right->left;
    right->left = node;

    return right;
}

如果简单地将左(右)子节点移动到根,那么从图形上看会发现该节点的孩子变成了3个(原来的左右节点和移动后的根节点),此时就需要将其中一个子树(左旋为左子树,右旋为右子树)移动为根节点(此时已经不是树根)的孩子(左旋为其右子树,右旋为其左子树)

树的旋转可以调整左右子树的高度,可以将高度较小的子树下移,高度较大的子树上移.在平衡树中,用于调整(减小)左右子树的高度差.

实现原理

需要实现的操作

实现一颗二叉平衡树需要实现如下操作:

1. 树的左旋和右旋
2. 向树中插入一个节点,并根据不同情况调整平衡
3. 从树中删除一个节点,并根据不同情况调整平衡

什么时候需要旋转

当树的节点发生了变化,即发生了插入或删除时,需要检查此时整个树是否仍然平衡,即左右子树高度差不超过1.

例如新增了一个节点7:

这说明插入/删除节点可能(不是一定)会导致树不再平衡,此时需要进行特定的旋转来重新平衡,当然,无论旋转与否,这棵树都是一棵合法的二叉搜索树,只不过不一定平衡而已.

下面讨论插入和删除的不同情况该如何旋转.

AVL树的插入操作

首先会按照常规二叉搜索树的插入操作插入一个节点,然后从这个节点进行回溯,对每个回溯路径上的点判断其左右子树是否平衡,如果不平衡,即高度之差超过1,就要进行调整.

设当前的根节点为X,其左右孩子为XL,XR.XL和XR的子树依次为T1,T2,T3…

插入节点S后有如下4种情况需要进行旋转:

1. X的左子树的高度比右子树大2,且S在XL的左子树上:

   

2. X的右子树的高度比左子树大2,且S在XR的右子树上:

   

3. X的左子树比右子树大2,且S在XL的右子树上:

   

4. X右子树比左子树大2,且S在XR的左子树上:

   

以上4种情况中,1和2,3和4为左右对称的情况,仅仅是一个镜像.

读者需要自己尝试试验,或去考虑为什么需要这样旋转,总之,在代码中要分情况讨论,选择对应的旋转操作.

当然,如果高度差不超过1,则不需要进行任何旋转.

AVL树的删除操作

插入(可能)会增加某棵子树的高度,而删除相反,相同的是,两种操作都可能影响高度差大于1,导致需要旋转调整.

同样,从删除后的节点进行回溯,按照上面的4中情况进行对应调整即可.

可以将要删除的节点不断向下旋转到叶子结点,最后删除该叶子节点.

另一种方法时,如果找到了删除节点S,有如下3种情况:

1. S既有左子树,又有右子树.

   找到右子树中最小的节点S2,用S2覆盖S,然后递归到右子树,这时问题转移为"删除右子树中S2节点".

   回溯回来后,要检查S(此时S的key已经被S2的key覆盖)的左右子树是否平衡,分情况选择是否旋转调整.

2. S只有左子树.

   简单地把S删除,用S的左孩子(的指针)替换S(S的父亲的孩子指针)即可,即删除S这个树根.

3. S只有右子树.

   简单地把S删除,用S的右孩子(的指针)替换S(S的父亲的孩子指针)即可,即删除S这个树根.

注意上面的情况2,3可能是从情况1递归下来的,所以如果需要旋转调整,会返回到递归的上一层进行处理,即回溯.

另一方面,如果尚未找到,那么简单地作为二叉搜索树进行递归查找即可,回溯后进行(可能需要的)旋转调整.

代码实现

本代码使用C语言编写.

头文件AVLTree.h:

//
// Created by WAHAHA on 2023/12/9.
//

#ifndef ADT_AVLTREE_AVLTREE_H
#define ADT_AVLTREE_AVLTREE_H

#define true 1
#define false 0
#define error -1
#define status int

typedef int ElementType;
typedef struct AVLNode {
    ElementType data;
    int height;
    struct AVLNode *left;
    struct AVLNode *right;
} AVLNode;

typedef struct {
    AVLNode *root;
    // int (*compare)(ElementType*, ElementType*); // 需要注册的比较函数
    int size;
} AVLTree;

// default compare function
// int defaultCompare(ElementType *a, ElementType *b);

// create and destroy
// AVLTree *AVLTreeCreate(int (*compare)(ElementType*, ElementType*));
AVLTree *AVLTreeCreate(void);
void AVLTreeDestroy(AVLTree *tree);
void AVLTreeDestroyRun(AVLNode *node);

// insert and delete
status AVLTreeInsert(AVLTree *tree, ElementType data);
status AVLTreeInsertRun(AVLNode **root, ElementType data);
status AVLTreeDelete(AVLTree *tree, ElementType data);
status AVLTreeDeleteRun(AVLNode **root, ElementType data);

// search
status AVLTreeSearch(AVLTree *tree, ElementType data);

// get max and min
status AVLTreeGetMax(AVLTree *tree, ElementType *result);
status AVLTreeGetMin(AVLTree *tree, ElementType *result);

// get status
int AVLTreeGetHeight(AVLTree *tree);
int GetNodeHeight(AVLNode *node);
int AVLTreeGetSize(AVLTree *tree);
status AVLTreeIsEmpty(AVLTree *tree);
ElementType GetNodeMin(AVLNode *node);
ElementType GetNodeMax(AVLNode *node);

// rotate
void LeftRotation(AVLNode **node);
void RightRotation(AVLNode **node);

// private functions
int max(int a, int b);

#endif //ADT_AVLTREE_AVLTREE_H

源文件AVLTree.c:

//
// Created by WAHAHA on 2023/12/9.
//

#include "AVLTree.h"
#include <stdio.h>
#include <stdlib.h>

AVLTree *AVLTreeCreate(void) {
    AVLTree *tree = (AVLTree *) malloc(sizeof(AVLTree));
    if (tree == NULL) {
        printf("malloc failed\n");
        return NULL;
    }
    tree->root = NULL;
    tree->size = 0;
    return tree;
}

void AVLTreeDestroyRun(AVLNode *node) {
    if (node == NULL) {
        return;
    }
    AVLTreeDestroyRun(node->left);
    AVLTreeDestroyRun(node->right);
    free(node);
}

void AVLTreeDestroy(AVLTree *tree) {
    if (tree == NULL) {
        printf("tree is NULL\n");
        return;
    }
    // recursive destroy
    AVLTreeDestroyRun(tree->root);
    free(tree);
}

// insert and delete
status AVLTreeInsert(AVLTree *tree, ElementType data) {
    if (tree == NULL) {
        printf("tree is NULL\n");
        return error;
    }
    status result = AVLTreeInsertRun(&tree->root, data);
    // check status
    if (result == true) {
        tree->size++;
        return true;
    } else if (result == false)
        return false;
    return error;
}

/*
 * insert data into AVLTree
 * return true if insert successfully
 * return false if insert failed
 */
status AVLTreeInsertRun(AVLNode **root, ElementType data) {
    if (*root == NULL) {
        *root = (AVLNode *) malloc(sizeof(AVLNode));
        if (*root == NULL) {
            printf("malloc failed\n");
            return error;
        }
        (*root)->data = data;
        (*root)->height = 1;
        (*root)->left = (*root)->right = NULL;
        return true;
    }

    if ((*root)->data == data)
        return false;
    else if ((*root)->data < data) {
        // insert into right subtree
        status result = AVLTreeInsertRun(&(*root)->right, data);
        if (result == false)
            return false;
        else if (result == error)
            return error;

        int leftHeight = GetNodeHeight((*root)->left);
        int rightHeight = GetNodeHeight((*root)->right);
        // after insert, we need check if the tree is balanced
        // in this case, we insert into right subtree,
        // so rightHeight >= leftHeight
        if (rightHeight - leftHeight == 2) {
            if ((*root)->right->data < data) {
                // type RR
                LeftRotation(root);
            } else {
                // type RL
                RightRotation(&(*root)->right);
                LeftRotation(root);
            }
        }
    } else {
        // insert into left subtree
        status result = AVLTreeInsertRun(&(*root)->left, data);
        if (result == false)
            return false;
        else if (result == error)
            return error;

        int leftHeight = GetNodeHeight((*root)->left);
        int rightHeight = GetNodeHeight((*root)->right);
        // after insert, we need check if the tree is balanced
        // in this case, we insert into left subtree,
        // so leftHeight >= rightHeight
        if (leftHeight - rightHeight == 2) {
            if ((*root)->left->data > data) {
                // type LL
                RightRotation(root);
            } else {
                // type LR
                LeftRotation(&(*root)->left);
                RightRotation(root);
            }
        }
    }
    // update height if abs(leftHeight - rightHeight) != 2
    (*root)->height =
            max(GetNodeHeight((*root)->left), GetNodeHeight((*root)->right)) +
            1;
    return true;
}

status AVLTreeDelete(AVLTree *tree, ElementType data) {
    if (tree == NULL) {
        printf("tree is NULL\n");
        return error;
    }
    status result = AVLTreeDeleteRun(&tree->root, data);
    // check status
    if (result == true) {
        tree->size--;
        return true;
    } else if (result == false)
        return false;
    return error;
}

status AVLTreeDeleteRun(AVLNode **root, ElementType data) {
    if (*root == NULL)
        return false;
    if ((*root)->data == data) {
        // find the node
        if ((*root)->left != NULL && (*root)->right != NULL) {
            // left and right subtree both exist

            // find the min node in right subtree and replace the node
            ElementType key = GetNodeMin((*root)->right);
            (*root)->data = key;

            // delete the min node in right subtree
            // In effect, the question is shifted to deleting the min node in right subtree
            AVLTreeDeleteRun(&(*root)->right, key);

            int leftHeight = GetNodeHeight((*root)->left);
            int rightHeight = GetNodeHeight((*root)->right);
            // after delete, we need check if the tree is balanced
            // in this case, we delete the min node in right subtree,
            // so leftHeight >= rightHeight
            if (leftHeight - rightHeight == 2) {
                // check >= , not >
                if (GetNodeHeight((*root)->left->left) >=
                    GetNodeHeight((*root)->left->right)) {
                    // type LL
                    RightRotation(root);
                } else {
                    // type LR
                    LeftRotation(&(*root)->left);
                    RightRotation(root);
                }
            }
        } else if ((*root)->left == NULL) {
            // left subtree is empty
            AVLNode *temp = *root;
            *root = (*root)->right;
            free(temp);
            temp = NULL;
            return true;
        } else {
            // right subtree is empty
            AVLNode *temp = *root;
            *root = (*root)->left;
            free(temp);
            temp = NULL;
            return true;
        }
    } else if ((*root)->data < data) {
        // find in right subtree
        status result = AVLTreeDeleteRun(&(*root)->right, data);
        if (result == false)
            return false;
        else if (result == error)
            return error;

        int leftHeight = GetNodeHeight((*root)->left);
        int rightHeight = GetNodeHeight((*root)->right);
        // after delete, we need check if the tree is balanced
        // in this case, we delete in right subtree,
        // so leftHeight >= rightHeight
        if (leftHeight - rightHeight == 2) {
            // check >= , not >
            if (GetNodeHeight((*root)->left->left) >=
                GetNodeHeight((*root)->left->right)) {
                // type LL
                RightRotation(root);
            } else {
                // type LR
                LeftRotation(&(*root)->left);
                RightRotation(root);
            }
        }
    } else {
        // find in left subtree
        status result = AVLTreeDeleteRun(&(*root)->left, data);
        if (result == false)
            return false;
        else if (result == error)
            return error;

        int leftHeight = GetNodeHeight((*root)->left);
        int rightHeight = GetNodeHeight((*root)->right);
        // after delete, we need check if the tree is balanced
        // in this case, we delete in left subtree,
        // so rightHeight >= leftHeight
        if (rightHeight - leftHeight == 2) {
            // check >= , not >
            if (GetNodeHeight((*root)->right->right) >=
                GetNodeHeight((*root)->right->left)) {
                // type RR
                LeftRotation(root);
            } else {
                // type RL
                RightRotation(&(*root)->right);
                LeftRotation(root);
            }
        }
    }

    // update height if abs(leftHeight - rightHeight) != 2 (?)
    (*root)->height =
            max(GetNodeHeight((*root)->left), GetNodeHeight((*root)->right)) +
            1;
    return true;
}

// search
status AVLTreeSearch(AVLTree *tree, ElementType data) {
    if (tree == NULL) {
        printf("tree is NULL\n");
        return error;
    }
    if (tree->root == NULL) {
        printf("tree is empty\n");
        return false;
    }
    AVLNode *node = tree->root;
    while (node != NULL) {
        if (node->data == data) {
            return true;
        } else if (node->data > data) {
            node = node->left;
        } else {
            node = node->right;
        }
    }
    return false;
}

// get max and min
status AVLTreeGetMax(AVLTree *tree, ElementType *result) {
    if (tree == NULL) {
        printf("tree is NULL\n");
        return error;
    }
    if (tree->root == NULL) {
        printf("tree is empty\n");
        return error;
    }
    AVLNode *node = tree->root;
    while (node->right != NULL) {
        node = node->right;
    }
    *result = node->data;
    return true;
}

status AVLTreeGetMin(AVLTree *tree, ElementType *result) {
    if (tree == NULL) {
        printf("tree is NULL\n");
        return error;
    }
    if (tree->root == NULL) {
        printf("tree is empty\n");
        return error;
    }
    AVLNode *node = tree->root;
    while (node->left != NULL) {
        node = node->left;
    }
    *result = node->data;
    return true;
}

// get status
int AVLTreeGetHeight(AVLTree *tree) {
    if (tree == NULL)
        return -1;
    if (tree->root == NULL)
        return 0;
    return tree->root->height;
}

int GetNodeHeight(AVLNode *node) {
    if (node == NULL)
        return 0;
    return node->height;
}

ElementType GetNodeMax(AVLNode *node) {
    if (node == NULL)
        return -1;
    while (node->right != NULL) {
        node = node->right;
    }
    return node->data;
}

ElementType GetNodeMin(AVLNode *node) {
    if (node == NULL)
        return -1;
    while (node->left != NULL) {
        node = node->left;
    }
    return node->data;
}

int AVLTreeGetSize(AVLTree *tree) {
    if (tree == NULL)
        return -1;
    return tree->size;
}

status AVLTreeIsEmpty(AVLTree *tree) {
    if (tree == NULL)
        return error;
    return tree->size == 0;
}

// rotate
void LeftRotation(AVLNode **root) {
    AVLNode *node = *root;
    AVLNode *temp = node->right;
    // rotate
    node->right = temp->left;
    temp->left = node;
    *root = temp;
    // update height
    node->height =
            max(GetNodeHeight(node->left), GetNodeHeight(node->right)) + 1;
    temp->height = max(GetNodeHeight(node), GetNodeHeight(temp->right)) + 1;
}

void RightRotation(AVLNode **root) {
    AVLNode *node = *root;
    AVLNode *temp = node->left;
    // rotate
    node->left = temp->right;
    temp->right = node;
    *root = temp;
    // update height
    node->height =
            max(GetNodeHeight(node->left), GetNodeHeight(node->right)) + 1;
    temp->height = max(GetNodeHeight(node), GetNodeHeight(temp->left)) + 1;
}

// private functions
int max(int a, int b) {
    return a > b ? a : b;
}

测试代码test.c:

//
// Created by WAHAHA on 2023/12/10.
//

#include <stdio.h>
#include "AVLTree.h"

int main() {
    int nums[] = {5, 3, 6, 2, 4, 0, 8, 1, 7, 9};
    AVLTree *tree = AVLTreeCreate();
    for (int i = 0; i < 10; ++i) {
        AVLTreeInsert(tree, nums[i]);
    }
    printf("size: %d\n", AVLTreeGetSize(tree));
    while (!AVLTreeIsEmpty(tree)) {
        ElementType result;
        AVLTreeGetMin(tree, &result);
        printf("%d ", result);
        AVLTreeDelete(tree, result);
    }
    printf("\n");
    AVLTreeDestroy(tree);
    return 0;
}

运行结果:

size: 10
0 1 2 3 4 5 6 7 8 9

参考:

AVL树原理及实现

AVL树

—WAHAHA 2023.12.10