首页 > 其他分享 >二叉搜索树、AVL（平衡二叉查找树）、红黑树

二叉搜索树、AVL（平衡二叉查找树）、红黑树

时间：2024-11-08 22:16:34浏览次数：3  
标签：Node right cur parent 二叉 AVL 红黑树 root left

一、二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

image-20241104194527561

1.二叉搜索树的操作

image-20241104194734625

1.二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

2.二叉搜索树的插入

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

image-20241104195016074

3.二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情

况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点（找左子树的最大值或者右子树的最小值）

image-20241104195306180

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程

如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点

中，再来处理该结点的删除问题--替换法删除

2.二叉搜索树的代码实现

key
#include<string>
​
namespace key
{
    template<class K>
    struct BSTreeNode
    {
        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;
​
        BSTreeNode(const K& key)
            :_left(nullptr)
            , _right(nullptr)
            , _key(key)
        {
​
        }
    };
​
    template<class K>
    class BSTree
    {
        typedef BSTreeNode<K> Node;
    public:
        bool Insert(const K& key)
        {
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
​
            Node* parent = nullptr;
            Node* cur = _root;
​
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }
​
            cur = new Node(key);
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }
            return true;
        }
        void InOrder()
        {
            _InOrder(_root);
        }
        bool Find(const K& key)
        {
            Node* cur = _root;
​
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
​
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
​
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //左为空
                    //父亲指向我的右
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    //右为空
                    //父亲指向我的左
                    else if (cur->_right == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    //左右都不为空，替换法删除
                    //
                    //查找右子树的最左节点
                    //或者是左子树的最大右点
                    else
                    {
                        Node* rightMinParent = cur;
                        Node* rightMin = cur->_right;
                        while (rightMin->_left)
                        {
                            rightMinParent = cur;
                            rightMin = rightMin->_left;
                        }
                        swap(cur->_key, rightMin->_key);
​
                        if (rightMinParent->_left == rightMin)
                        {
                            rightMinParent->_left = rightMin->_right;
                        }
                        else
                        {
                            rightMinParent->_right = rightMin->_right;
                        }
                        delete rightMin;
                    }
                    return true;
                }
            }
​
        }
​
​
    private:
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
​
    void TestBSTree1()
    {
        int a[] = { 8,3,1,10,6,4,7,14,13 };
        BSTree<int>t1;
        for (auto e : a)
        {
            t1.Insert(e);
        }
​
        t1.InOrder();
        cout << endl;
​
        t1.Erase(8);
        t1.InOrder();
        cout << endl;
​
        for (auto e : a)
        {
            t1.Erase(e);
            t1.InOrder();
            cout << endl;
        }
    }
}
key and value
namespace key_val
{
    template<class K,class V>
    struct BSTreeNode
    {
        BSTreeNode<K,V>* _left;
        BSTreeNode<K,V>* _right;
        K _key;
        V _value;
​
        BSTreeNode(const K& key,const V&value)
            :_left(nullptr)
            , _right(nullptr)
            , _key(key)
            ,_value(value)
        {
​
        }
    };
​
    template<class K,class V>
    class BSTree
    {
        typedef BSTreeNode<K,V> Node;
    public:
        bool Insert(const K& key, const V& value)
        {
            if (_root == nullptr)
            {
                _root = new Node(key,value);
                return true;
            }
​
            Node* parent = nullptr;
            Node* cur = _root;
​
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }
​
            cur = new Node(key,value);
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }
            return true;
        }
        void InOrder()
        {
            _InOrder(_root);
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
​
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }
            return cur;
        }
​
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
​
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //左为空
                    //父亲指向我的右
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    //右为空
                    //父亲指向我的左
                    else if (cur->_right == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    //左右都不为空，替换法删除
                    //
                    //查找右子树的最左节点1
                    //或者是左子树的最右节点
                    else
                    {
                        Node* rightMinParent = cur;
                        Node* rightMin = cur->_right;
                        while (rightMin->_left)
                        {
                            rightMinParent = cur;
                            rightMin = rightMin->_left;
                        }
                        swap(cur->_key, rightMin->_key);
​
                        if (rightMinParent->_left == rightMin)
                        {
                            rightMinParent->_left = rightMin->_right;
                        }
                        else
                        {
                            rightMinParent->_right = rightMin->_right;
                        }
                        delete rightMin;
                    }
                    return true;
                }
            }
​
        }
    private:
        //中序遍历
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _InOrder(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
​
    void TestBSTree2()
    {
        BSTree<string, string>dict;
        dict.Insert("string", "字符串");
        dict.Insert("left", "左边");
        dict.Insert("right", "右边");
        dict.Insert("int", "整型");
​
        string str;
        while (cin >> str)
        {
            BSTreeNode<string, string>* ret = dict.Find(str);
            if (ret)
            {
                cout << ret->_value << endl;
            }
            else
            {
                cout << "查无此单词" << endl;
            }
        }
    }
    void TestBSTree3()
    {
        string arr[] = { "苹果","草莓", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
        "苹果", "香蕉", "苹果", "香蕉","草莓" };
​
        BSTree<string, int> countTree;
        for (const auto& str : arr)
        {
            auto ret = countTree.Find(str);
            if (ret == nullptr)
            {
                countTree.Insert(str, 1);
            }
            else
            {
                ret->_value++;
            }
        }
        countTree.InOrder();
    }
}
​
​
//查找
//二分查找
//二叉搜索树查找 - AVL树和红黑树
//哈希查找
//跳表查找
//多叉搜索数查找 - B树系列

3.二叉搜索树的应用

1.K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树，

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2.KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。

该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，

通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出

现次数就是<word, count>就构成一种键值对。

4.二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，

则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log2N

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\franc{N}{2}$

image-20241104204008121

问题：如果退化成单支树，二叉搜索树的性能就失去了。

二、AVL树

1.概念

二叉搜索树虽可以缩短查找的效率，

但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树

2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

image-20241104225032768

如果一棵二叉搜索树是高度平衡的，它就是AVL树。

如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)。

2.AVL树的定义



3.AVL的实现


删除 1.按搜索树的规则删除


2.删除后更新平衡因子


3.不平衡 -> 旋转


template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    pair<K, V>_kv;
    int _bf;//balance factor
​
    AVLTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _kv(kv)
        ,_parent(nullptr)
        ,_bf(0)
    {
​
    }
};


平衡因子==0 要继续更新


1/-1不用更新 2/-2 旋转


1.按照搜索树规则插入 2.更新插入节点的祖先节点的平衡因子 a.插入父亲的左边，父亲的平衡因子-- b.插入父亲的右边，父亲的平衡因子++


c.父亲的平衡因子==0，父亲所在的子树高度不变，不再继续向上更新。插入结束。 d.父亲的平衡因子==-1/1，父亲所在的子树高度改变，继续向上更新 e.父亲的平衡因子==-2/2，父亲所在的子树已经不平衡了，需要旋转处理


template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            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);
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
​
        //更新平衡因子
        while (parent)
        {
            if (cur == parent->_left)
            {
                parent->_bf--;
            }
            else
            {
                parent->_bf++;
            }
​
            // 是否继续更新依据：子树的高度是否变化
            // 1、parent->_bf == 0说明之前parent->_bf是 1 或者 -1
            // 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新
            // 2、parent->_bf == 1 或 -1 说明之前是parent->_bf == 0，两边一样高，现在插入一边更高了，
            // parent所在子树高度变了，继续往上更新
            // 3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则
            // 就地处理--旋转
​
            // 旋转：
            // 1、让这颗子树左右高度不超过1
            // 2、旋转过程中继续保持他是搜索树
            // 3、更新调整孩子节点的平衡因子
            // 4、让这颗子树的高度跟插入前保持一致
​
            if (parent->_bf == 0)
            {
                //更新结束
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                //继续向上更新
                cur = cur->_parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                //当前子树出问题了，需要旋转更新平衡一下
                //右单旋
                if (parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                //左单旋
                else if (parent->_bf == 2 && cur->_bf == 1)
                {
                    RotateL(parent);
                }
                //双旋
                //右左单旋
                else if (parent->_bf == 2 && cur->_bf == -1)
                {
                    RotateRL(parent);
                }
                //左右单旋
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                break;
            }
            else
            {
                //理论而言 不可能出现这种情况
                assert(false);
            }
        }
        return true;
    }
​
    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
​
        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
​
        Node* ppnode = parent->_parent;
​
        parent->_parent = subL;
​
        if (_root == parent)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subL;
            }
            else
            {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
        parent->_bf = subL->_bf = 0;
    }
​
    //左单旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
​
        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
​
        subR->_left = parent;
​
        Node* ppnode = parent->_parent;
​
        parent->_parent = subR;
​
        if (_root == parent)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subR;
            }
            else
            {
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
        subR->_bf = parent->_bf = 0;
    }
​
    //右左单旋
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
​
        int bf = subRL->_bf;
​
        RotateR(parent->_right);
        RotateL(parent);
​
        if (bf == -1)
        {
            subRL->_bf = 0;
            subR->_bf = 1;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == 0)
        {
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }
​
    //双旋的结果
    //60的左边给了30的右边
    //60的右边给了90的左边
    //30和90作为60的左右边
    //60成为根
​
    //左右单旋
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
​
        int bf = subLR->_bf;
​
        RotateL(parent->_left);
        RotateR(parent);
​
​
        if (bf == 1)
        {
            subLR->_bf = 0;
            parent->_bf = 0;
            subL->_bf = -1;
        }
        else if (bf == -1)
        {
            subLR->_bf = 0;
            parent->_bf = 1;
            subL->_bf = 0;
        }
        else if (bf == 0)
        {
            parent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }
​
    void InOrder()
    {
        _InOrder(_root);
    }
    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;
    }
​
    
    //判断是否是平衡树
    bool IsBalance()
    {
        return _IsBalance(_root);
    }
​
    int Height()
    {
        return _Height(_root);
    }
    int Size()
    {
        return _Size(_root);
    }
​
    int _Size(Node* root)
    {
        return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
    }
​
    int _Height(Node* root)
    {
        if (root == nullptr)
        {
            return 0;
        }
​
        return max(_Height(root->_left), _Height(root->_right)) + 1;
    }
​
    bool _IsBalance(Node* root)
    {
        if (root == nullptr)
        {
            return true;
        }
​
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        //不平衡
        if (fabs(leftHeight - rightHeight) >= 2)
        {
            return false;
        }
​
        //检查平衡因子
        if (rightHeight - leftHeight != root->_bf)
        {
            cout << root->_kv.first << endl;
            return false;
        }
​
        return fabs(leftHeight - rightHeight) < 2
            && _IsBalance(root->_left)
            && _IsBalance(root->_right);
    }
​
    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;;
        _InOrder(root->_right);
    }
​
private:
    Node* _root = nullptr;
};


4.旋转细化


  1.  
    新节点插入较高左子树的左侧---左左：右单旋
     






LL


  1.  
    新节点插入较高右子树的右侧---右右：左单旋
     




image-20241105231659633


3.新节点插入较高左子树的右侧---左右：先左单旋再右单旋




LR


  1.  
    新节点插入较高右子树的左侧---右左：先右单旋再左单旋
     
     
    RL
     


5.总结


假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑


  1.  
    pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
     


当pSubR的平衡因子为1时，执行左单旋


当pSubR的平衡因子为-1时，执行右左双旋


  1.  
    pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
     


当pSubL的平衡因子为-1是，执行右单旋


当pSubL的平衡因子为1时，执行左右双旋


旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新


6.性能


AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，


这样可以保证查询时高效的时间复杂度，即logN。


但是如果要对AVL树做一些结构修改的操作，性能非常低下，


比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。


因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。


三、RB树（红黑树）


1.概念


红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。


通过对任何一条从根到叶子的路径上各个结点着色方式的限制，


红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。




RBT


2.性质


红黑树的性质


  1.  
    每个结点不是红色就是黑色
     
  2.  
    根节点是黑色的
     
  3.  
    *如果一个节点是红色的，则它的两个孩子结点是黑色的
     
  4.  
    *对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
     
  5.  
    每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
     


最长路径 <= 最短路径*2


AVL树：严格平衡（更多的旋转--保持平衡）|二叉| RB树：近似平衡|二叉| B树：|多叉树|平衡


3.定义


#include<iostream>
using namespace std;
#include<assert.h>
#include<vector>
​
enum Color
{
    RED,
    BLACK
};
​
template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
​
    pair<K, V> _kv;
    Color _col;
​
    RBTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _kv(kv)
        , _parent(nullptr)
        , _col(RED)
    {
​
    }
};


4.实现


template<class K, class V>
struct RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
​
    //新插入节点，插入红色（可能违反规则3）
    //插入黑色，必然违反规则4
​
    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 (grandfather->_left == parent)
            {
                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
            {
                Node* uncle = grandfather->_left;
                //叔叔存在且为红--变色即可
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
​
                    //继续往上处理
                    cur = grandfather;
                    parent = cur->_parent;
                }
                //叔叔不存在/叔叔存在且为黑
                else
                {
                    if (cur == parent->_left)
                    {
                        //                  g
                        //          u               p
                        //                     c
                        //
​
                        //                  ||
                        //                  g
                        //          u               c
                        //                              p
​
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    
                    else
                    {
                        //                  g
                        //          u               p
                        //                              c
                        //
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
​
        _root->_col = BLACK;
​
​
        return true;
    }
​
    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
​
        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
​
        Node* ppnode = parent->_parent;
​
        parent->_parent = subL;
​
        if (_root == parent)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subL;
            }
            else
            {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
    }
​
    //左单旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
​
        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
​
        subR->_left = parent;
​
        Node* ppnode = parent->_parent;
​
        parent->_parent = subR;
​
        if (_root == parent)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subR;
            }
            else
            {
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
    }
    
    void InOrder()
    {
        _InOrder(_root);
    }
​
    bool IsBalance()
    {
        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);
​
        //每个节点记录一个值：根到当前节点路径中黑色节点的数量
        //形参
​
    }
​
private:
    bool Check(Node* root, int blacknum,const int refnum)
    {
        if (root == nullptr)
        {
            //cout << blacknum << endl;
            if (refnum != blacknum)
            {
                cout << root->_kv.first << "存在黑色节点数量不相等的路径" << 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);
    }
    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;;
        _InOrder(root->_right);
    }
​
private:
    Node* _root = nullptr;
    //size_t _size = 0;
};




5.调整细化


检测新节点插入后，红黑树的性质是否造到破坏


因为新节点的默认颜色是红色，


因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；


但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，


此时需要对红黑树分情况来讨论：


约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点


情况一: cur为红，p为红，g为黑，u存在且为红


解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。




1


情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑


p为g的左孩子，cur为p的左孩子，则进行右单旋转；


相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转


p、g变色--p变黑，g变红




2




情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑


p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；


相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转


则转换成了情况2




3


6.红黑树与AVL树的比较


红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log N)，


红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，


相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，


而且红黑树实现比较简单，所以实际运用中红黑树更多。




标签：Node,right,cur,parent,二叉,AVL,红黑树,root,left	

From： https://blog.csdn.net/lll_666666/article/details/143636050
      

      




      

      

        
相关文章

        

          
    
 
  • JS数据结构之树和二叉树
    一、树树（Tree）是一种非常常见的数据结构，它模拟了自然界中树的结构，由节点（或称为顶点）组成，并且具有层次化的组织形式。树结构在计算机科学中广泛应用，例如在组织数据、管理信息层次以及算法设计中。1.基本概念节点（Node）根节点（Root）：树的最顶端节点，没有父节点。内部节点（InternalNod......
     
  • Leecode热题100-104.二叉树中的最大路径和
    二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。示例......
     
  • 洛谷题单指南-二叉堆与树状数组-P1168 中位数
    原题链接：https://www.luogu.com.cn/problem/P1168题意解读：中位数就是位于中间的数，前1个数的中位数是第1个，前3个数的中位数是第2个，前5个数的中位数的第3个...以此类推。所以，此题本质上就是动态维护一组数，每1/3/5...等奇数个取第k小的数，取一次后k++。解题思路：要动态维护数据，且每......
     
  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接：https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接：https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内，所以递归是要统计子树的高度的intg......
     
  • 二叉树遍历
    二叉树遍历这个问题，以前一直没搞懂，只是模糊的了解。先序遍历:先访问根节点，再从左到右依次访问各子树。ABDECFG中序遍历:先访问左节点，再访问根节点，最后再访问右节点。DBEACGF后序遍历:先从左到右遍历各棵子树，再访问根节点。DEBGFCA先中后实际上对应的是根遍历的位置。层次遍历......
     
  • 代码随想录算法训练营第二十一天| leetcode669. 修剪二叉搜索树、leetcode108.将有序
    1leetcode669.修剪二叉搜索树题目链接：669.修剪二叉搜索树-力扣（LeetCode）文章链接：代码随想录视频链接：你修剪的方式不对，我来给你纠正一下！|LeetCode：669.修剪二叉搜索树_哔哩哔哩_bilibili思路：目前想的是分三种情况，第一种情况就是这个数删除左边全部，第二种删除右边的全部，第......
     
  • 二叉树 （王道数据结构 C语言版）
    2004.11.04计算一颗给定二叉树的所有双分支节点个数编写把一个树的所有左右子树进行交换的函数求先序遍历中第k个结点的值(1<=k<=二叉树中的结点个数)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefstructBitnode{......
     
  • 代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.
    1leetcode235.二叉搜索树的最近公共祖先题目链接：235.二叉搜索树的最近公共祖先-力扣（LeetCode）文章链接：代码随想录视频链接：二叉搜索树找祖先就有点不一样了！|235.二叉搜索树的最近公共祖先_哔哩哔哩_bilibili思路：用之前一样的方法，哈哈哈哈哈，好处就是做出来了，但是我觉得需......
     
  • 二叉树的递归遍历和迭代遍历
    递归每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件：写完了递归算法,运行的时......
     
  • 洛谷题单指南-二叉堆与树状数组-P2827 [NOIP2016 提高组] 蚯蚓
    原题链接：https://www.luogu.com.cn/problem/P2827题意解读：初始n个数，每次取最大值x，根据u/v分成两部分：x*u/v，x-x*u/v，然后其余数都增加q，整个过程重复m次。输出有两类数据：第t，2t，3t...次取出的最大值；最后剩余的数第t，2t，3t...个，从大到小输出。解题思路：直观上，通过模拟法可以实......
     
    •            
          

        

      

    

    

      
赞助商

      




      

      
阅读排行

      

        
      

    

  





  
 
    
网站主页关于我们联系我们网站地图 

    
本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。 

    
Copyright © 2020-2023  IPS99  版权所有 IPS99