几种常见的树结构

The Redefine Team Lv3
  2025-01-03 15:30:13 2025-01-03 15:30:13 创建   2025-05-18 00:59:17 2025-05-18 00:59:17 更新    1.9k 字  8 分钟  

几种常见的树结构

二叉搜索树(Binary Search Tree)

构建规则

当前节点的左子树一定小于该节点，而右子树一定大于该节点

优势

会带来极高的查找效率，时间复杂度为O(logn)，因为每次查找都是两个节点选一个，可以看作是一种二分查找，而二分查找的时间复杂度就是O(logn)

缺点

但是有些情况下，比如插入的值总是大于或小于前一个值，会导致树的高度过深，二分查找的时间效率就会退化成线性查找的效率；

代码实现

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left, * right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class BST {
private:
    TreeNode* root;
public:
    BST() : root(nullptr) {}

    bool insert(int val) {
        TreeNode* cur = root, * parent = nullptr;
		// 寻找插入位置
        // 根据二叉搜索树特性进行查找
        while (cur) {
            parent = cur;
            if (val < cur->val)
                cur = cur->left;
            else if (val > cur->val)
                cur = cur->right;
            else
                return false; // 重复值，不插入
        }

        TreeNode* newNode = new TreeNode(val);
        if (!parent) {
            // 说明树为空
            root = newNode;
        }
        else if (val < parent->val) {
            parent->left = newNode;
        }
        else {
            parent->right = newNode;
        }
        return true;
    }
	
    // 注意BST的删除逻辑
    bool erase(int val) {
        TreeNode* cur = root, * pre_parent = nullptr;

        while (cur) {
            pre_parent = cur;
            if (val < cur->val) {
                cur = cur->left;
            }
            else if (val > cur->val) {
                cur = cur->right;
            }
            else break;
        }

        if (!cur) return false; // 没找到
        // left == nullptr
        if (cur->left == nullptr) {
            if (pre_parent == nullptr) {
                root = cur->right;
            } else if (pre_parent->left == cur) {
                pre_parent->left = cur->right;
            } else {
                pre_parent->right = cur->right;
            }
        }
        else if (cur->right == nullptr) {
            if (pre_parent == nullptr) {
                root = cur->left;
            } else if (pre_parent->left == cur) {
                pre_parent->left = cur->left;
            } else {
                pre_parent->right = cur->left;
            }
        }
        else {
            TreeNode* leftMax = cur->left, * parent = cur;
            while (leftMax->right) {
                parent = leftMax;
                leftMax = leftMax->right;
            }
            cur->val = leftMax->val;
            if (parent == cur) {
                parent->left = leftMax->left;
            } else {
                parent->right = leftMax->left;
            }
            delete leftMax;

        }
        return true;
    }

    // 中序遍历辅助函数
    // 二叉搜索树的特性决定了中序遍历会按序输出值
    void inorderTraversal(TreeNode* node) {
        if (!node) return;
        inorderTraversal(node->left);
        cout << node->val << " ";
        inorderTraversal(node->right);
    }
	
    // 中序遍历函数
    void printInOrder() {
        inorderTraversal(root);
        cout << endl;
    }

};

二叉搜索树的删除逻辑详解：

删除一个节点，必须要找到对应的替代节点填补删除节点的空白，我们根据二叉搜索树的性质，可以找到这两个节点

  1. 第一个是删除节点的左子树中的最大节点
  2. 第二个是删除节点的右子树中的最小节点

这里以左子树中的最大节点为例（右子树中的最小节点类似），那么我们如何才能找到该节点呢？

考虑二叉搜索树的性质，最大节点必然出现在当前节点的右子树中，而下一个节点的最大节点也一样，这就满足了一个递归关系，也就是说，我们需要在左子树中递归（或迭代）右子树，直到找到叶子节点，该节点就是左子树中的最大节点……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode* leftMax = cur->left,
TreeNode* parent = cur;
// 这里使用递归方法找到最大节点
while (leftMax->right) {
    parent = leftMax;
    leftMax = leftMax->right;
}
// 找到之后开始执行交换操作
cur->val = leftMax->val;
if (parent == cur) {
    parent->left = leftMax->left;
} else {
    parent->right = leftMax->left;
}
// 交换完成后删除对应节点
delete leftMax;

上述讨论的是删除的一般情况，但是根据具体的情况来看，又可以分为三个细分情形：

  1. 左子树为空
  2. 右子树为空
  3. 左右都不为空

这里的第一、二点都是一般情况的特殊化，为了简化代码逻辑，提高执行效率，我们将其细化，执行特殊处理：

我们直接将对应节点删除，然后将该节点后的子树结构直接拼接到原树结构即可，从而免除了迭代查找带来的时间开销。

平衡二叉搜索树（AVL Tree）

针对以上问题，便出现了平衡二叉搜索树的解决方案，该结构的构建规则和二叉搜索树相同，不同的是该结构会维持左右子树的高度差始终小于等于1，从而解决了树的高度过深导致时间效率退化的问题
但是如何保证高度差始终满足要求呢 -> 这就引出了旋转(Rotation) + 平衡因子(Balance Factor)的方法

所谓旋转，可以理解成对树结构的一种局部重构——选取合适的节点作为局部子树新的根节点，然后以此重构树结构（局部上的）

注意，下面介绍的旋转都会包含对应平衡因子的更新策略

单旋

左单旋

左单旋

绿色代表当前节点的平衡因子，h代表树的高度

节点变化

当插入新节点后，根节点的平衡因子变为2，不满足AVL树的要求，需要进行旋转（上图进行的是左单旋），简单来说就是将根节点的右节点（后续称为subR）作为新的根节点，而subR->left（subRL）作为cur节点的右节点，如上图所示。

平衡因子更新

除了上面的节点更新，平衡因子的更新也同样重要，具体的更新策略如图所示，只需计算出旋转过后对应节点的新平衡因子即可。

代码实现
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
#include <cassert>
#include <iostream>

// 定义节点结构体
struct TreeNode {
    int _key;
    TreeNode* _left;
    TreeNode* _right;
    TreeNode* _parent;

    int _balanceFactor;

    TreeNode(int key) : _key(key), _left(nullptr), _right(nullptr), _parent(nullptr), _balanceFactor(0) {}
};

// 左单旋
void leftRotate(TreeNode* parent) {
    // 参照上图, 首先要找到subR节点和subRL节点
    TreeNode* subRight = parent->_right;
    TreeNode* subRightLeft = subRight->_left;
    TreeNode* grandParent = parent->_parent;
	
    parent->_right = subRightLeft;
	
    // 如果subRL存在
    // 则需要将subRL节点的父节点(parent)标记为cur节点
    if (subRightLeft) {
        subRightLeft->_parent = parent;
    }
	
    // 将父节点交换
    // subR节点成为新的父节点
    subRight->_left = parent;
    parent->_parent = subRight;

    // 还要将subR节点和上面的节点相连接
    // 否则局部子树会断开连接
    subRight->_parent = grandParent;
	
    // 判断cur节点是否为根节点
    if (grandParent == nullptr) {
        _root = subRight;
        _root->_parent = nullptr;
    } else {
        // 如果不是
        // 根据cur的之前的位置来选择连接的是左子树还是右子树
        if (grandParent->_key > subRight->_key) {
            grandParent->_left = subRight;
        }
        else {
            grandParent->_right = subRight;
        }
    }
    // 更新平衡因子
    // 因为左右子树没有高度差
    // 平衡因子为0
    parent->_balanceFactor = subRight->_balanceFactor = 0;
}

右单旋

右单旋

节点变化

和左单旋类似，只不过方向不同，具体逻辑参考上图

平衡因子更新

同左单旋，没有高度差，平衡因子为0

代码实现
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
// 右单旋
// 具体逻辑和左单旋类似
// 可参考上图理解
// 不过多赘述
void rightRotate(TreeNode* parent) {
    TreeNode* subLeft = parent->_left;
    TreeNode* subLeftRight = subLeft->_right;
    TreeNode* grandParent = parent->_parent;

    parent->_left = subLeftRight;

    if (subLeftRight) {
        subLeftRight->_parent = parent;
    }
    subLeft->_right = parent;
    parent->_parent = subLeft;

    subLeft->_parent = grandParent;

    if (grandParent == nullptr) {
        _root = subLeft;
        _root->_parent = nullptr;
    }
    else {
        if (grandParent->_key > subLeft->_key) {
            grandParent->_left = subLeft;
        }
        else {
            grandParent->_right = subLeft;
        }
    }
    parent->_balanceFactor = subLeft->_balanceFactor = 0;
}

双旋

有时一些情况一次旋转无法解决问题，我们可以采取多次旋转的方式——即双旋，双旋分为两种——左右双旋和右左双旋

左右双旋

左右双旋

节点变化

右左双旋

红黑树（RBTree）

  • 标题: 几种常见的树结构
  • 作者: The Redefine Team
  • 创建于 : 2025-01-03 15:30:13
  • 更新于 : 2025-05-18 00:59:17
  • 链接: https://redefine.ohevan.com/2025/01/03/Tree/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
几种常见的树结构
  1. 几种常见的树结构
    1. 二叉搜索树(Binary Search Tree)
      1. 构建规则
      2. 优势
      3. 缺点
      4. 代码实现
    2. 平衡二叉搜索树（AVL Tree）
      1. 单旋
      2. 双旋
    3. 红黑树（RBTree）