Vanadium的小屋

Lecture 1

AVL Tree

Defination

平衡因子 balance factor = h(L) - h(R)

定义 AVL Tree: 每个节点的 BF 满足

$$|BF| \le 1 \tag{1}$$

Rotation

对节点操作后, 需要通过旋转 Rotation 进行维护, 以满足条件 (1)

旋转分为右旋和左旋

Insertion

1. insert as in BST
2. restore the balance with rotation ($O(\log n )$ nodes become imbalanced)

首先从插入点开始, 向上找到第一个不平衡点 u

1. LL case 对 u 右旋
2. RR case 对 u 左旋
3. LR case 对 v 左旋后转化为 LL case
4. RL case 对 v 右旋后转化为 RR case

Deletion

1. delete as in BST
2. restore balance

[Lemma] Every deletion in AVL Tree is essentially to remove a leave

同样的, 从删除的叶子节点向上找到第一个不平衡点, 按照上文提到的方法维护即可

Q: 删除节点后, 有多少个节点会不平衡?
A: 一个

Q: 多少次旋转后, AVL Tree 会平衡?
A: log n

为了减少删除时, 旋转的开支, 引入红黑树

Red Black Tree

Final Exam 前背就行

Appendix

AVL 树插入操作的 C++ version

#include<iostream>

using namespace std;

struct AvlTree{
    int value, height;
    AvlTree* left_child;
    AvlTree* right_child;

    AvlTree(){
        this->value = -1;
        this->height = 0;
        this->left_child = this->right_child = nullptr;
    }

    int get_height();
    int get_value();
    void insert(int x);
    void left_rotation();
    void right_rotation();
    void left_right_rotation();
    void right_left_rotation();
    void update_height();
};

void AvlTree::update_height(){
    this->height = max(this->left_child->get_height(), this->right_child->get_height()) + 1;
}

int AvlTree::get_value(){
    return this->value;
}

int AvlTree::get_height(){
    return this->height;
}

void AvlTree::insert(int x){
    if(this->value == -1){
        this->value = x;
        this->height = 0;
        this->left_child = new AvlTree();
        this->right_child = new AvlTree();
    }
    else if(x < this->value){
        this->left_child->insert(x);

        if(this->left_child->get_height() - this->right_child->get_height() >= 2){
            if(x < this->left_child->get_value()){    // LL
                this->right_rotation();
            }

            else{                               // LR
                this->left_right_rotation();
            }
        }
    }
    else{
        this->right_child->insert(x);

        if(this->right_child->get_height() - this->left_child->get_height() >= 2){
            if(x > this->right_child->get_value()){     // RR
                this->left_rotation();
            }

            else{                               // RL
                this->right_left_rotation();
            }
        }
    }

    this->update_height();
}

void AvlTree::left_rotation(){
    auto this_value = this->value;
    auto l = this->left_child;
    auto r = this->right_child;
    auto rl = this->right_child->left_child;
    auto rr = this->right_child->right_child;

    this->value = r->value;
    this->right_child = rr;
    this->left_child = new AvlTree();

    this->left_child->value = this_value;
    this->left_child->left_child = l;
    this->left_child->right_child = rl;
    
    this->left_child->update_height();

    this->update_height();
}

void AvlTree::right_rotation(){
    auto this_value = this->value;
    auto l = this->left_child;
    auto r = this->right_child;
    auto ll = this->left_child->left_child;
    auto lr = this->left_child->right_child;


    this->value = l->value;
    this->left_child = ll;
    this->right_child = new AvlTree();

    this->right_child->value = this_value;
    this->right_child->left_child = lr;
    this->right_child->right_child = r;
    
    this->right_child->update_height();

    this->update_height();

}

void AvlTree::left_right_rotation(){
    this->left_child->left_rotation();
    this->right_rotation();
}

void AvlTree::right_left_rotation(){
    this->right_child->right_rotation();
    this->left_rotation();
}

int main(){
    auto t = new AvlTree();
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        t->insert(x);
    }

    cout << t->get_value();
}