数据结构：树

敖炜 Lv5
  2023-11-08 17:56:16 2023-11-08 17:56:16 创建   2024-04-19 09:30:06 2024-04-19 09:30:06 更新      6.5k 字  30 分钟  

这一篇博客将介绍树

二叉树

二叉树是一种非线性数据结构

常用术语

  • 根节点：位于二叉树顶层的节点，没有父节点
  • 叶节点：没有子节点的节点，其两个指针均指向None
  • 边：连接两个节点的线段，即节点引用（指针）
  • 节点所在的层：从顶至底递增，根节点所在层为1
  • 节点的度：节点的子节点的数量
  • 二叉树的高度：从根节点到最远叶节点所经过的边的数量
  • 节点的深度：从根节点到该节点所经过的边的数量
  • 节点的高度：从距离该节点最远的叶节点到该节点所经过的边的数量

    以上部分术语的定义不唯一，可以是边的数量或节点的数量

二叉树的常用术语

基本操作

  1. 初始化二叉树

首先初始化节点，然后构建引用（指针）

  1. 插入与删除节点

通过修改指针来实现

在二叉树中插入与删除节点

常见二叉树类型

  1. 完美二叉树（满二叉树）: perfect binary tree

完美二叉树（满二叉树）所有层的节点都被完全填满，除叶节点外所有节点的度都为2。高度为的完美二叉树（满二叉树）节点总数为

完美二叉树

  1. 完全二叉树: complete binary tree

只有最底层的节点未被填满，且最底层节点尽量靠左填充

完全二叉树

  1. 完满二叉树: full binary tree

除了叶节点之外，其余所有节点都有两个子节点。所有节点的度都为0或2

完满二叉树

  1. 平衡二叉树: balanced binary tree

任意节点的左子树和右子树的高度之差的绝对值不超过1

平衡二叉树

二叉树的退化

  • 完美二叉树是理想情况，是最佳情况

  • 当所有节点都偏向一侧，二叉树退化为链表，无法体现分治的优势，是最差情况

二叉树的最佳与最差结构

完美二叉树 链表
第层节点数量
高度树的叶节点数量
高度树的节点总数
节点总数树的高度

二叉树遍历

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等

层序遍历

从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。本质上属于广度优先遍历(breadth-first traversal)，体现了一种一圈一圈向外扩展的逐层遍历方式

二叉树的层序遍历

  1. 代码实现

借助队列来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def level_order(root):
    queue = deque()
    queue.append(root)

    res = []
    while queue:
        node = queue.popleft()
        res.append(node.val)
        if node.left is not None:
            queue.qppend(node.left)
        if node.right is not None:
            queue.append(node.right)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> levelOrder(TreeNode* root){
    queue<TreeNode*> queue;
    queue.push(root);
    vector<int> res;

    while(!queue.empty()){
        TreeNode* node = queue.front();
        queue.pop();
        res.push_back(node->val);
        if (node->left != nullptr){
            queue.push_back(node->left);
        }
        if (node->right != nullptr){
            queue.push_back(node->right);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int* levelOrder(TreeNode* root, int* size){
    // 辅助队列
    int front, rear;
    int index;
    int* res;

    TreeNode* node;
    TreeNode** queue;
    queue = (TreeNode**)malloc(sizeof(TreeNode*) * MAX_SIZE);

    front = 0;
    rear = 0;
    queue[rear++] = root;

    res = (int*)malloc(sizeof(int) * MAX_SIZE);

    index = 0;
    while(front < rear){
        node = queue[front++];
        res[index++] = node->val;
        if(node->left != NULL){
            queue[rear++] = node->left;
        }
        if(node->right != NULL){
            queue[rear++] = node->right;
        }
    }

    *size = index;
    res = realloc(res, sizeof(int) * (*size));

    free(queue);
    return res;
}
  1. 复杂度分析

  • **时间复杂度**：所有节点被访问一次，使用时间，为节点数量

  • **空间复杂度**：最差情况下（满二叉树），遍历到最底层之前，队列中最多同时存在个节点，占用空间

前序、中序、后序遍历

前序、中序和后序遍历都属于深度优先遍历(depth-first traversal)，体现了一种先走到尽头，再回溯继续的思想

深度优先遍历就像是绕着整个二叉树的外围走一圈，再每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历

二叉搜索树的前、中、后序遍历

  1. 代码实现

深度优先遍历通常基于递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def pre_order(root, res):
    if root is None:
        return 
    res.append(root.val)
    pre_order(root=root.left, res)
    pre_order(root=root.right, res)

def in_order(root, res):
    if root is None:
        return
    in_order(root=root.left, res)
    res.append(root.val)
    in_order(root=root.right, res)

def post_order(root, res):
    if root is None:
        return
    post_order(root.left, res)
    post_order(root.right, res)
    res.append(root.val)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void preOrder(TreeNode *root, vector<int>& vec) {
    if (root == nullptr)
        return;
    vec.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode *root, vector<int>& vec) {
    if (root == nullptr)
        return;
    inOrder(root->left);
    vec.push_back(root->val);
    inOrder(root->right);
}

void postOrder(TreeNode *root, vector<int>& vec) {
    if (root == nullptr)
        return;
    postOrder(root->left);
    postOrder(root->right);
    vec.push_back(root->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void preOrder(TreeNode* root, int* size, int* arr){
    if(root == NULL){
        return;
    }
    arr[(*size)++] = root->val;
    preOrder(root->left, size);
    preOrder(root->right, size);
}

void inOrder(TreeNode *root, int *size, int* arr) {
    if (root == NULL)
        return;
    inOrder(root->left, size);
    arr[(*size)++] = root->val;
    inOrder(root->right, size);
}

void postOrder(TreeNode *root, int *size, int* arr) {
    if (root == NULL)
        return;
    postOrder(root->left, size);
    postOrder(root->right, size);
    arr[(*size)++] = root->val;
}

  • 递：表示开启新方法，程序再此过程中访问下一个节点

  • 归：表示函数返回，代表当前节点已经访问完毕

  1. 复杂度分析

  • **时间复杂度**：所有节点被访问一次，使用时间

  • **空间复杂度**：最差情况下（树退化为链表），递归深度为，占用栈帧空间

二叉树数组表示

表示完美二叉树

给定一个完美二叉树，将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引

若某个节点索引为，则其左子节点索引为，右子节点索引为

完美二叉树的数组表示

表示任意二叉树

对于非完美二叉树，前面的数组表示方法已经失效

层序遍历序列对应多种二叉树可能

因此我们可以在层序遍历序列中显式地写出所有None

完全二叉树非常适合使用数组来表示，其None一定出现在层序遍历序列的末尾，可以省略存储所有None

完全二叉树的数组表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class ArrayBinaryTree:

    def __init__(self, arr):
        self._tree = list(arr)

    def size(self):
        return len(self._tree)

    def val(self, i):
        if i < 0 or i >= self.size():
            return None
        return self._tree[i]

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def parent(self, i):
        return (i - 1) // 2

    def level_order(self):
        self.res = []
        for i in range(self.size()):
            if self.val(i) is not None:
                self.res.append(self.val(i))
        return self.res

    def dsf(self, i, order):
        if self.val(i) is None:
            return
        if order == "pre":
            self.res.append(self.val(i))
        self.dfs(self.left(i), order)
        if order == "in":
            self.res.append(self.val(i))
        self.dfs(self.right(i), order)
        if order == "post":
            self.res.append(self.val(i))

    def pre_order(self):
        self.res = []
        self.dfs(0, "pre")
        return self.res

    def in_order(self):
        self.res = []
        self.dfs(0, "in")
        return self.res

    def post_order(self):
        self.res = []
        self.dfs(0, "post")
        return self.res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class ArrayBinaryTree{
    private:
        vector<int> tree;

        void dfs(int i, string order, vector<int>& res){
            if (val(i) == INT_MAX){
                return;
            }
            if(order == "pre"){
                res.push_back(val(i));
            }
            dfs(left(i), order, res);
            if(order == "in"){
                res.push_back(val(i));
            }
            dfs(right(i), order, res);
            if(order == "post"){
                res.push_back(val(i));
            }
        }

    public:

        ArrayBinaryTree(vector<int> arr){
            tree = arr;
        }

        int size(){
            return tree.size();
        }

        int val(int i){
            if (i < 0 || i >= size()){
                return INT_MAX;
            } 
            return tree[i];
        }

        int left(int i){
            return 2 * i + 1;
        }

        int right(int i){
            return 2 * i + 2;
        }

        int parent(int){
            return (i - 1) / 2;
        }

        vector<int> levelOrder(){
            vector<int> res;
            for(int i = 0; i < size(); i++){
                if(val(i) != INT_MAX){
                    res.push_back(val(i));
                }
            }
            return res;
        }

        vector<int> preOrder() {
            vector<int> res;
            dfs(0, "pre", res);
            return res;
        }

        vector<int> inOrder() {
            vector<int> res;
            dfs(0, "in", res);
            return res;
        }

        vector<int> postOrder() {
            vector<int> res;
            dfs(0, "post", res);
            return res;
        }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
typedef struct{
    int* tree;
    int size;
}ArrayBinaryTree;

ArrayBinaryTree* newArrayBinaryTree(int* arr, int arrSize){
    ArrayBinaryTree* abt = (ArrayBinaryTree*)malloc(sizeof(ArrayBinaryTree));
    abt->tree = (int*)malloc(sizeof(int) * arrSize);
    memcpy(abt->tree, arr, sizeof(int) * arrSize);
    abt->size = arrSize;
    return abt;
}

void delArrayBinaryTree(ArrayBinaryTree* abt){
    free(abt->tree);
    free(abt);
}

int size(ArrayBinaryTree* abt){
    return abt->size;
}

int val(ArrayBinaryTree* abt, int i){
    if (i < 0 || i >= size(abt)){
        return INT_MAX;
    }
    return abt->tree[i];
}

int left(int i){
    return 2 * i + 1;
}

int right(int i){
    return 2 * i + 2;
}

int* levelOrder(ArrayBinaryTree* abt, int* returnSize){
    int* res = (int*)malloc(sizeof(int) * abt->size);
    int index = 0;
    for(int i = 0; i < size(abt); i++){
        if(val(abt, i) != INT_MAX){
            res[index++] = val(abt, i);
        }
    }
    *returnSize = index;
    return res;
}

void dfs(ArrayBinaryTree* abt, int i, char* order, int* res, int* index){
    if(val(abt, i) == INT_MAX){
        return;
    }
    if(strcmp(order, "pre") == 0){
        res[(*index)++] = val(abt, i);
    }
    dfs(abt, left(i), order, res, index);
    if(strcmp(order, "in") == 0){
        res[(*index)++] = val(abt, i);
    }
    dfs(abt, right(i), order, res, index);
    if(strcmp(order, "post") == 0){
        res[(*index)++] = val(abt, i);
    }
}

int* preOrder(ArrayBinaryTree* abt, int* returnSize){
    int* res = (int*)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "pre", res, &index);
    *returnSize = index;
    realloc(res, sizeof(int) * index);
    return res;
}

int* inOrder(ArrayBinaryTree* abt, int* returnSize){
    int* res = (int*)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "in", res, &index);
    *returnSize = index;
    realloc(res, sizeof(int) * index);
    return res;
}

int* postOrder(ArrayBinaryTree* abt, int* returnSize){
    int* res = (int*)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "post", res, &index);
    *returnSize = index;
    realloc(res, sizeof(int) * index);
    return res;
}

优势与局限性

优点

  • 连续内存空间，缓存友好，遍历和访问速度较快
  • 不需要存储指针以维护结构信息，节省空间
  • 支持随机访问

局限性

  • 需要连续空间，不适合数据量过大的树
  • 增删节点需要进行数组插入与删除操作，效率较低
  • 当二叉树中存在大量None时，空间利用率较低

二叉搜索树

  1. 对于根节点，左子树中所有节点的值根节点的值右子树 中所有节点的值
  2. 任意节点的左、右子树也是二叉搜索树

二叉搜索树

常用操作

  1. 查找节点

利用二叉搜索树的性质来查找，与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的高度，当二叉树平衡时，最多为。

1
2
3
4
5
6
7
8
9
10
def search(self, num):
    cur = self._root
    while cur is not None:
        if cur.val < num:
            cur = cur.right
        elif cur.val > num:
            cur = cur.left
        else:
            break
    return cur
1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* search(int num){
    TreeNode* cur = root;
    while(cur != nullptr){
        if(cur->val < num){
            cur = cur->right;
        }else if(cur->val > num){
            cur = cur->left;
        }else{
            break;
        }
    }
    return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* search(BinarySearchTree* bst, int num){
    TreeNode* cur = bst->root;
    while(cur != NULL){
        if(cur->val < num){
            cur = cur->right;
        }else if(cur->val > num){
            cur = cur->left;
        }else{
            break
        }
    }
    return cur;
}
  1. 插入节点

  • 查找插入位置：与查找操作相似，直到越过叶节点（None节点）时跳出循环

  • 在该位置插入节点

在二叉搜索树中插入节点

  • 二叉搜索树不允许存在重复节点，否则将违反其定义。若待插入节点在树中已存在，则不插入，直接返回

  • 插入节点时，我们需要保存插入位置(None)的父节点，从而实现插入

  • 与查找节点复杂度相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def insert(self, num):
    if self._root is None:
        self._root = TreeNode(num)
        return
    cur, pre = self._root, None
    while cur is not None:
        if cur.val == num:
            return
        pre = cur
        if cur.val < num:
            cur = cur.right
        else:
            cur = cur.left
    node = TreeNode(num)
    if pre.val < num:
        pre.right = node
    else:
        pre.left = node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void insert(int num){
    if(root == nullptr){
        root = new TreeNode(num);
        return;
    }
    TreeNode *cur = root, *pre = nullptr;
    while(cur != nullptr){
        if(cur->val == num){
            return;
        }
        pre = cur;
        if (cur->val < num){
            cur = cur.right;
        }else{
            cur = cur.left;
        }
        TreeNode* node = new TreeNode(num);
        if(pre->val < num){
            pre.right = node;
        }else{
            pre.left = node;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void insert(BinarySearchTree* bst, int num){
    if(bst->root == NULL){
        bst->root = newTreeNode(num);
        return;
    }
    TreeNode *cur = bst->root, *pre = NULL;
    while(cur != NULL){
        if(cur->val == num){
            return;
        }
        pre = cur;
        if(cur->val < num){
            cur = cur->right;
        }else{
            cur = cur->left;
        }
    }
    TreeNode* node = newTreeNode(num);
    if(pre->val  < num){
        pre->right = node;
    }else{
        pre->left = node;
    }
}
  1. 删除节点

先在二叉树中找到目标节点，再将其删除。根据目标节点的子节点数量，分为0、1和2三种情况，执行对应的删除节点操作

  • 当待删除节点的度为0时，表示该节点是叶节点，直接删除
    在二叉搜索树中删除节点（度为0）
  • 当待删除节点的度为1时，将待删除节点替换为其子节点即可
    在二叉搜索树中删除节点（度为1）
  • 当待删除节点的度为2时，无法直接删除，需要选用一个节点替换该节点 ，这个节点可以是右子树的最小节点：中序遍历的下一个节点或左子树的最大节点：中序遍历的上一个节点
  • 找到中序遍历序列中的上一个或者下一个节点，记作tmp，在树中递归删除节点tmp，用tmp的值覆盖待删除节点的值，

删除节点操作使用时间，查找待删除节点需要时间，获取中序遍历后继或前驱节点需要时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def remove(self, num):
    if self._root is None:
        return
    cur, pre = self._root, None
    while cur is not None:
        if cur.val == num:
	        break
	    pre = cur
	    if cur.val < num:
		    cur = cur.right
		else:
			cur = cur.left
	if cur is None:
		return

	if cur.left is None or cur.right is None:
		child = cur.left or cur.right
		if cur != self._root:
			if pre.left == cur:
                pre.left = child
            else:
                pre.right = child
        else:
            self._root = child
    else:
        # 获取中序遍历中cur的下一个节点
        tmp = cur.right
        while tmp.left is not None:
            tmp = tmp.left
        self.remove(tmp.val)
        cur.val = tmp.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void remove(int num){
    if (root == nullptr){
        return;
    }
    TreeNode *cur = root, *pre = nullptr;
    while(cur != nullptr){
        if(cur->val == num){
            break;
        }
        pre = cur;
        if(cur->val < num){
            cur = cur.right;
        }else{
            cur = cur.left;
        }
    }

    if (cur == nullptr){
        return;
    }

    if(cur->left == nullptr || cur->right == nullptr){
        TreeNode* chile = cur->left != nullptr ? cur->left : cur->right;
        if(cur != root){
            if(pre->left == cur){
                pre->left = child;
            }else{
                pre->right = child;
            }
        }else{
            root = child;
        }
        delete cur;
    }else{
        TreeNode* tmp = cur->right;
        while(tmp->left != nullptr){
            tmp = tmp->left;
        }
        int tepVal = tmp->val;
        remove(tmp->val);
        cur->val = tmpVal;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void removeItem(BinarySearchTree* bst, int num){
    if(bst->root == NULL){
        return;
    }
    TreeNode *cur = bst->root, *pre = NULL;
    while(cur != NULL){
        if(cur->val == num){
            break;
        }
        pre = cur;
        if(cur->val < num){
            cur = cur->right;
        }else{
            cur = cur->left;
        }
    }
    
    if(cur == NULL){
        return;
    }

    if(cur->left == NULL || cur->right == NULL){
        TreeNode* child = cur->left != NULL ? cur->left : cur->right;
        if(pre->left == cur){
            pre->left = child;
        }else{
            pre->right = child;
        }
        free(cur);
    }else{
        TreeNode* tmp = cur->right;
        while(tmp->left != NULL){
            tmp = tmp->left;
        }
        int tmpVal = tmp->val;
        removeItem(bst, tmp->val);
        cur->val = tmp->val;
    }
}
  1. 中序遍历有序

二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，因此二叉搜索树的中序遍历序列是升序的

利用上述性质，在二叉搜索树中获取有序数据仅需时间，无须进行额外的排序操作

二叉搜索树的中序遍历序列

效率

二叉搜索树的各项操作的时间复杂度都是对数阶，稳定且高效。只有在高频添加、低频查找删除的数据时，无序数组比二叉搜索树效率高

无序数组 二叉搜索树
查找元素
添加元素
删除元素(先查找)

理想情况下，二叉搜索树是平衡的，这样可以在轮循环内查找任意节点

但是在二叉搜索树中不断插入和删除节点，可能会导致其退化为链表，此时各种操作的时间复杂度退化为

二叉搜索树的退化

常见应用

  • 用作系统中的多级索引，实现高效的查找、插入、删除操作

  • 用作某些搜索算法的底层数据结构

  • 用作存储数据流，以保持其有序状态

AVL树

AVL树既是二叉搜索树也是平衡二叉树，因此也被称为**平衡二叉搜索树(balanced binary search tree)**AVL树在持续添加和删除节点后，不会退化，使得各种操作的时间复杂度保持在级别。

常见术语

  1. 节点高度

AVL树的相关操作需要获取节点高度，因此需要为节点类添加height变量。节点高度是指从该节点到其最远叶节点的距离，即所经过的边的数量。**叶节点的高度为0，空节点的高度为-1。

1
2
3
4
5
6
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.height = 0
        self.left = None
        self.right = None
1
2
3
4
5
6
7
8
9
struct TreeNode{
    int val{}; // C++及以后版本中的一种新的变量初始化语法，称为值初始化，将其初始化为默认值
    // 使用花括号`{}`进行初始化有一些优势，其中之一是避免了某些情况下的隐式类型转换
    int height = 0;
    TreeNode* left;
    TrerNode* right;
    TreeNode() = default; // 默认构造函数，使用'= default'表示使用编译器默认生成的构造函数，将val、height初始化为0，left、right初始化为nullptr
    explicit TreeNode(int x) : val(x){} // 声明一个带参数的构造函数，`explicit`关键字防止隐式转换，确保在使用该构造函数时必须显式调用
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct TreeNode{
    int val;
    int height;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* newTreeNode(int val){
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->height = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

创建两个工具函数，用于获取和更新节点的高度

1
2
3
4
5
6
7
def height(self, node):
    if node is not None:
        return node.height
    return -1

def updata_height(self, node):
    node.height = max([self.height(node.left), self.height(node.right)]) + 1 # 节点高度等于最高子树高度 + 1
1
2
3
4
5
6
7
int height(TreeNode* node){
    return node == nullptr ? -1 : node->height;
}

void updateHeight(TreeNode* node){
    node->height = max(height(node->left), height(node->right)) + 1;
}
1
2
3
4
5
6
7
int height(TreeNode* node){
    return node == NULL ? -1 : node->height;
}

void updateHeight(TreeNode* node){
    node->height = max(height(node->left), height(node->right)) + 1;
}
  1. 节点平衡因子

节点的平衡因子定义为节点左子树的高度减去右子树的高度，空节点的平衡因子为0。一棵AVL树的任意节点的平衡因子皆满足

1
2
3
4
def balance_factor(self, node):
    if node is None:
        return 0
    return self.height(node.left) - self.height(node.right)
1
2
3
4
5
6
int balanceFactor(TreeNode* node){
    if(node == nullptr){
        return 0;
    }
    return height(node->left) - height(node->right);
}
1
2
3
4
5
6
int balanceFactor(TreeNode* node){
    if(node == NULL){
        return 0;
    }
    return height(node->left) - height(node->right);
}

AVL树旋转

树旋转是对二叉树的一种操作，不影响元素的顺序（旋转操作前后，树的中序遍历结果一致），旋转过程中始终是二叉搜索树，但会改变树的结构，将一个节点(子树)上移、一个节点(子树)下移，常被用来将较小的子树下移、较大的子树上移，从而降低树的高度、提升许多树的操作效率。

AVL树的特点在于旋转操作————能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。也就是说旋转操作既能保持二叉搜索树的性质，又能使树重新变为平衡二叉树

平衡因子绝对值的节点称为失衡节点。需要通过旋转进行平衡化。

AVL树是二叉平衡树的一种，虽然不同的二叉平衡树定义有所不同，但区别只在于节点维护的信息不同、旋转调整后节点更新的信息不同。因此下面介绍广义的二叉平衡树平衡性调整的操作以及平衡性被破坏的情况。

  1. 平衡性调整的操作

平衡二叉树进行平衡性调整的操作只包括两大基础操作：左旋和右旋。根据不平衡情况的不同，进行一次或两次基本操作。

对一棵树进行旋转时，这棵树的根节点是被旋转的两棵子树的父节点，称为旋转时的根(root)；在旋转后成为新的父节点的节点被称为旋转时的转轴(pivot)

  • 右旋：顺时针旋转。为保持二叉搜索树的性质，右旋时，旋转前根的左节点的右子树会变成根的左节点，根本身则在旋转后会变成新的根的右节点。

右旋

  • 左旋：逆时针旋转，为保持二叉搜索树的性质，左旋时，旋转前根的右节点的左子树会变成根的右节点，根本身则在旋转后会变成新的根的左节点

左旋

下面这一张动图很好的解释了树旋转的过程

树旋转

下面这一张图则列出了树旋转的各个步骤

树旋转的步骤拆分

  1. 平衡性被破坏的情况以及对应平衡化采取的操作

前提：当平衡性被破坏时，旋转操作都是从失去平衡的最小子树根节点开始的（即离插入或删除节点最近且平衡因子绝对值超过1的节点）

LL型：在n节点的左节点的左子树添加了新节点，使得n的左节点的左子树过长，导致n节点平衡因子变为+2，平衡性被破坏，此时对节点n右旋一次即可平衡。

LL型

RR型：与LL型类似，定义中的左右互换、+2换位-2即可。

LR型：在n节点的左节点的右子树添加了新节点，使得n的左节点的右子树过长，导致n节点平衡因子变为+2，平衡性被破坏，此时先将n的左子树左旋，再将以n为根节点右旋。

LR型

RL型：与RL型类似，定义中的左右互换、+2换为-2即可。

下面这张图很好的概括了四种类型

四种类型

  1. 代码实现

在代码实现中，我们通过失衡节点及其子节点的平衡因子判断四种类型

失衡节点的平衡因子 子节点的平衡因子 应采用的旋转方法
(即左偏树) 左子节点 左旋
(即左偏树) 左子节点 先左旋再右旋
(即右偏树) 右子节点 右旋
(即右偏树) 左子节点 先右旋再左旋 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def right_rotate(self, root):
    pivot = root.left 
    root.left = pivot.right
    pivot.right = root
    # root下降，pivot上升，其余节点高度不变，因此先更新root，再更新pivot
    self.update_height(root)
    self.update_height(pivot)
    return child

def left_rotate(self, root):
    pivot = root.right
    root.right = pivot.left
    pivot.left = root
    self.update_height(root)
    self.update_height(pivot)
    return pivot

def rotate(self, node):
    """执行旋转操作，使该子树重新恢复平衡"""
    balance_factor = self.balance_factor(node)
    if balance_factor > 1:
        if self.balance_factor(node.left) >= 0:
            return self.right_rotate(node)
        else:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)
    elif balance_factor < -1:
        if self.balance_factor(node.right) <= 0:
            return self.left_rotate(node)
        else:
            node.right = self.right_rotate(node.right)
            return left_rotate(node)
    # 平衡树，无需旋转
    return node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
TreeNode* rightRotate(TreeNode* root){
    TreeNode* pivot = root->left
    root->left = pivot->right
    pivot->right = root
    updateHeight(root);
    updateHeight(pivot);
    return pivot;
}

TreeNode* leftRotate(TreeNode* root){
    TreeNode* pivot = root->right;
    root->right = pivot->left;
    pivot->left = root;
    updateHeight(root);
    updateHeight(pivot);
    return pivot;
}

TreeNode* rotate(TreeNode* node){
    int balanceFactor = balanceFactor(node);
    if (balanceFactor > 1){
        if (balanceFactor(node->left) >= 0){
            return rightRotate(node);
        }else{
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }else if (balanceFactor < -1){
        if (balanceFactor(node->right) <= 0){
            return leftRotate(node);
        }else{
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
TreeNode* rightRotate(TreeNode* root){
    TreeNode* pivot = root->left;
    root->left = pivot->right;
    pivot->right = root;
    updateHeight(root);
    updateHeight(pivot);
    return pivot;
}

TreeNode* leftRotate(TreeNode* root){
    TreeNode* pivot = root->right;
    root->right = pivot->left;
    pivot->left = root;
    updateHeight(root);
    updateHeight(pivot);
    return pivot;
}

TreeNode* rotate(TreeNode* node){
    int balanceFactor = balanceFactor(node);
    if (balanceFactor > 1){
        if (balanceFactor(node->left) >= 0){
            return rightRotate(node);
        }else{
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }else if (balanceFactor < -1){
        if (balanceFactor(node->right) <= 0){
            return leftRotate(node);
        }else{
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    return node;
}

AVL树常见操作

  1. 插入节点

与在二叉搜索树上插入节点大体相似。但是在AVL树中插入节点后，从该节点到根节点的路径上可能出现一系列失衡节点，因此从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def insert(self, val):
    self._root = self.insert_helper(self._root, val)

# 在以node为根的子树中添加val，并返回添加后子树的根节点
def insert_helper(self, node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = self.insert_helper(node.left, val)
    elif val > node.val:
        node.right = self.insert_helper(node.right, val)
    else:
        # 重复节点不插入，原样返回
        return node
    self.update_height(node)
    return self.rotate(node)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(int val){
    root = insertHelper(root, val);
}

// 在以node为根的子树中添加val，并返回添加后子树的根节点
TreeNode* insertHelper(TreeNode* node, int val){
    if(node == nullptr){
        return new TreeNode(val);
    }
    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);
    else
        return node;  
    updateHeight(node);
    node = rotate(node);
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(AVLTree *tree, int val) {
    tree->root = insertHelper(tree->root, val);
}

TreeNode *insertHelper(TreeNode *node, int val) {
    if (node == NULL) {
        return newTreeNode(val);
    }
    if (val < node->val) {
        node->left = insertHelper(node->left, val);
    } else if (val > node->val) {
        node->right = insertHelper(node->right, val);
    } else {
        return node;
    }
    updateHeight(node);
    node = rotate(node);
    return node;
}

下面这张动图形象的展示了AVL树插入节点的情况

插入节点动图

  1. 删除节点

在二叉搜索树删除节点方法的基础上，从底至顶执行旋转操作，使所有失衡节点恢复平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def remove(self, val):
    self._root = self.remove_helper(self._root, val)

# 在以node为根的子树中删除val，并返回删除后子树的根节点
def remove_helper(self, node, val):
    if node is None:
        reurn None
    if val < node.val:
        node.left = self.remove_helper(node.left, val)
    elif val > node.val:
        node.right = self.remove_helper(node.right, val)
    else:
        if node.left is None or node.right is None:
            child = node.left or node.right
            if child is None:
                return None
            else:
                node = child
        else:
            temp = node.right
            while temp.left is not None:
                temp = temp.left
            node.right = self.remove_helper(node.right, temp.val)
            node.val = temp.val
    self.update_height(node)
    return self.rotate(node)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void remove(int val){
    root = removeHelper(root, val);
}

// 在以node为根的子树中删除val，并返回删除后子树的根节点
TreeNode* removeHelper(TreeNode* node, int val){
    if (node == nullptr){
        return nullptr;
    }
    if (val < node->val){
        node->left = removeHelper(node->left, val);
    }else if (val > node->val){
        node->right = removeHelper(node->right, val);
    }else{
        if (node->left == nullptr || node->right == nullptr){
            TreeNode *child = node->left != nullptr ? node->left : node->right;
            if(child == nullptr){
                delete node;
                return nullptr;
            }else{
                delete node;
                node = child;
            }
        }else{
            TreeNode* temp = node->right;
            while(temp->left != nullptr){
                temp = temp->left;
            }
            int tempVal = temp.->val;
            node-> right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node);
    node = rotate(node);
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void removeItem(AVLTree *tree, int val) {
    TreeNode *root = removeHelper(tree->root, val);
}

TreeNode *removeHelper(TreeNode *node, int val) {
    TreeNode *child, *grandChild;
    if (node == NULL) {
        return NULL;
    }
    if (val < node->val) {
        node->left = removeHelper(node->left, val);
    } else if (val > node->val) {
        node->right = removeHelper(node->right, val);
    } else {
        if (node->left == NULL || node->right == NULL) {
            child = node->left;
            if (node->right != NULL) {
                child = node->right;
            }
            if (child == NULL) {
                return NULL;
            } else {
                node = child;
            }
        } else {
            TreeNode *temp = node->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node);
    node = rotate(node);
    return node;
}
  1. 查找节点

与二叉搜索树完全相同

典型应用

  • 组织和存储大型数据，适用于高频查找、低频增删

  • 用于构建数据库中的索引系统

参考链接

1. 维基百科：树旋转

2. 维基百科：AVL树

3. 详解AVL树

4. 二叉搜索树&平衡树

  • 标题: 数据结构：树
  • 作者: 敖炜
  • 创建于 : 2023-11-08 17:56:16
  • 更新于 : 2024-04-19 09:30:06
  • 链接: https://ao-wei.github.io/2023/11/08/数据结构：树/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
数据结构：树
  1. 二叉树
    1. 常用术语
    2. 基本操作
    3. 常见二叉树类型
    4. 二叉树的退化
  2. 二叉树遍历
    1. 层序遍历
    2. 前序、中序、后序遍历
  3. 二叉树数组表示
    1. 表示完美二叉树
    2. 表示任意二叉树
    3. 优势与局限性
  4. 二叉搜索树
    1. 常用操作
    2. 效率
    3. 常见应用
  5. AVL树
    1. 常见术语
    2. AVL树旋转
    3. AVL树常见操作
    4. 典型应用
  6. 参考链接