AVL树是一种自平衡二叉搜索树(BST),对于所有节点,其左右子树的高度差不能超过1。

大多数BST操作(例如:搜索,最大,最小,插入,删除)以O(h)为时间,h是BST的高度。对于倾斜的二叉树,这些操作的成本可能变成O(n)。如果我们确保在每次插入和删除之后树的高度仍然是O(Logn),那么我们就可以保证所有这些操作的O(Logn)的上界。AVL树的高度总是O(Logn),其中n是树中的节点数。

左旋和右旋

# 右旋 (左边树,针对根节点为 x 的子树右旋)
# 左旋 (右边树,针对根节点为 y 的子树左旋)
       y                                x
      / \      右旋转                  /  \
     x   T3    – – – – – – – >        T1   y
    / \        < - - - - - - -            / \
   T1  T2      左旋转                    T2  T3

插入key操作

为了确保在每次插入之后给定的树仍然是AVL,我们必须增加标准的BST插入操作来执行一些重新平衡。左旋转 和 右旋转 两个操作可以在不违反BST属性(key(左)< key(根)< keys(右))的情况下重新平衡BST。

针对插入新节点 w

  • 执行标准的插入(从树的根节点开始向下遍历,w 的 key 大于子树的根结点则向右遍历,否则向左遍历。直到找到节点为 NULL 的地方,把 w 节点插入该位置)
  • 从 w 节点向上移动(w 节点高度为 1,向上移动顺次更新各个节点高度),找到第一个不平衡节点(针对AVL树不满足左子树和右子树高度差不超过1这一条件的节点)。设 z 是第一个不平衡节点,y 是 z 的子结点,x 是 z 的孙子结点。
  • 通过对以z为根的子树进行适当的旋转来重新平衡树。有4种可能的情况需要处理,因为x、y 和 z 有4种排列方式,如下所示:

① y 是 z 的左子结点 x 是 y 的左子结点(左下)

左左 --- 右旋
T1, T2, T3 和 T4 是子树。
假设字数 T1 T2 高度都为 1 括号值为每个节点高度,显然 z 节点 左子树 和 其左右子树的高度超过了 1
旋转前提:
  调整的办法就是降低高度高的那一个节点
  由二叉搜索树性质(左子树 < 根节点 < 右子树)得出: z > y、T4 > z、 T3 < z

        (4)z                                       y
        /   \                                    /   \
      (3)y (2)T4      右旋 (z)                  x      z
       /   \          - - - - - - - - ->      /  \    /  \
     (2)x  (1)T3                             T1   T2  T3  T4
      /   \
T1(1)   T2(1)

② y是z的左子结点x是y的右子结点(左右图)

左右 -- 左旋 + 右旋
T1, T2, T3 和 T4 是子树
        z                               z                           x
       / \                            /   \                        /  \
      y   T4  左旋 (y)                x    T4  右旋(z)            y      z
     / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
   T1   x                          y    T3                    T1  T2 T3  T4
        / \                        / \
      T2   T3                    T1   T2

③ y是z的右子结点x是y的右子结点

右右 -- 左旋
T1, T2, T3 和 T4 是子树
       z                                y
      /  \                            /   \
     T1   y      左旋(z)             z      x
         /  \   - - - - - - - ->    / \    / \
        T2   x                     T1  T2 T3  T4
            / \
          T3  T4

④ y是z的右子结点x是y的左子结点(右左)

右左 -- 右旋 + 左旋
T1, T2, T3 和 T4 是子树
       z                            z                            x
      / \                          / \                          /  \
    T1   y   右旋 (y)             T1   x      左旋(z)          z      y
        / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
       x   T4                      T2   y                  T1  T2  T3  T4
      / \                              /  \
    T2   T3                           T3   T4

代码实现

代码中暂时主要只针对 “左左” 进行了检测(详见:主函数注释),配合前序遍历和后续遍历可检查树的结构是否正确。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    int height;
};

// 获得节点高度
int height(struct Node* n) {
    if (NULL == n) {
        return 0;
    }
    return n->height;
}

// 获取整数较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 创建新节点
struct Node* new_node(int key) {
    struct Node* node = (struct Node*) malloc(sizeof (struct Node));
    memset(node, 0, sizeof (struct Node));

    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;

    return node;
}

// 右旋
struct Node* right_rotate(struct Node* z) {
    struct Node* x = z->left;
    struct Node* T2 = x->right;

    x->right = z;
    z->left = T2;

    z->height = 1 + max(height(z->left), height(z->right));
    x->height = 1 + max(height(x->left), height(x->right));

    return x;
}

// 左旋
struct Node* left_rotate(struct Node* z) {
    struct Node* y = z->right;
    struct Node* T2 = y->left;

    y->left = z;
    z->right = T2;

    z->height = 1 + max(height(z->left), height(z->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y;
}

// 节点的平衡系数
int get_balance(struct Node* n) {
    if (NULL == n) {
        return 1;
    }

    return height(n->left) - height(n->right);
}

// 插入操作
struct Node* insert(struct Node* node, int key) {
    // 1. 执行插入操作
    if (NULL == node) {
        return (new_node(key));
    }

    if (key < node->key) { // key 值小于根节点 key 值,则向左子树遍历
        node->left = insert(node->left, key);
    } else if (key > node->key) { // key 值大于根节点 key 值,则向右子树遍历
        node->right = insert(node->right, key);
    } else { // key 值重复,直接返回
        return node;
    }

    // 更新节点高度, 插入新节点后,新节点的祖先节点高度需要更新,知道 root 根节点。
    node->height = 1 + max(height(node->left), height(node->right));
//    printf("%d(%d)\n", node->key, node->height);

    // 检查是否失衡
    int balance = get_balance(node);

    // 如果失衡 有四种情况
    if(balance > 1 && key < node->left->key) {// 左左 -- node 处为不平衡子树的根节点、key < 跟节点左子树, 则新节点在左边
        return right_rotate(node);
    } else if (balance > 1 && key > node->left->key) { // 左右
        node->left = left_rotate(node->left);
        return right_rotate(node);
    } else if (balance < -1 && key < node->right->key) {
        node->right = right_rotate(node->left);
        return left_rotate(node);
    } else if (balance < -1 && key > node->right->key) {
        return left_rotate(node);
    }

    // 不需要调整
    return node;
}

// 前序遍历
void pre_order(struct Node* root) {
    if (NULL != root) {
        printf("%d(%d) ", root->key, root->height);
        pre_order(root->left);
        pre_order(root->right);
    }
}

// 后序遍历
void post_order(struct Node* root) {
    if (NULL != root) {
        post_order(root->left);
        post_order(root->right);
        printf("%d(%d) ", root->key, root->height);
    }
}

int main(void) {

    struct Node* root = NULL;
    /**
     *  10、20、30
     *      20
     *    /   \
     *  10    30
     *
     *
     *  10、20、30、40
     *      20
     *     / \
     *    10 30
     *        \
     *        40
     *
     *  10、20、30、40、50
     *      20                                                  20
     *     / \                                              /       \
     *    10 30(3)          ----->                         10       40
     *        \                                                   /    \
     *        40(2)                                              30     50
     *         \
     *         50(1)
     *
     *  10、20、30、40、50、60
     *             20(4)                                     40
     *          /     \                                   /    \
     *         10(1)  40(3)        ------->             20     50
     *               /  \                              / \      \
     *              30  50(2)                         10 30     60
     *                   \
     *                   60(1)
     *
     * 10、20、30、40、50、60、70
     *              40                                      40
     *            /   \                                   /     \
     *          20    50                                20      60
     *         / \     \    ----------->              /   \    /  \
     *        10 30    60                            10   30  50  70
     *                  \
     *                  70
     */

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 60);
    root = insert(root, 70);
    root = insert(root, 80);
    root = insert(root, 90);
    root = insert(root, 100);
    root = insert(root, 110);
    root = insert(root, 120);


    pre_order(root);
    puts("\n");
    post_order(root);

    return 0;
}

删除key操作

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    int height;
};

// 获得节点高度
int height(struct Node* n) {
    if (NULL == n) {
        return 0;
    }
    return n->height;
}

// 获取整数较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 创建新节点
struct Node* new_node(int key) {
    struct Node* node = (struct Node*) malloc(sizeof (struct Node));
    memset(node, 0, sizeof (struct Node));

    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;

    return node;
}

// 右旋
struct Node* right_rotate(struct Node* z) {
    struct Node* x = z->left;
    struct Node* T2 = x->right;

    x->right = z;
    z->left = T2;

    z->height = 1 + max(height(z->left), height(z->right));
    x->height = 1 + max(height(x->left), height(x->right));

    return x;
}

// 左旋
struct Node* left_rotate(struct Node* z) {
    struct Node* y = z->right;
    struct Node* T2 = y->left;

    y->left = z;
    z->right = T2;

    z->height = 1 + max(height(z->left), height(z->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y;
}

// 节点的平衡系数
int get_balance(struct Node* n) {
    if (NULL == n) {
        return 1;
    }

    return height(n->left) - height(n->right);
}

// 返回键值最小的节点
struct Node* min_value_node(struct Node* node) {
    struct Node* current = node;

    while (NULL != current->left) {
        current = current->left;
    }

    return current;
}

// 插入操作
struct Node* insert(struct Node* node, int key) {
    // 1. 执行插入操作
    if (NULL == node) {
        return (new_node(key));
    }

    if (key < node->key) { // key 值小于根节点 key 值,则向左子树遍历
        node->left = insert(node->left, key);
    } else if (key > node->key) { // key 值大于根节点 key 值,则向右子树遍历
        node->right = insert(node->right, key);
    } else { // key 值重复,直接返回
        return node;
    }

    // 更新节点高度, 插入新节点后,新节点的祖先节点高度需要更新,知道 root 根节点。
    node->height = 1 + max(height(node->left), height(node->right));
//    printf("%d(%d)\n", node->key, node->height);

    // 检查是否失衡
    int balance = get_balance(node);

    // 如果失衡 有四种情况
    if(balance > 1 && key < node->left->key) {// 左左 -- node 处为不平衡子树的根节点、key < 跟节点左子树, 则新节点在左边
        return right_rotate(node);
    } else if (balance > 1 && key > node->left->key) { // 左右
        node->left = left_rotate(node->left);
        return right_rotate(node);
    } else if (balance < -1 && key < node->right->key) {
        node->right = right_rotate(node->left);
        return left_rotate(node);
    } else if (balance < -1 && key > node->right->key) {
        return left_rotate(node);
    }

    // 不需要调整
    return node;
}

struct Node* delete (struct Node* node, int key) {
    if (NULL == node) {
        return node;
    }

    // 删除指定key的节点
    if (key < node->key) { // 小于根节点 向左遍历接着找
        node->left = delete(node->left, key);
    } else if (key > node->key) {
        node->right = delete(node->right, key);
    } else { // 要找的 key 就是此时的跟节点
        if((NULL == node->left) || (NULL == node->right)) { // 最多有一个子树的情况
            struct Node* tmp = (node->left != NULL) ? node->left : node->right;

            if (NULL == tmp) { // 没有子树的情况
                tmp = node;
                node = NULL;
            } else { // 只有一个子树
                *node = *tmp; // 深拷贝 用tmp的值覆盖了 node, 相当于删除
                free(tmp);  // 删除多一份的 tmp 值
            }
        } else { // 删除要查找的key 并以此右子树最小值替代此时根节点的值,删除右子树被替代的值
            struct Node* tmp = min_value_node(node->right);
            node->key = tmp->key;
            node->right = delete(node->right, tmp->key);
        }
    }

    if(NULL == node) { // tree 只有一个节点则返回
        return node;
    }

    // 更新 tree 的高度 从删除掉的节点开始依次向根节点更新
    node->height = 1 + max(height(node->left), height(node->right));

    // 检测是否平衡
    int balance = get_balance(node);

    // 四种可能的不平衡状态
    if(balance > 1 && key < node->left->key) {// 左左 -- node 处为不平衡子树的根节点、key < 跟节点左子树, 则新节点在左边
        return right_rotate(node);
    } else if (balance > 1 && key > node->left->key) { // 左右
        node->left = left_rotate(node->left);
        return right_rotate(node);
    } else if (balance < -1 && key < node->right->key) {
        node->right = right_rotate(node->left);
        return left_rotate(node);
    } else if (balance < -1 && key > node->right->key) {
        return left_rotate(node);
    }

    // 平衡
    return node;
}

// 前序遍历
void pre_order(struct Node* root) {
    if (NULL != root) {
        printf("%d(%d) ", root->key, root->height);
        pre_order(root->left);
        pre_order(root->right);
    }
}

// 后序遍历
void post_order(struct Node* root) {
    if (NULL != root) {
        post_order(root->left);
        post_order(root->right);
        printf("%d(%d) ", root->key, root->height);
    }
}

int main(void) {

    struct Node* root = NULL;
    /**
     * 10、20、30、40、50、60、70
     *            40
     *         /     \
     *       20      60
     *     /   \    /  \
     *    10   30  50  70
     *
     * 删除 key = 60
     *          40
     *       /     \
     *      20     70
     *    /   \    /
     *   10   30  50
     *
     * 删除 key = 40
                50
     *       /     \
     *      20     60
     *    /   \     \
     *   10   30    70
     *
     *
     */

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 60);
    root = insert(root, 70);

    root = delete(root, 40);

    //root = delete(root, 60);


    pre_order(root);
    puts("\n");
    post_order(root);

    return 0;
}

修改key操作

修改key操作可以由删除和插入组合而成.

查找key操作

直接从根节点开始递归遍历,找到指定 key 则返回;若已经到达了叶子节点(左子树和右子树都是 NULL)依然没有没找到指定 key,则说明key不存在。

文章目录