Cpp 二叉树

二叉搜索树

左边子树的节点小于根节点右边子树的节点大于跟节点
方便搜索树的节点
搜索二叉树也叫做排序二叉树

代码实现

#pragma once
#include <iostream>
using  namespace  std;
namespace chen
{
    template<class K>
    struct BTreeNode{ //binary Search Tree

        BTreeNode(const K& val) {
            _val = val;
            _left = nullptr;
            _right = nullptr;
        }
        BTreeNode<K> *_left;
        BTreeNode<K> *_right;
        K _val;
    };
    template <class K>
    class BSTree{
    typedef BTreeNode<K> Node;
    public:
        bool Insert(const K& key)
        {

            if(_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
            Node * Cur = _root;
            Node * Parents;
            while(Cur != nullptr)
            {
                Parents = Cur;
                if(Cur ->_val < key)
                {
                    Cur = Cur-> _right;
                }
               else if(Cur -> _val > key)
                {
                    Cur = Cur->_left;
                }
                else return false;
            }
            Node *Curd = new Node(key);  // 找到空节点

            if(Parents->_val > key)
            {
                Parents->_left = Curd;
            }else{
                Parents->_right = Curd;
            }
            return true;
        }

        void InOrder(){
            _InOrder(_root);
            cout << endl;
        }

        void _InOrder(Node *root)
        {

            if(root == nullptr)return;

            _InOrder(root->_left);
            cout << root->_val << " ";
            _InOrder(root->_right);
        }
        bool Find(const K& val){   // 虽然设计使用递归也可以实现 但是能用循环就用循环
            Node *temp = _root;
            while(temp){
                if(temp->_val == val){
                    return true;
                }
                else if(temp->_val < val)
                {
                    temp = temp->_right;
                }else{
                    temp = temp->_left;
                }
            }
            return false;
        }
        bool Erase(const K& val)
        {
            if(_root == nullptr)return false;

            Node * Cur = _root; // 要寻找的节点
            Node * Parent = _root;   // 节点的父节点
            while(Cur)
            {
                if(val == Cur->_val){ // 此时Cur 为要删除的节点
                    break;
                }else if(val < Cur->_val)
                {
                    Parent = Cur; // 走之前记录一下父节点
                    Cur = Cur->_left;
                }else{
                    Parent = Cur;  // 走之前记录一下父节点
                    Cur = Cur->_right;
                }
            }
            if(Cur == nullptr)return false; // 没有找到返回  False
            // 此时应已经找到要删除的节点
            if(Cur->_left == nullptr){    //这边要分情况  字节点在左右的情况
                // 子树左字树为null
                if(Parent->_right == Cur)
                    Parent->_right = Cur->_right;
                else
                    Parent->_left = Cur -> _right;
                delete Cur;
            }else if(Cur->_right == nullptr){ //这边要分情况  字节点在左右的情况
                // 子树右字树为null
                if(Parent->_right == Cur)
                    Parent->_right = Cur->_left;
                else
                    Parent->_left = Cur -> _left;
                delete Cur;
            }else{
                // 子树两边子树都不为空  imp

                Node * RightMinParent = Cur; //此时 Cur 为 要删除的节点
                Node * RightMin = Cur->_right;  // 找到Cur右边最小的节点

                while(RightMin->_left)
                {
                    RightMinParent = RightMin;
                    RightMin = RightMin->_left;
                }
                // 交换值
                Cur->_val =  RightMin->_val;

                if( RightMinParent->_left == RightMin)
                {  // 父节点的左边 为 RightMin
                    // RightMin 为 左为空 让父亲指向其右
                    RightMinParent->_left = RightMin->_right;

                }else
                {
                    //
                    RightMinParent ->_right = RightMin->_right;
                }
                delete RightMin;
            }
            return  true;
        }
    private:
        Node *_root = nullptr;
    };
    void testTree()
    {
        BSTree<int> root;
        int arr[] = {5,3,4,1,7,3,2,2};
        for(auto i:arr)
        {
//            cout << (int )root.Insert(i) <<" ";
            root.Insert(i) ;
        }
        root.InOrder();
//        root.Erase(1);
        root.Erase(7);
        root.Erase(1);
        root.InOrder();
    }
}

二叉树的逻辑模型

K模型只有Key作为关键码,结构中只需要存储Key 即可,关键码即为搜索到的值. K 就为值上面的代码为K 模型使用场景:判断在不在
KV 模型: 每一个关键码Key 都有与之对应的Value 即<Key , Value>的键值对这种方法在现实生活中非常常见使用场景通过Key 寻找对应的Value

在K 模型上进行修改为K/V 模型

#pragma once
#include <iostream>

using  namespace  std;

namespace chen
{

    template<class K,class Value>
    struct BTreeNode{ //binary Search Tree

        BTreeNode(const K& Key,const Value& val) {
            _val = val;
            _left = nullptr;
            _right = nullptr;
            _Key = Key;
        }
        BTreeNode<K,Value> *_left;
        BTreeNode<K,Value> *_right;
        Value _val;
        K _Key;
    };


    template <class K,class Value>
    class BSTree{
    typedef BTreeNode<K,Value> Node;
    public:
        bool Insert(const K& key,const Value& value )
        {

            if(_root == nullptr)
            {
                _root = new Node(key,value);
                return true;
            }
            Node * Cur = _root;
            Node * Parents = nullptr;
            while(Cur != nullptr)
            {
                Parents = Cur;
                if(Cur ->_Key< key)
                {
                    Cur = Cur-> _right;
                }
               else if(Cur -> _Key > key)
                {
                    Cur = Cur->_left;
                }
                else return false;
            }
            Node *Curd = new Node(key,value);  // 找到空节点

            if(Parents->_Key > key)
            {
                Parents->_left = Curd;
            }else{
                Parents->_right = Curd;
            }
            return true;
        }

        void InOrder(){
            _InOrder(_root);
            cout << endl;
        }

        void _InOrder(Node *root)
        {

            if(root == nullptr)return;

            _InOrder(root->_left);
            cout << root->_Key  << " " << root->_val << endl;
            _InOrder(root->_right);
        }

        Value*  Find(const K& Key){   // 虽然设计使用递归也可以实现 但是能用循环就用循环
            Node *temp = _root;
            while(temp){
                if(temp->_Key == Key){
                    return temp;
                }
                else if(temp->_Key < Key)
                {
                    temp = temp->_right;
                }else{
                    temp = temp->_left;
                }
            }
            return nullptr;
        }



        // 删除节点
        bool Erase(const K& key){

            if(_root == nullptr) return false; // 根为空
            if(_root->_left == nullptr && _root->_right == nullptr&&key == _root->_val)
                //删除1个节点并且为根 情况4
            {
                _root = nullptr;
                return true;
            }
            Node * Cur = _root;
            Node *Parent = nullptr;

            while(Cur) // 定位到要删除节点的位置
            {
                if(key > Cur->_Key)
                {
                    Parent = Cur;
                    Cur = Cur->_right;
                }else if(key < Cur->_Key)
                {
                    Parent = Cur;
                    Cur = Cur->_left;
                }else{
                    break;
                }
            }
            // 没有找到节点
            if(Cur == nullptr){return false;}

            //处理删除的节点

            // 情况1 : 左子树为空
            if(Cur->_left == nullptr){

                if(Parent->_left == Cur)
                {
                    Parent->_left = Cur->_right;
                } else{
                    Parent->_right = Cur->_right;
                }
                delete Cur;
            }
            // 情况2: 右子树为空
            else if(Cur->_right == nullptr)
            {
                if(Parent->_left == Cur)
                {
                    Parent->_left = Cur->_left;
                } else{
                    Parent->_right = Cur->_left;
                }
                delete Cur;
            }
            // 情况3: 左右子树都不为空
            else
            {

                Node* rightMinParent = Cur;
                Node* rightMin = Cur->_right;

                while(rightMin->_left)  // 找到最左边
                {
                    rightMinParent = rightMin;
                    rightMin = rightMin->_left;
                }

                Cur->_Key = rightMin->_Key;
                Cur->_val = rightMin->_val;


                 // 删除右边子树的最小节点
                if(rightMinParent->_left == rightMin){
                    rightMinParent->_left = rightMin->_right;
                }else{
                    rightMinParent->_right= rightMin->_right;
                }
                delete rightMin;
            }


            return true;

        }



    private:
        Node *_root = nullptr;
    };

    void testTree() {

//        BSTree<int, string> root;
        BSTree<int,int> root;



        int keys[] = {5, 3, 4, 1, 7, 6, 8, 2};
//        string values[] = {"five", "three", "four", "one", "seven", "six", "eight", "two"};

        for (int i = 0; i < 8; i++) {
            root.Insert(keys[i], keys[i]);
        }


//        root.Insert(7,1);
        root.InOrde r();
        root.Erase(5);
        root.Erase(1);
        root.InOrder();
    }


}

oid testTree() {

        BSTree<int, string> root;
//        BSTree<int,int> root;
        int keys[] = {5, 3, 4, 1, 7, 6, 8, 2};
        string values[] = {"five", "three", "four", "one", "seven", "six", "eight", "two"};

        for (int i = 0; i < 8; i++) {
            root.Insert(keys[i], values[i]);
        }
        
//        root.Insert(7,1);
        root.InOrder();
        root.Erase(5);
        root.Erase(1);
        root.InOrder();
    }

/home/chen/CLionProjects/untitled/cmake-build-debug/untitled 1 one 2 two 3 three 4 four 5 five 6 six 7 seven 8 eight
2 two 3 three 4 four 6 six 7 seven 8 eight
Process finished with exit code 0

二叉树的性能分析

搜索效率 :

插入数据是有序的搜索树的效率完全没有办法被保障
所以搜索树的效率为 (O(N))

如何解决 ? 平衡树

AVL 树
红黑树

搜索🌲中的key 是不允许修改的
只能修改 key

Map _ Set

容器:

序列式容器: vector / list / string / deque
关联式容器: map / set / unordered_map / unordered_set
map / multimp /set / multiset
其都是按照二叉搜索树的搜索顺序来实现的假如往树中插入的顺序是按照二叉搜索树来实现的,但是二叉树都有自身的缺陷,加入往树中插入的元素有序或者接近有序就会退化成 O(n),因此 map set 等关联式容器对二叉树进行平衡处理

AVLTree 高度平衡二叉搜索树

二叉搜索树
二叉搜索树的左子树和右子树的高度差不大于1

实现使用平衡因子 (平衡因子 = 左子树高度 - 右子树的高度) 将高度控制在 O(logn)

AVL树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子,因此AVL 树也是二叉搜索树 .

AVL 树的插入分为两步

按照二叉搜索树的方式插入新节点
调整节点的平衡因子

当插入节点后会破坏AVL树的平衡性需要对树进行旋转

AVL树的旋转

AVL 中旋转部分是最难以理解的

我细分成四个部分 (｡♥‿♥｡)

主要是像是一个臣篡位

安排小人
将自己左边/右边子树安排在皇帝右/左边
如果有小人小人的上司就是皇帝
起义
让皇帝成为臣子
自己代替他的位置
黄袍加身
如果皇帝上面没老人直接登基
如果左/右有同化为自己的老人
让旧皇帝服从新皇帝
制定法则
从0开始接手旧皇的bf

实现AVL🌲的代码

#pragma once

#include <iostream>
using namespace std;
namespace chen{


    template< class K,class V>
    struct avlTree {

        //  构造函数
        avlTree(const pair<K,V>& val)
            :_parent(nullptr),_left(nullptr),_right(nullptr),_bf(0),_Data(val)
        {}
        avlTree<K,V> * _parent;
        avlTree<K,V> * _left;
        avlTree<K,V> * _right;
        pair<K,V> _Data;
        int _bf;
    };


    template<class K,class V>


    class aAVLTree{

        typedef avlTree<K,V> Node;
    public:
        bool insert(const pair<K,V> & data)
        {
            // root is null
            if(!_root)
            {
                _root = new Node(data);
                return true;
            }

            Node * Cur = _root;
            Node * parent = nullptr;

            while(Cur)
            {
                if(Cur->_Data.first < data.first)
                {
                    parent = Cur;
                    Cur = Cur->_right;
                }else if(Cur->_Data.first > data.first)
                {
                    parent = Cur;
                    Cur = Cur->_left;
                }else{

                    // 找到重复项
                    return false;
                }
            }
            // 此时找到 Cur 是 新节点要插入的位置

            Cur = new Node(data);
            Cur->_parent = parent;
            // 定Cur 位置
            if(data.first > parent->_Data.first)
            {
                parent->_right = Cur;
            }else{
                parent->_left = Cur;
            }

            // 更新平衡因子
            while(parent){
                if (Cur == parent->_left)
                {
                    parent->_bf --;
                }else{
                    parent->_bf ++;
                }

                if(parent->_bf == 0) // 平衡因子为0  // 平衡状态不需要调整
                {
                    break;
                }
                else if(parent->_bf == 1||parent->_bf == -1)
                {
                    Cur = parent;
                    parent = parent->_parent; // 向上回溯
                }
                else{

                    // 需要进行旋转操作 恢复平衡

                    if(parent->_bf == 2)
                    {
                        if(Cur->_bf == 1)
                        {
                            rotateL(parent);
                        }else{
                            rotateRL(parent);
                        }
                    }else if(parent->_bf == -2){
                        if(Cur->_bf == -1)
                        {
                            rotateR(parent);
                        }else{
                            rotateLR(parent);
                        }
                    }else
                        break;
                }
            }
            return true;
        }

        void InOrder()
        {
            _InOrder(_root);
        }


        int TreeHight()
        {
            return _Height(_root);
        }

        ~aAVLTree() {
            _Destroy(_root);
        }

    private:
        void _InOrder(Node * root)
        {
            if(!root)return ;
            _InOrder(root->_left);
            cout << root->_Data.first <<" : " << root->_Data.second <<endl;
            _InOrder(root->_right);
        }

        //  此为左旋
        void rotateL(Node* parent)
        {
            cout <<"--L--" << endl;

            Node * subR = parent->_right;
            //  开始旋转

            // 安排小人在皇帝身边
            parent->_right = subR->_left;
            if(subR->_left){ // subL 不为空
                subR->_left->_parent = parent;
            }

            // 起义
            subR->_left = parent;
            subR->_parent = parent->_parent;

            // 黄袍加身
            if(parent->_parent == nullptr){
                    _root = subR;
            }else if(parent->_parent->_left == parent)
            {
                parent->_parent->_left = subR;
            }else {
                parent->_parent->_right = subR;
            }

            parent->_parent = subR;

            //  制定法则
          parent->_bf = subR->_bf = 0;

        }

        void rotateR(Node * parent)
        {
            Node * subL = parent->_left;

            cout << "--R--"<<endl;

            // 安排小人
            parent->_left = subL->_right;
            if(subL->_right) {
                subL->_right->_parent = parent;
            }

            //起义
            subL->_right = parent;
            subL->_parent = parent->_parent;

            // 黄袍加身
            if(parent->_parent == nullptr) {
                _root = subL;
            }else if(parent->_parent->_left == parent){
                parent->_parent->_left = subL;
            }else {
                parent->_parent->_right = subL;
            }
            parent->_parent = subL;

            //制定法则
            parent->_bf = subL->_bf = 0;

        }
        void rotateLR(Node * parent)
        {
            cout <<"--------" << endl;
            rotateL(parent->_left);
            rotateR(parent);
            cout <<"--------" << endl;
        }
        void rotateRL(Node * parent)
        {
            cout <<"--------" << endl;
            rotateR(parent->_right);
            rotateL(parent);
            cout <<"--------" << endl;

        }
        int _Height(Node* root) {
            if (!root) return 0;
            return max(_Height(root->_left), _Height(root->_right)) + 1;
        }

        void _Destroy(Node* root) {
            if (root) {
                _Destroy(root->_left);
                _Destroy(root->_right);
                delete root;
            }
        }

        Node * _root = nullptr;
    };
    void testAVLTree() {
        aAVLTree<int, int> tree;
        tree.insert({1, 1});
        tree.insert({2, 2});
        tree.insert({3, 3});
        tree.insert({4, 4});
        tree.insert({5, 5});
        tree.insert({6, 6});
        tree.insert({-1, -1});
        tree.insert({-2, -2});
        tree.insert({-3, -3});
        tree.insert({0, 0});
        tree.InOrder();

        cout << "树的高度是: " << tree.TreeHight() << endl;
    }
};

## AVL 树的删除

AVL 树的删除实际上和插入后的逻辑差不多

右边插入 ,父亲的平衡因子++ 左边插入父亲的平衡因子--

右边删除,父亲的平衡因子--,左边删除父亲的平衡因子++

插入后父亲的平衡因子变成0 说明父亲所在的高度不变,更新结束

删除后,父亲的平衡因子变成0 说明父亲所在的树高度变了,继续往上更新

插入后父亲的平衡因子变成1/-1说明父亲所在的高度变了继续往上更新

删除后父亲的平衡因子变成1/-1 说明父亲所在的树高度不变,更新结束

插入删除后父亲的平衡因子变成 2/-2 说明不平衡旋转处理

        bool Earse(const K& key)
        {
            Node * Cur = _root;
            Node * parent = nullptr; // 要删除节点的父节点
            while(Cur)
            {
                parent = Cur;
                if(Cur->_Data.first == key)
                {
                    break;
                }else if(Cur->_Data.first < key){
                    Cur = Cur->_left;
                }else{
                    Cur = Cur->_right;
                }
            }
            if(Cur == nullptr) return false;
            Node * delNode = Cur; // 记录要删除的节点
            //分明三种情况
            if(Cur->_right && Cur->_left){
                Node * rep = Cur->_right;
                //两个 取出右树最小的节点进行替换
                while(rep->_left)
                {
                    rep = rep->_left;
                }

                Cur->_Data = rep->_Data;
                delNode = rep;
                parent = delNode->_parent;
                Cur = delNode->_right;
            }else{
                if(Cur->_left == nullptr){
                    Cur = Cur->_right;
                }else{
                    Cur = Cur->_left;
                }
            }
            if(parent){

                if(parent->_left == delNode) {
                    parent->_left = Cur;
                    if(Cur)Cur ->_parent = parent;
                    parent->_bf++;
                }else {
                    parent->_right = Cur;
                    if(Cur)Cur->_parent = parent;
                    parent->_bf --;
                }
            }else
            {
                _root = Cur;
                if(Cur)Cur->_parent = nullptr;
            }

            delete delNode;


            //  向上 回溯

            while(parent) {
                if(parent->_bf == 2) {
                    Node * pR = parent->_right;
                    if(pR->_bf >= 0) {
                        rotateL(parent);
                        if(pR->_bf == 0)break;
                    }else {
                        rotateRL(parent);
                    }
                }else if(parent->_bf == -2) {
                    Node * pL = parent->_left;

                    if(pL->_bf >= 0) {
                        rotateR(parent);
                        if(pL->_bf == 0)break;
                    }else {
                        rotateLR(parent);
                    }
                }else if(parent->_bf == 0) {
                    Cur = parent;
                    parent = parent->_parent;
                }
                else break;  // 平衡因子 高 为 1/ -1  高度没变化
            }
            return  true;
        }

补充函数 find 和二叉搜索树的逻辑差不多

Node * find(const V& value)
     {
         Node * Cur = _root;



         while(Cur)
         {
             if(Cur->_Data.first == value)
             {
                 return Cur;
             }else if(Cur->_Data.first < value){

                 Cur = Cur->_left;

             }else{
                 Cur = Cur->_right;
             }
         }

         if(Cur == nullptr) return nullptr;
     }