Catshao

用户名：Catshao

访问量：29114

签　名：

stO KHIN Orz

等　　级
排　　名	159
经　　验	7166
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

8月月赛总结（附题解）
浏览：101

Dotcpp国庆Div.2题解
浏览：165

[ω] 最大子段乘积
浏览：108

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

数据结构-AVL详解（C++代码）（小白向）

　　作者: Catshao　　　　发表时间：2021-02-06 21:41:32 浏览：370　|　评论：0　

原题链接：数据结构-平衡二叉树的基本操作

# Part -1 前置算法

由于平衡二叉树的目的是调整平衡，使搜索的速度保持`logn`，所以请在学任何平衡树之前请了解有关于**二叉搜索树**的特性与基本操作（增删改查）

# Part 1 基础概念

AVL是一种非常经典的调整平衡的思路，使用**平衡因子**来保持平衡。

#### 平衡因子

平衡因子的英文为`Balance Factor`，在代码中简称`bf`

平衡因子的计算方法为`左子树高度 - 右子树高度`，当`这个值的绝对值>1`时，这棵树就会不平衡。举一个例子：

![不平衡](http://cat-shao.gitee.io/mypic/不平衡.jpg)

这个例子明显是一个不平衡的例子，于是一个节点的平衡因子超出范围。

## 旋转

我们通过左旋和右旋来调整AVL树，使树平衡。

>（动图可能加载不出来，请重新刷新（图如果丢了请及时告诉作者），转载自[最容易懂得红黑树](https://blog.csdn.net/sun_tttt/article/details/65445754)）

#### 左旋

![左旋](http://cat-shao.gitee.io/mypic/leftRotate.png)

![左旋](https://i.loli.net/2021/01/25/No8QsnYejPhgOUG.gif)

`x`变为y的左子节点，`2号节点`变为`x`的右子节点。

#### 右旋

![右旋](http://cat-shao.gitee.io/mypic/rightRotate.png)

![右旋](https://i.loli.net/2021/01/25/RCpSzlFEY1AfjiK.gif)

`x`变为y的右子节点，`2号节点`变为`x`的左子节点。

## 调整平衡

#### 左左局面（ll）

![左左](http://cat-shao.gitee.io/mypic/ll.png)

1. 以`x`为轴进行右旋，使二叉树平衡。

#### 右右局面（rr）

![右右](http://cat-shao.gitee.io/mypic/rr.png)

1. 以`x`为轴进行左旋，使二叉树平衡。

#### 左右局面（lr）

![左右](http://cat-shao.gitee.io/mypic/lr.png)

1. 首先以`y`为轴进行左旋，形成左左局面。
2. 然后以`x`为轴进行右旋，使二叉树平衡。

#### 右左局面（rl）

![右左](http://cat-shao.gitee.io/mypic/rl.png)

1. 首先以`y`为轴进行右旋，形成右右局面。
2. 然后以`x`为轴进行左旋，使二叉树平衡。

# Part 2 相关操作

## 插入

首先使用**二叉搜索树**的插入方式插入一个节点，之后由这个节点开始向上更新**树高和平衡因子，调整平衡**。

拿刚开始的图举例子：

![不平衡](http://cat-shao.gitee.io/mypic/不平衡.jpg)

我们插入了一个`7`，但父节点`6`的平衡因子**经过更新**均未超出范围，于是我们到节点`5`，平衡因子的绝对值超出2，我们发现这是一个**右右局面**，于是我们**左旋**，左旋后二叉树得到了平衡。

![插入后平衡](http://cat-shao.gitee.io/mypic/insertExample.png)

#### 更新值

更新树的高度的方式：`高度 = max(左孩子高度， 右孩子高度) + 1`
更新平衡因子的方式：`平衡因子 = 左子树高度 - 右子树高度`，（因为使用了高度，所以在**更新平衡因子之前要更新高度**）

#### 对局面的判断

![第一组平衡因子](http://cat-shao.gitee.io/mypic/rrllbf.png)

![第二组平衡因子](http://cat-shao.gitee.io/mypic/lrrlbf.png)

用`bf`表示自己的平衡因子，`leftBf`表示左子树的平衡因子，`rightBf`表示右子树的平衡因子，就有（**下列判断基于自己的平衡因子超出范围`2`**）：
- 左左：`bf为正 且 leftBf > 0`
- 右右：`bf为负 且 rightBf < 0`
- 左右：`bf为正 且 leftBf < 0`
- 右左：`bf为负 且 rightBf > 0`

# Part 3 实现

#### 不实现parent

AVL树可以不实现parent，使用递归来实现回溯到上层。[详细图文——AVL树](https://blog.csdn.net/qq_25343557/article/details/89110319)中用了**java**来实现的AVL树。

## 我的代码

之后可能会更新删除、查找等功能，这里先放一下目前的代码。

**（remove重写后炸了，建议只看insert）**

```cpp
//
// Created by Cat-shao on 2021/1/28.
//

#include <cstdio>
#include <algorithm>
using namespace std;

namespace avl {
    template<typename T>
    class avlNode {
    public:
        T data;
        avlNode *parent;
        avlNode *left;
        avlNode *right;
        int count, size, height;

avlNode(const T &d) {
            data = d;
            parent = NULL;
            left = NULL;
            right = NULL;
            count = 1;
            size = 1;
            height = 1;
        }

avlNode() {

}

bool isLeftChild() {
            if (parent == NULL) {
                return true; // 在没有双亲节点（为根节点）的情况下设节点为做节点
            }
            return parent->left == this;
        }

bool isLeaf() {
            if (left == NULL && right == NULL) {
                return true;
            }
            return false;
        }
    };

template<typename T>
    class avlTree {
    private:
        typedef avlNode<T> node;
        node *root;

void destroy(node *current) {
            if (current == NULL) {
                return;
            }
            destroy(current->left);
            destroy(current->right);
            delete current;
        }

int getHeight(node *current) {
            if (current == NULL) {
                return 0;
            } else {
                return current->height;
            }
        }

int getSize(node *current) {
            if (current == NULL) {
                return 0;
            } else {
                return current->size;
            }
        }

void updateHeight(node* current) {
            current->height = max(getHeight(current->left), getHeight(current->right)) + 1;
        }

void updateSize(node *current) {
            current->size = getSize(current->left) + getSize(current->right) + 1;
        }

int getBF(node* current) {
            if (current == NULL) {
                return 0;
            }
            return getHeight(current->left) - getHeight(current->right);
        }

void printNode(node* current) {
            if (current == NULL) {
                return;
            }

printf("n%d[label = \"%d\"]\n", current, current->data);

if (current->left != NULL) {
                printf("n%d -> n%d[style = blod, taillabel = \"%d\"]\n", current, current->left, getBF(current));
            } else {
                printf("null%d[label = \"null\", style = dotted]\n", current);
                printf("n%d -> null%d[style = dotted, taillabel = \"%d\"]\n", current, current, getBF(current));
            }

if (current->right != NULL) {
                printf("n%d -> n%d[style = blod, taillabel = \"%d\"]\n", current, current->right, getBF(current));
            } else {
                printf("null%d[label = \"null\", style = dotted]\n", current + 1);
                printf("n%d -> null%d[style = dotted, taillabel = \"%d\"]\n", current, current + 1, getBF(current));
            }
            printNode(current->left);
            printNode(current->right);
        }

void printTree() { // 显示图
            freopen("tree.dot", "w", stdout);
            printf("digraph {\n");
            printNode(root);
            printf("}");
            freopen("CON", "w", stdout);
            printf("output .dot file in tree.dot\n");
        }

void remove(node *current) {
            node *parent = current->parent;
            node *replace;
            if (current->count > 1) {
                current->count--;
            } else if (current->isLeaf()) { // current为叶子节点
                if (current != root) {
                    if (current->isLeftChild()) {
                        parent->left = NULL;
                    } else {
                        parent->right = NULL;
                    }
                } else {
                    root = NULL;
                }
                delete current;
            } else {
                if (current->left == NULL) {
                    replace = current->right;
                } else if (current->right == NULL) {
                    replace = current->left;
                } else {
                    replace = findMin(current->right);
                }

if (current->left != NULL && current->right != NULL) {
                    replace->left = current->left;
                    replace->right = current->right;
                    if (replace->isLeftChild()) {
                        replace->parent->left = NULL;
                    } else {
                        replace->parent->right = NULL;
                    }
                    replace->left->parent = replace;
                    replace->right->parent = replace;
                }

if (current != root) {
                    if (current->isLeftChild()) {
                        parent->left = replace;
                    } else {
                        parent->right = replace;
                    }
                    replace->parent = parent;
                } else {
                    root = replace;
                    root->parent = NULL;
                }
                delete current;
            }

changeBalance(parent);
        }

public:
        avlTree() {
            root = NULL;
        }
        ~avlTree() {
            destroy(root);
        }

bool empty() {
            return root == NULL;
        }

void clean() {
            destroy(root);
            root = NULL;
        }

void leftRotate(node *parent) {
            node* current = parent->right;

parent->right = current->left;
            if (current->left != NULL) {
                current->left->parent = parent;
            }

if (parent == root) {
                current->parent = NULL;
                root = current;
            } else {
                current->parent = parent->parent;
                if (parent->isLeftChild()) {
                    parent->parent->left = current;
                } else {
                    parent->parent->right = current;
                }
            }

current->left = parent;
            parent->parent = current;

updateHeight(parent);
            updateSize(parent);

updateHeight(current);
            updateSize(current);
        }

void rightRotate(node *parent) {
            node* current = parent->left;

parent->left = current->right;

if (current->right != NULL) {
                current->right->parent = parent;
            }

current->right = parent;
            parent->parent = current;

updateHeight(parent);
            updateSize(parent);

updateHeight(current);
            updateSize(current);
        }

void changeBalance(node *parent) {
            node *current;
            while (parent != NULL) { // 遍历回root
                updateHeight(parent);
                updateSize(parent);
                int bf = getBF(parent), leftBf = getBF(parent->left), rightBf = getBF(parent->right);
                bool positive = bf > 1, negative = bf < -1;

current = parent->parent;

if (positive && leftBf > 0) {
                    rightRotate(parent);
                } else if (negative && rightBf < 0) {
                    leftRotate(parent);
                } else if (positive && leftBf < 0) {
                    leftRotate(parent->left);
                    rightRotate(parent);
                } else if (negative && rightBf > 0) {
                    rightRotate(parent->right);
                    leftRotate(parent);
                }
                parent = current;
            }
        }

void insert(const T &input) {
            if (root == NULL) {
                root = new node(input);
                return;
            }

node *current;
            node *parent;
            current = root;
            while (current != NULL) {
                parent = current;
                if (input < current->data) {
                    current = current->left;
                } else if (input > current->data) {
                    current = current->right;
                } else if (input == current->data) {
                    current->count ++;
                    return;
                }
            }

if (input < parent->data) {
                parent->left = new node(input);
                parent->left->parent = parent;
            }
            if (input > parent->data) {
                parent->right = new node(input);
                parent->right->parent = parent;
            }

changeBalance(parent);
        }

node* find(const T &input) {
            node *current;
            current = root;
            while (current != NULL) {
                if (input < current->data) {
                    current = current->left;
                } else if (input > current->data) {
                    current = current->right;
                } else if (input == current->data) {
                    return current;
                }
            }
            return NULL; // 找不到
        }

node* findMax(node *current) {
            if (current->right == NULL) {
                return current;
            }
            return findMax(current->right);
        }

node* findMin(node *current) {
            if (current->left == NULL) {
                return current;
            }
            return findMax(current->left);
        }

node* top() {
            return root;
        }

void remove(const T &input) {
            node *current = find(input);
            if (current == NULL) {
                return;
            }
            remove(current);
        }

void print() {
            printTree();
        }
    };
}

int main()
{
    avl::avlTree<int> tree;
    int n, k, v;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &v);
        tree.insert(v);
    }

for (int i = 0; i < k; ++i) {
        scanf("%d", &v);
        if (tree.find(v) == NULL) {
            printf("0 ");
        } else {
            printf("1 ");
        }
    }
//    tree.remove(1);
//    tree.print();
    return 0;
}
```

--------------
预计更新列表：
1. 插入（已更新）
2. 删除

参考：
1. [程序员小灰](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653206226&idx=2&sn=9026eddb485cecc91171e75c118d1231)
2. [详细图文——AVL树](https://blog.csdn.net/qq_25343557/article/details/89110319)

更新表：
1. 2021/2/8 发现画的图没传。

0.0分

2 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

亲和的解法

【出圈】（C++代码）（典型的约瑟夫环——链表解决）

数据结构-AVL详解（C++代码）（小白向）

评论区

精彩推荐

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

回文串（C语言代码）

WU-判定字符位置（C++代码）

【绝对值排序】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

矩形面积交（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

亲和的解法

【出圈】 （C++代码）（典型的约瑟夫环——链表解决）

数据结构-AVL详解（C++代码）（小白向）

评论区

精彩推荐

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

回文串 （C语言代码）

WU-判定字符位置 （C++代码）

【绝对值排序】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

矩形面积交 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

母牛的故事（C语言代码）

【出圈】（C++代码）（典型的约瑟夫环——链表解决）

　　评论区

回文串（C语言代码）

WU-判定字符位置（C++代码）

【绝对值排序】（C语言代码）

矩形面积交（C++代码）