一只萨摩耶的博客

程序员技术栈

0%

数据结构

发表于 更新于 分类于 Valine：

树

二叉树

每个结点最多 2 棵子树，没有其它限制了。

‌二叉树的性质‌包括：

  • ‌节点数的限制‌：在二叉树的第i层上至多有个节点，深度为k的二叉树至多有个节点。
  • ‌叶子节点和度为2的节点的关系‌：对于任何一棵二叉树，如果其叶子节点数为，度为2的节点数为，则。

前序遍历

根->左->右

1
2
3
4
5
6
7
8
void preorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    visit(root);            // (2)
    preorder(root->left);   // (3)
    preorder(root->right);  // (4)
}

中序遍历

左->根->右

1
2
3
4
5
6
7
8
void inorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    inorder(root->left);    // (2)
    visit(root);            // (3)
    inorder(root->right);   // (4)
}

后序遍历

左->右->根

1
2
3
4
5
6
7
8
void postorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    postorder(root->left);  // (2)
    postorder(root->right); // (3)
    visit(root);            // (4)
}

层序遍历

如果二叉树为空，则直接返回。否则，依次从树的第一层开始，从上至下逐层遍历。在同一层中，按从左到右的顺序对结点逐个访问。层序遍历就是一个广度优先搜索。

在遍历过程中，将每个节点的值按照遍历的顺序存储到一个队列中，然后依次取出队列中的节点进行访问。这样就可以实现对二叉树的层级遍历。

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
vector<vector<int>> levelOrder(BTNode* root)
{
    vector<vector<int>> ans;
    if (root == nullptr)
        return ans;
    queue<BTNode *> Qu;
    Qu.push(root);

    while (!Qu.empty())
    {
        vector<int> ret;
        int count = Qu.size();

        while (count--)
        {
            BTNode *tmp = Qu.front();
            Qu.pop();
            ret.push_back(tmp->val);
            if (tmp->left)
                Qu.push(tmp->left);
            if (tmp->right)
                Qu.push(tmp->right);
        }

        ans.push_back(ret);
    }
    return ans;
}

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树就称为满二叉树

满二叉树的特点有：

  • 叶子只能出现在最下一层。出现在其他层就不可能达到平衡。
  • 非叶子结点的度一定是2。
  • 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

完全二叉树

完全二叉树的特点：

  • 叶子结点只能出现在最下两层。
  • 最下层的叶子一定集中在左部连续位置
  • 倒数二层，若有叶子结点，一定都在右部连续位置。
  • 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
  • 同样结点数的二叉树，完全二叉树的深度最小。
  • ‌完全二叉树的深度‌：具有个节点的完全二叉树的深度为
  • ‌编号规则‌：具有个节点的完全二叉树，按顺序编号，节点的父节点为，左子节点为，右子节点为

注意：满二叉树一定是棵完全二叉树，但完全二叉树不一定是满的。

二叉查找树


也叫二叉搜索树、二叉排序树，首先它是二叉树，并且 左子树上所有结点的值 小于 它根结点的值，右子树上所有结点的值 大于 它根结点的值。若对该树进行中序遍历，可得到一个递增的序列。

插入

对一棵空二叉排序树进行插入，则直接将结点依次插入即可，遵循二叉排序树各结点值的关系，若插入的结点小于根结点的值，则插入到左子树，否则插入到右子树。

深度

对个结点构造二叉排序树，理想情况下，即为一棵满二叉树时的高度，类比于完全二叉树，此时拥有最小深度，即树的高度为或
而若二叉排序树只是一个单支树（左或右单支树），此时最坏情况，即树的高度为元素的个数，则其最大深度为。

查找长度

对n个结点的二叉排序树中，查找某个元素:

  1. 最坏情况下是当构造的二叉树为单支树时，为n层，此时查找树中最后一个元素或不存在的元素时，需要进行n次比较。
  2. 在等概率的情况下，二叉排序树查找成功的平均查找长度ASL=每层层数乘以每层结点个数之和 / 二叉排序树的结点总个数。

元素总数为10，其中第一层元素个数为1，第二层为2，第三层为4，第四层为3，所以可得查找成功的平均查找长度：

删除

  1. 删除叶子结点
    若删除的结点是二叉排序树的叶子结点，则可以直接删除，删除后并不影响二叉排序树的性质。
  2. 删除结点存在左孩子或右孩子
    若删除的结点存在左孩子或右孩子时，则让该结点的子树成为其父结点的子结点。
  3. 删除结点存在左孩子和右孩子
    若删除结点存在左孩子和右孩子，则令该结点的前驱/后继代替其本身（用中序遍历序列中该结点的前驱/后继代替），调整后的树仍是二叉排序树。

如下删除66节点，可用70或58其中任意一个代替：

AVL和RB树

平衡二叉树(AVL)

首先它是 “二叉搜索树”，其次，它是平衡的，即是它的每一个结点的左子树的高度和右子树的高度差至多为 1。​将二叉查找树平衡均匀地分布，这样的好处就是可以减少二叉查找树的深度。
查找效率：

失衡调整

当不满足平衡条件的话，那就只能去通过旋转来实现平衡。下面有4种不满足平衡条件的情况，如图所示：

  • 树2是在左子树右子节点出现失衡情况，属于 LR型
  • 树3是在右子树右子节点出现失衡情况，属于 RR型
  • 树4是在左子树左子节点出现失衡情况，属于 LL型
  • 树5是在右子树左子节点出现失衡情况，属于 RL型
LL型失衡

右旋，口诀：左失衡，中为支，高右旋

右旋就是通过顺时针旋转来实现平衡，就是处于右边的根结点落下变为叶子节点，而中间的节点变为新的根节点，最左边的叶子节点保持不变，最后形成新的结构。

在结点A的左孩子结点B的左子树插入导致不平衡，A结点的左孩子B结点右旋代替A成为当前最小不平衡二叉树的根节点，A结点的左孩子指向B结点的右孩子，并把B结点的右孩子指向A结点。

代码如下：

1
2
3
4
5
6
7
8
Node* R_Rotate(Node* head){
        Node* new_head=head->lchild;
        head->lchild=new_head->rchild;
        new_head->rchild=head;
        head->height=1+std::max(GetHeight(head->lchild),GetHeight(head->rchild));
        new_head->height=1+std::max(GetHeight(new_head->lchild),GetHeight(new_head->rchild));
        return new_head;
    }
RR型失衡

左旋，口诀：右失衡，中为支，高左旋
对于RR型失衡，通过逆时针旋转，最左边的根结点落下，变成叶子节点，中间的节点变为新的根节点，最右边的叶子节点保持不变。

在结点A的右孩子结点B的右子树插入导致不平衡，A结点的右孩子B结点左旋代替A成为当前最小不平衡二叉树的根节点，A结点的右孩子指向B结点的左孩子，并把B结点的左孩子指向A结点。

代码如下：

1
2
3
4
5
6
7
8
Node* L_Rotate(Node* head){
        Node* new_head=head->rchild;
        head->rchild=new_head->lchild;
        new_head->lchild=head;
        head->height=1+std::max(GetHeight(head->lchild),GetHeight(head->rchild));
        new_head->height=1+std::max(GetHeight(new_head->lchild),GetHeight(new_head->rchild));
        return new_head;
    }
LR型失衡

先左旋再右旋，口诀：下二整体左旋，后与LL型调整一样

对于LR型失衡，先在根节点左子树进行左旋处理，变成LL型失衡，然后再去通过右旋来实现整体平衡

1. 左旋：

2. 右旋：

1
2
3
4
5
Node* LR_Rotate(Node* head){
        Node* new_lhead=L_Rotate(head->lchild);
        head->lchild=new_lhead;
        return R_Rotate(head);
    }
RL型失衡

先右旋再左旋，口诀：下二整体右旋，后与RR型调整一样

对于RL型失衡，在根节点的右子树先进行右旋处理，形成RR型失衡，然后整体进行左旋处理，最后达到平衡状态

1. 右旋：

2. 左旋：

1
2
3
4
5
Node* RL_Rotate(Node* head){
        Node* new_rhead=R_Rotate(head->rchild);
        head->rchild=new_rhead;
        return L_Rotate(head);
    }

插入操作

这里的代码通过递归实现，变量bal表示平衡二叉树的平衡因子，一旦完成了插入会从下往上进行return，这样在第一次bal不满足条件时，就是最小不平衡二叉树。

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
void insert(T val){
     root= _insert(root,val);
}

Node* _insert(Node* head,T val){
        if(head==NULL){
            head=new Node(val);
            return head;
        }
        if(val>head->val){
            head->rchild=_insert(head->rchild,val);
        }else if(val<head->val){
            head->lchild=_insert(head->lchild,val);
        }else{
            throw std::invalid_argument("Cannot insert elements with the same value!");
            return nullptr;
        }
        head->height=1+std::max(GetHeight(head->lchild),GetHeight(head->rchild));
        int bal = GetHeight(head->lchild) -GetHeight(head->rchild);
        if(bal>1){
            if(val<head->lchild->val){
                return LL_Rotate(head);
            }else if(val>head->lchild->val){
                return LR_Rotate(head);
            }
        }
        if(bal<-1){
            if(val>head->rchild->val){
                return RR_Rotate(head);
            }else if(val<head->rchild->val){
                return RL_Rotate(head);
            }
        }
        return head; 
}

删除操作

  1. 蓝色情况：比较简单，直接将其置空，释放，然后返回给父节点即可。
  2. 橙色情况：删除节点有左子树没有右子树。 先保存该结点左子树的地址，delete该结点，然后把地址等于左子树地址， 相当于将原来结点地址覆盖
  3. 黄色情况：删除节点有右子树没有左子树 。与2处理相同，只是将左子树换为右子树。
  4. 绿色情况：既有左子树又有右子树：找到右子树中的最小值，将值赋给当前结点，然后以该最小值为目标继续往右子树寻找并删除结点。

以上操作完成之后需要判断整体的失衡情况，进行相对的旋转操作。

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
void erase(T val)
{
    root = _erase(root, val);
}
Node *_erase(Node *head, T val)
{
    if (head == nullptr)
    {
        return nullptr;
    }
    if (val < head->val)
    {
        head->lchild = _erase(head->lchild, val);
    }
    else if (val > head->val)
    {
        head->rchild = _erase(head->rchild, val);
    }
    else
    {
        if (!head->lchild && !head->rchild)
        { // 无左子树无右子树
            delete (head);
            head = nullptr;
        }
        else if (head->lchild && !head->rchild)
        { // 有左子树无右子树
            Node *lc = head->lchild;
            delete (head);
            head = lc;
        }
        else if (!head->lchild && head->rchild)
        { // 无左子树有右子树
            Node *rc = head->rchild;
            delete (head);
            head = rc;
        }
        else
        { // 都有
            Node *cur = head->rchild;
            while (cur->lchild)
            {
                cur = cur->lchild;
            }
            head->val = cur->val;
            head->rchild = _erase(head->rchild, cur->val);
        }
    }
    if (head == nullptr)
        return head;
    int bal = GetHeight(head->lchild) - GetHeight(head->rchild);
    head->height = 1 + std::max(GetHeight(head->lchild), GetHeight(head->rchild));
    if (bal > 1)
    {
        if (GetHeight(head->lchild->lchild) >= GetHeight(head->lchild->rchild))
        {
            return RR_Rotate(head);
        }
        else
        {
            return LR_Rotate(head);
        }
    }
    else if (bal < -1)
    {
        if (GetHeight(head->lchild->lchild) >= GetHeight(head->lchild->rchild))
        {
            return RL_Rotate(head);
        }
        else
        {
            return RR_Rotate(head);
        }
    }
    return head;
}

判断操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//判断一个树是否为平衡二叉树
bool Judge(Node* T) {
	if (!T){
		printf("NULL\n");
		exit(0);
	}
	if(T->left->data>T->data||T->right->data<T->data)
		return false;
	if (abs(GetHeight(T->left) - GetHeight(T->right)) > 1)
		return false;
	else
		return true;
	return Judge(T->left)&&Judge(T->right);
}

红黑树(RB)

假设全部黑节点有N个

  • 整棵树的节点数量：之间
  • 最短路径长度：
  • 最长路径长度：
  • 查找效率：

红黑树有以下规则：
口决：左根右，根叶红，不红红，黑路同

  • 规则1：一个节点不是红色就是黑色。
  • 规则2：红黑树的根节点(root)必须是黑色。
  • 规则3：如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。(黑色结点的孩子可能是红也可能是黑，红色结点的孩子只能是黑)
  • 规则4：对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。

红黑树的路径

《算法导论》等书籍上补充了⼀条每个叶子结点(NIL)都是黑色的规则。它这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。
NIL都是黑色既不违反规则3，也不违反规则4。
NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道一下这个概念即可。

红黑树的特性

红黑树如何确保最长路径不超过最短路径的2倍？

  • 由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就是全是黑色结点的路径，假设最短路径长度为bh。
  • 由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为2*bh。

综合红黑树的4点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x，那么bh<=x<=2*bh。

插入操作

红黑树插入一个值的大致过程：

  1. 首先按⼆叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的4条规则。
  2. 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须是红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4是难维护的。
  3. 非空树插入后，新增结点必须是红色结点，如果此时父亲结点是黑色的，则没有违反任何规则，插入结束。
  4. 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。这种情况是可以维护的，具体维护过程如下分析：
插入结点的叔叔是红色

叔父爷变色（红变黑，黑变红），爷爷变插入节点（将爷爷视为插入结点，继续判定是否破坏红黑树的性质）

插入结点的叔叔是黑色

根据（LL、RR、LR、RL）以爷爷作为旋转点进行旋转，然后对旋转点和旋转中心变色

LL 型

RR型

LR型

RL型

点击跳转B站视频，学习更多相关红黑树知识

代码相关

插入
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
bool Insert(const pair<K, V> &kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;

        return true;
    }

    Node *parent = nullptr;
    Node *cur = _root;
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }

    cur = new Node(kv);
    cur->_col = RED; // 插入的新结点必须是红色
    if (parent->_kv.first < kv.first)
        parent->_right = cur;
    else
        parent->_left = cur;

    // 链接父亲
    cur->_parent = parent;

    // 父亲是红色，那么就会出现连续的红色节点，需要处理
    while (parent && parent->_col == RED)
    {
        Node *grandfather = parent->_parent;

        if (parent == grandfather->_left) // 叔叔(u)在右边
        {
            //   g
            // p   u
            Node *uncle = grandfather->_right;
            // 第一种情况：叔叔存在且为红
            if (uncle && uncle->_col == RED)
            {
                // 变色
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;

                // 继续往上处理
                cur = grandfather;
                parent = cur->_parent;
            }
            // 第二、三种情况：叔叔不存在或者叔叔存在且为黑
            else
            {
                if (cur == parent->_left) // 右单旋
                {
                    //     g
                    //   p    (u)
                    // c
                    RotateR(grandfather);
                    parent->_col = BLACK; // 更新颜色
                    grandfather->_col = RED;
                }
                else // 双旋
                {
                    //     g
                    //   p   (u)
                    //     c
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK; // 更新颜色
                    grandfather->_col = RED;
                }

                break; // 旋转完直接结束，不需要向上再进行判断了
            }
        }
        else // 叔叔(u)在左边，主要逻辑和上面一样，只不过方向变了
        {
            //   g
            // u   p
            Node *uncle = grandfather->_left;
            // 叔叔存在且为红 -> 变色即可
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;

                // 继续往上处理
                cur = grandfather;
                parent = cur->_parent;
            }
            else // 叔叔(u)不存在或者存在且为黑
            {
                // 情况二、三：叔叔不存在或者存在且为黑 -> 旋转+变色
                //	   g
                // (u)   p
                //         c
                if (cur == parent->_right) // 单旋
                {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else // 双旋
                {
                    //     g
                    // (u)   p
                    //     c
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break; // 旋转完直接结束，不需要向上更新
            }
        }
    }
    _root->_col = BLACK; // 特殊处理，插入结束后不管三七二十一直接让根结点为黑(主要是针对情况1)
    return true;
}

旋转
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
// 右单旋
void RotateR(Node *parent)
{
    Node *subL = parent->_left;
    Node *subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;

    Node *pParent = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (parent == _root)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (pParent->_left == parent)
            pParent->_left = subL;
        else
            pParent->_right = subL;

        subL->_parent = pParent;
    }
}
// 左单旋
void RotateL(Node *parent)
{
    Node *subR = parent->_right;
    Node *subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;

    Node *parentParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (parentParent == nullptr)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (parent == parentParent->_left)
            parentParent->_left = subR;
        else
            parentParent->_right = subR;
        subR->_parent = parentParent;
    }
}
高度
1
2
3
4
5
6
7
8
int _Height(Node* root)
{
	if (root == nullptr)
		return 0;
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
结点数量
1
2
3
4
5
6
7
int _Size(Node* root)
{
	if (root == nullptr)
		return 0;
 
	return _Size(root->_left) + _Size(root->_right) + 1;
}
判断平衡

这里获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。
所以我们还是去检查4点规则，满足这4点规则，一定能保证最长路径不超过最短路径的2倍。

  1. 对于规则1，因为每个结点都有颜色，天然实现保证了颜色不是黑色就是红色。
  2. 对于规则2，直接检查根即可。
  3. 对于规则3，前序遍历检查，遇到红色结点查孩子结点的颜色，因为孩子有两个，且不一定存在，所以查起来不太方便，但遇到红色结点，反过来检查父亲的颜色就方便多了。
  4. 对于规则4，前序遍历，遍历过程中用形参记录根到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了⼀条路径的黑色结点数量。再以任意一条路径黑色结点数量作为参考值(refNum)，依次比较即可。
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
bool IsBalance()
{
    if (_root == nullptr)
        return true;

    if (_root->_col == RED)
        return false;

    // 参考值
    int refNum = 0;
    Node *cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
        {
            ++refNum;
        }
        cur = cur->_left;
    }

    return Check(_root, 0, refNum);
}

bool Check(Node *root, int blackNum, const int refNum)
{
    if (root == nullptr)
    {
        // 前序遍历走到空时，意味着一条路径走完了
        // cout << blackNum << endl;
        if (refNum != blackNum)
        {
            cout << "存在黑色结点的数量不相等的路径" << endl;
            return false;
        }
        return true;
    }

    // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << root->_kv.first << "存在连续的红色结点" << endl;
        return false;
    }

    if (root->_col == BLACK)
    {
        blackNum++;
    }

    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
查找结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//查找结点
Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)
			cur = cur->_right;
		else if (cur->_kv.first > key)
			cur = cur->_left;
		else
			return cur;
	}
	return nullptr;
}

红黑树和AVL树的区别

  1. 平衡性的追求：
    红黑树：追求的是大致平衡，允许左右子树的高度差大于1，但要求从根到叶子的最长路径不超过最短路径的两倍。
    平衡二叉树（AVL树）：追求的是绝对平衡，要求任意节点的左右子树的高度差的绝对值不超过1。

  2. 实现复杂度：
    红黑树：由于追求的是大致平衡，因此其实现相对简单，每次插入最多只需要三次旋转就能达到平衡。
    平衡二叉树（AVL树）：由于追求绝对平衡，条件比较苛刻，实现起来更为复杂，每次插入新节点后需要旋转的次数不能预知。

  3. 查找、插入和删除操作的效率：
    两者在查找、插入和删除操作上的时间复杂度都是O(log n)，其中n是树中元素的数目。但由于红黑树的实现更简单，因此在实际应用中可能具有更高的效率。

  4. 节点颜色：
    红黑树：每个节点都带有颜色属性，可以是红色或黑色。颜色信息在维护树的平衡性时起到关键作用。
    平衡二叉树（AVL树）：节点没有颜色属性，仅通过调整节点的位置（旋转）来维持平衡。

  5. 应用场景：
    红黑树：由于其高效的插入、删除和查找操作以及相对简单的实现，被广泛应用于各种数据结构和算法中，如C++ STL中的set和map容器。
    平衡二叉树（AVL树）：由于其追求绝对平衡的特性，使得它在某些需要严格保证数据平衡性的场景中更为适用。

B B- B+ B*树

B树

即二叉查找树点击此处跳转到：二叉查找树

B- 树

  1. 所有叶子节点都在同一层级；
  2. 除根结点以外的非叶子结点的儿子数为；
  3. 除了根节点和叶子节点外，每个结点存放至少（取上整）和至多个关键字；（至少2个关键字）
  4. 根节点必须包含至少2个孩子节点；
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1；

  6. 一个节点的所有key值必须是升序排序的；

    如：（M=3）

B+ 树

B+树是B树的变体，也是一种多路搜索树，其定义基本与B-树相同，除了：

  1. 非叶子结点的子树指针与关键字个数相同；
  2. 非叶子结点的子树指针，指向关键字值属于的子树（B-树是开区间）；
  3. 为所有叶子结点增加一个链指针；
  4. 所有关键字都在叶子结点出现；

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

  • 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
  • 不可能在非叶子结点命中；
  • 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

非关系型数据库索引如mongoDB用的B树，大部分关系型数据库索引使用的是B+树。

B+树的分裂：

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点

B* 树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针

B 树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）；

B* 树的分裂：

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

总结

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

跳表

redis的Zset类型使用了跳表数据结构，更多内容可查看Redis—数据结构—跳表—Zset类型

跳表是在链表基础上改进过来的，实现了一种多层的有序链表，这样的好处是能快读定位数据。当数据量很大时，跳表的查找复杂度就是 O(logN)。

查询

跳表查找任意数据的时间复杂度为O(logn)

  1. 从顶层链表的首元素开始，从左往右搜索，直至找到一个大于或等于目标的元素，或者到达当前层链表的尾部
  2. 如果该元素等于目标元素，则表明该元素已被找到
  3. 如果该元素大于目标元素或已到达链表的尾部，则退回到当前层的前一个元素，然后转入下一层进行搜索

插入

跳表插入的时间复杂度为：O(logn)，支持高效的动态插入，插入过程主要涉及三个关键步骤：

  1. 确定节点层级
    首先，我们需要为新插入的节点随机确定其所在的层级
    同时将这个数据插入到部分索引层中，如何选择索引层，可以通过一个随机函数来决定这个节点插入到哪几级索引中，比如随机生成了k，那么就将这个索引加入到，第一级到第k级索引中。

  2. 寻找插入位置
    通过之前讨论的搜索方法，我们能够定位到了新节点应当插入的具体位置

  3. 更新指针关系
    将新节点在各层的前驱节点（即在该层中小于新节点且最接近新节点的节点）的指针指向新节点。同时，新节点的指针需要指向其在各层的前驱节点原本指向的节点。
    此操作和单链表的插入操作类似，区别在于跳表需要在多层中的重复进行此操作，而链表只需要进行一次。

删除

跳表的删除操作时间复杂度为：O(logn)，支持动态的删除。

  • 在跳表中删除某个结点时，如果这个结点在索引中也出现了，我们除了要删除原始链表中的结点，还要删除索引中的。
  • 在查找要删除的结点的时候，需要拿到删除结点的前驱结点，然后再通过指针操作完成删除（双向链表除外）。

跳表层数

跳表的相邻两层的节点数量的比例会影响跳表的查询性能。跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)

那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢？

  • 如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。Redis跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。
  • 具体的做法是，跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。
  • 这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高限制 7.0 定义为 32，R 5.0 定义为 64， 3.0 定义为 32。

那么为什么是小于0.25呢？直接上干货：

  • 首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
  • 如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
  • 节点最大的层数不允许超过一个最大值，记为MaxLevel（即层高限制）。

产生越高的节点层数，概率越低,无论如何层数总是满足幂次定律（power law，越大的数出现的概率越小）。定量的分析如下：

• 节点层数至少为1。而大于1的节点层数，满足一个概率分布。
• 节点层数恰好等于1的概率为1-p。
• 节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
……..

因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：

当p=1/2时，每个节点所包含的平均指针数目为2；当p=1/4时，每个节点所包含的平均指针数目为1.33，你，听懂了吗？

Redis跳表—Zset

源码

1
2
3
4
5
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; //头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
    unsigned long length;                //长度，便于在O(1)时间复杂度获取跳表节点的数量；
    int level;                           //最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量；
} zskiplist;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

跳表结构

  • 每个跳表节点都有一个后向指针（*backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。
  • 跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，

查询过程

  • 从头节点的最高层开始，在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断
  • 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
  • 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。
  • 如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的：

  1. 先从头节点的最高层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；
  2. 但是该层的下一个节点是空节点（ leve[2]指向的是空节点），于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[1];
  3. 「元素：abc，权重：3」节点的 leve[1] 的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据「大于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]；
  4. 「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束

哈希表

哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。

哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。

哈希表目的与特性：
数组的最大特点：寻址容易，插入和删除困难；链表的特点正好相反：寻址困难，而插入和删除操作容易。哈希表结合两者的优点，是一个集查找、插入和删除操作于一身的数据结构。

哈希函数

哈希函数（Hash Function）：将哈希表中元素的关键键值映射为元素存储位置的函数。哈希函数是哈希表中最重要的部分。

一般来说，哈希函数会满足以下几个条件：

  • 哈希函数应该易于计算，并且尽量使计算出来的索引值均匀分布。
  • 哈希函数计算得到的哈希值是一个固定长度的输出值。

如果Hash(key1)不等于Hash(key2)，那么 key1、key2 一定不相等。
如果Hash(key1)等于Hash(key2)，那么 key1、key2 可能相等，也可能不相等（会发生哈希碰撞）。

一般我们会将各种类型的关键字先转换为整数类型，再通过哈希函数，将其映射到哈希表中。而关于整数类型的关键字，通常用到的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。

直接定址法

取关键字本身 / 关键字的某个线性函数值 作为哈希地址。

即： 或者 ，其中 和 为常数。

这种方法计算最简单，且不会产生冲突。适合于关键字分布基本连续的情况，如果关键字分布不连续，空位较多，则会造成存储空间的浪费。

  • 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突；
  • 缺点：要占用连续地址空间，空间效率低。

除留余数法

假设哈希表的表长为 ，取一个不大于 但接近或等于 的质数 p，利用取模运算，将关键字转换为哈希地址。即：，其中 为不大于 的质数。

这也是一种简单且常用的哈希函数方法。其关键点在于 的选择。根据经验而言，一般 取素数或者 ，这样可以尽可能的减少冲突。

  • 特点：以关键码除以p的余数作为哈希地址。
  • 技巧：若设计的哈希表长为m，则一般取且为质数 （也可以是不包含小于20质因子的合数）。

平方取中法

先通过求关键字平方值的方式扩大相近数之间的差别，然后根据表长度，取关键字平方值的中间几位数为哈希地址。
理由：因为中间几位与数据的每一位都相关。

例：2589的平方值为6702921，可以取中间的029为地址。

这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关，所以产生的哈希地址也比较均匀，有利于减少冲突的发生。

哈希冲突

哈希冲突（Hash Collision）：不同的关键字通过同一个哈希函数可能得到同一哈希地址，即 ，而 ，这种现象称为哈希冲突。

理想状态下，我们的哈希函数是完美的一对一映射，即一个关键字（key）对应一个值（value），不需要处理冲突。但是一般情况下，不同的关键字 key 可能对应了同一个值 value，这就发生了哈希冲突。

设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题

开放地址法

指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。

例如，在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录（哈希函数为 ）。现在将插入关键字为 38 的新纪录。根据哈希函数得到的哈希地址为 5，产生冲突。

线性探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。

得到下一个地址 ，仍然冲突；继续求出 ，仍然冲突；继续求出 ，8 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 8 的位置。　

再平方探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

得到下一个地址 ，仍然冲突；继续求出 ，4 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 4 的位置。

伪随机探测

按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。

假设伪随机数为 9，则得到下一个地址 ，3 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 3 的位置。

链式地址法

HashMap的哈希冲突解决方法
对于相同的值，使用链表进行连接。使用数组存储每一个链表。
优点：

  • 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
  • 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
  • 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
  • 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点：

  • 指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。

建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据。

再哈希法

对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

—————请稍等———————

------赞助耶耶，加快更新！------

给耶耶买杯咖啡喝