AVL(平衡二叉树)

AVLTree.cpp

//
// Created by jvm on 4/12/19.
// AVL 树
// 平衡二叉树(AVL)实现
// Doc: https://blog.csdn.net/u014634338/article/details/42465089
// Doc: http://www.cnblogs.com/gaochundong/p/binary_search_tree.html
// Doc: https://blog.zhenlanghuo.top/2017/08/22/AVL%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AE%9E%E7%8E%B0/
//

typedef int ElementType;

class AVLNode {
private:
    int max(a, b int) {
        return a > b? a: b;
    }
    int height(const AVLNode* node) {
        return node?node->h:-1
    }

public:
    AVLNode* left;
    AVLNode* right;
    ElementType val;
    int h; // 以此节点为根的树的高度

    AVLNode(ElementType val): val(val) {
        left = nullptr;
        right = nullptr;
        h = 0;
    }

    AVLNode* LL_rotate(AVLNode* node);
    AVLNode* RR_rotate(AVLNode* node);
    AVLNode* LR_rotate(AVLNode* node);
    AVLNode* RL_rotate(AVLNode* node);
};

// LL型(左孩子的左子树) 通过右旋解决
AVLNode* AVLNode::LL_rotate(AVLNode *node) {
    // node: 失衡点

    // 失衡点的左孩子
    AVLNode* left = node->left;

    // 将失衡点的左孩子更新为left的右子树
    node->left = left->right;
    // 失衡点右旋， 变成left的右孩子
    left->right = node;

    // 更新left和失衡点的高度
    node->h = 1 + max(height(node->left), height(node->right));
    left->h = 1 + max(height(left->right), node->h);

    return left;
}

// RR型(右孩子右子树) 通过左旋解决
AVLNode* AVLNode::RR_rotate(AVLNode *node) {
    AVLNode* right = node->right;

    node->right = right->left;
    right->left = node;

    // 更新right和失衡点的高度
    node->h = 1 + max(height(node->left), height(node->right));
    right->h = 1 + max(height(right->left), node->h);

    return right;
}

// LR型, 先左旋后右旋
AVLNode* AVLNode::LR_rotate(AVLNode* node) {
    node->left = LL_rotate(node->left);
    return RR_rotate(node);
}

// RL型, 先右旋后左旋
AVLNode* AVLNode::RL_rotate(AVLNode* node) {
    node->right = RR_rotate(node->right);
    return LL_rotate(node);
}