【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)

简介: 【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解

【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)https://developer.aliyun.com/article/1617412


七、AVLTree.h

#pragma once
#include <assert.h>
#include <iostream>
using namespace std;
//设置默认权限为公用的结构体
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;
        //主要类型
        AVLTreeNode(const pair<K, V>& kv)
            :_left(nullptr)
                , _right(nullptr)
                , _parent(nullptr)
                , _kv(kv)
                , _bf(0)
            {}
    };
template<class K, class V>
    class AVLTree
    {
        typedef AVLTreeNode<K, V> Node;
        public:
        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 Insert(const pair<K, V>& kv)
        {
            if (_root == nullptr)
            {
                _root = new Node(kv);
                return true;
            }
            //也是查找需要插入的地方,进行插入
            Node* parent = nullptr;
            Node* cur = _root;
            //目的就是让cur走到合适的空位置
            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
                {
                    assert(!cur);
                }
            }
            //需要将这个节点连接起来
            cur = new Node(kv);
            cur->_parent = parent;
            if (parent->kv.first > cur->_kv.first)
            {
                parent->_left = cur;
            }
            else if (parent->kv.first < cur->_kv.first)
            {
                parent->_right = cur;
            }
            //上述完成了插入的逻辑,调正平衡因子
            while (parent)
            {
                //平衡因子的规则
                if (parent->_left == cur)
                {
                    parent->_bf--;
                }
                else if (parent->_right == cur)
                {
                    parent->_bf++;
                }
                //判断是否回到父亲节点改动
                if (parent->_bf == 0)
                {
                    //没有啥问题,可以跳出程序
                    break;
                }
                else if (parent->_bf == 1 || parent->_bf == -1)
                {
                    cur = parent;
                    parent = parent->_parent;
                }
                //出现问题,这种情况是由情况二变化过来的,那么就是说,cur和parent向上移动了
                else if (parent->_bf == 2 || parent->_bf == -2)
                {
                    //这里根据规律,去固定改变平衡因子
                    if (parent->_bf == 2 && cur->_bf == 1)
                    {
                        RotateL(parent);
                    }
                    if (parent->_bf == -2 && cur->_bf == -1)
                    {
                        RotateR(parent);
                    }
                    //双旋
                    if (parent->_bf == 2 &&  cur->_bf == -1)
                    {
                        RotateRL(parent);
                    }
                    if (parent->_bf == -2 && cur->_bf == 1)
                    {
                        RotateLR(parent);
                    }
                    break;
                }
                else
                {
                    assert(false);
                }
            }
        }
        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 (parent == _root)
            {
                SubL = _root;
                SubL->_parent = nullptr;
            }
            else
            {
                if (ppNode->_left == parent)
                {
                    ppNode->_left = SubL;
                }
                else if (ppNode->_right == parent)
                {
                    ppNode->_right = SubL;
                }
                SubL->_parant = ppNode;
            }
            SubL->_bf = 0;
            parent->_bf = 0;
        }
        void RotateL(Node* parent)
        {
            Node* SubR = parent->_right;
            Node* SubRL = SubR->_left;
            parent->_right = SubRL;
            if (SubRL)
                SubR->_parent = parent;
            SubR->_left = parent;
            Node* ppNode = parent->_parent;
            parent->_parent = SubR;
            if (parent == _root)
            {
                SubR = _root;
                SubR->_parent = nullptr;
            }
            else
            {
                if (ppNode->_left == parent)
                {
                    ppNode->_left = SubR;
                }
                else if (ppNode->_right == parent)
                {
                    ppNode->_right = SubR;
                }
                SubR->_parant = ppNode;
            }
            SubR->_bf = 0;
            parent->_bf = 0;
        }
        void RotateRL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            int bf = subRL->_bf;
            RotateR(subR);
            RotateL(parent);
            subRL->_bf = 0;
            if (bf == 1)
            {
                subR->_bf = 0;
                parent->_bf = -1;
            }
            else if (bf == -1)
            {
                parent->_bf = 0;
                subR->_bf = 1;
            }
            else
            {
                parent->_bf = 0;
                subR->_bf = 0;
            }
        }
        void RotateLR(Node* parent)
        {
            Node* SubL = parent->_left;
            Node* SubLR = SubL->_right;
            int _bf = SubLR->_bf;
            RotateL(parent->_left);
            RotateR(parent);
            if (_bf == 0)
            {
                parent->_bf = 0;
                SubL->_bf = 0;
                SubLR->_bf = 0;
            }
            else if (_bf == 1)
            {
                parent->_bf = 0;
                SubL->_bf = -1;
                SubLR->_bf = 0;
            }
            else if (_bf == -1)
            {
                parent->_bf = 1;
                SubL->_bf = 0;
                SubLR->_bf = 0;
            }
            else
            {
                assert(false);
            }
        }
        void InOder()
        {
            _InOder(_root);
            cout << endl;
        }
        bool IsBalance()
        {
            return _IsBalance(_root);
        }
        int Height()
        {
            return _Height(_root);
        }
        int Size()
        {
            return _Size(_root);
        }
        private:
        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 (abs(leftHeight - rightHeight) >= 2)
            {
                cout << root->_kv.first << endl;
                return false;
            }
            // 顺便检查一下平衡因子是否正确
            if (rightHeight - leftHeight != root->_bf)
            {
                cout << root->_kv.first << endl;
                return false;
            }
            return _IsBalance(root->_left)
                && _IsBalance(root->_right);
        }
        void _InOder(Node* _root)
        {
            if (_root == nullptr)
            {
                return;
            }
            InOder(_root->_left);
            cout << _root->_kv.first << " " << _root->_kv.second << endl;
            InOder(_root->_right);
        }
        private:
        Node* _root = nullptr;
    };
void AVLTest1()
{
    AVLTree<int, int> at;
}

以上就是本篇文章的所有内容,在此感谢大家的观看!这里是高阶数据结构笔记,希望对你在学习高阶数据结构旅途中有所帮助!

相关文章
|
21天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
21天前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
20 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
21天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
15 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
23天前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
24 1
|
23天前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
22 1
|
18天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
22 0
|
21天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
21天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
17 0
|
22天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器