手撕二叉平衡树

这篇具有很好参考价值的文章主要介绍了手撕二叉平衡树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天给大家带来的是平衡树的代码实现,如下:

#pragma once 
#include <iostream>
#include <map>
#include <set>
#include <assert.h>
#include <math.h>
using namespace std;
namespace cc
{
    template<class K, class V>
    struct AVLnode
    {
        int _bf = 0;
        pair<K, V> _val;
        AVLnode<K, V>* _left;
        AVLnode<K, V>* _right;
        AVLnode<K, V>* _parent;
        AVLnode(const pair<K, V>& val = pair<K, V>(), AVLnode<K, V>* left = nullptr, AVLnode<K, V>* right = nullptr, AVLnode<K, V>* parent = nullptr)
            : _val(val)
            , _left(left)
            , _right(right)
            , _parent(parent)
        {}
    };
    template<class K, class V>
    class AVL
    {
    public:
        typedef AVLnode<K, V> node;
        //此parent其实就相当于是旋转点
        void revolveL(node* parent)
        {
            //需要改变的节点
            node* sub = parent->_right;
            node* subl = sub->_left;
            //如果根节点是parent
            if (_root == parent)
            {
                _root = sub;
                sub->_parent = nullptr;
                sub->_left = parent;
                parent->_parent = sub;
                parent->_right = subl;
                if (subl)
                    subl->_parent = parent;
            }
            //此旋转点不是根节点
            else
            {
                node* pparent = parent->_parent;
                if (pparent->_left == parent)
                    pparent->_left = sub;
                else
                    pparent->_right = sub;
                sub->_parent = pparent;
                sub->_left = parent;
                parent->_parent = sub;
                parent->_right = subl;
                if (subl)
                    subl->_parent = parent;
            }
            //旋转完成,更新平衡因子
            sub->_bf = 0;
            parent->_bf = 0;
        }
        void revolveR(node* parent)
        {
            node* sub = parent->_left;
            node* subr = sub->_right;
            if (_root == parent)
            {
                _root = sub;
                sub->_parent = nullptr;
                sub->_right = parent;
                parent->_parent = sub;
                parent->_left = subr;
                if (subr)
                    subr->_parent = parent;
            }
            else
            {
                node* pparent = parent->_parent;
                if (pparent->_left == parent)
                    pparent->_left = sub;
                else
                    pparent->_right = sub;
                sub->_parent = pparent;
                sub->_right = parent;
                parent->_parent = sub;
                parent->_left = subr;
                if (subr)
                    subr->_parent = parent;
            }
            sub->_bf = 0;
            parent->_bf = 0;
        }
        bool insert(const pair<K, V>& x)
        {
            //根节点为空
            if (_root == nullptr)
            {
                _root = new node(x);
                //节点中父指针已经指向nullptr
                return true;
            }
            node* parent = nullptr;
            node* cur = _root;
            while (cur)
            {
                if (x.first < (cur->_val).first)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (x.first > (cur->_val).first)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                    return false;
            }
            cur = new node(x);
            if ((parent->_val).first > x.first)
                parent->_left = cur;
            else
                parent->_right = cur;
            cur->_parent = parent;
            //插入完成,更新平衡因子
            while (parent)
            {
                if (parent->_right == cur)
                    parent->_bf++;
                else if (parent->_left == cur)
                    parent->_bf--;
                //此情况说明cur既不是做孩子也不是右孩子,所以直接报错,说明插入的时候出现了问题
                else
                    assert(false);
                if (abs(parent->_bf) == 0)
                    break;
                else if (abs(parent->_bf) == 1)
                {
                    cur = parent;
                    parent = parent->_parent;
                }
                else if (abs(parent->_bf) == 2)
                {
                    //旋转
                    if (parent->_bf == 2 && cur->_bf == 1)
                    {
                        revolveL(parent);
                        break;
                    }
                    else if (parent->_bf == -2 && cur->_bf == -1)
                    {
                        revolveR(parent);
                        break;
                    }
                    else if (parent->_bf == -2 && cur->_bf == 1)
                    {
                        node* sub = parent->_left;
                        node* subr = sub->_right;
                        int bf = subr->_bf;
                        revolveL(sub);
                        revolveR(parent);
                        if (bf == 0)
                        {
                            parent->_bf = 0;
                            sub->_bf = 0;
                            subr->_bf = 0;
                        }
                        else if (bf == 1)
                        {
                            sub->_bf = -1;
                            parent->_bf = 0;
                            subr->_bf = 0;
                        }
                        else if (bf == -1)
                        {
                            sub->_bf = 0;
                            parent->_bf = 1;
                            subr->_bf = 0;
                        }
                        else
                            assert(false);
                        break;
                    }
                    else if (parent->_bf == 2 && cur->_bf == -1)
                    {
                        node* sub = parent->_right;
                        node* subl = sub->_left;
                        int bf = subl->_bf;
                        revolveR(sub);
                        revolveL(parent);
                        subl->_bf = 0;
                        if (bf == 0)
                        {
                           // subl->_bf = 0;
                            sub->_bf = 0;
                            parent->_bf = 0;
                        }
                        else if (bf == 1)
                        {
                            sub->_bf = 0;
                           // subl->_bf = 0;
                            parent->_bf = -1;
                        }
                        else if (bf == -1)
                        {
                            sub->_bf = 1;
                            //subl->_bf = 0;
                            parent->_bf = 0;
                        }
                        else
                            assert(false);
                        break;
                    }
                    //如果走到这步,说明这棵树的平衡因子有问题
                    else
                        assert(false);
                }
                else
                    assert(false);
            }
            return true;
        }
        int high()
        {
            return _high(_root);
        }
        bool check()
        {
            return _check(_root);
        }
    private:
        node* _root = nullptr;
        bool _check(node* root)
        {
            if (root == nullptr)
                return true;
            int bf = _high(root->_right) - _high(root->_left) ;
            if (bf != root->_bf)
            {
                cout << "bf:不一样" << endl;
                return false;
            }
            cout << "bf:" << bf <<" " << "root:" << (
                root->_val).first << endl;
            return _check(root->_left) && _check(root->_right);
        }
        int _high(node *root)
        {
            if (root == nullptr)
                return 0;
            int left = _high(root->_left);
            int right = _high(root->_right);
            if (left > right)
                return left + 1;
            else
                return right + 1;
        }
    };
}

这个仅仅是平衡树的插入,其实二叉平衡树的插入并不难,逻辑就是那么几个,但是难得是细节处的实现,尤其是平衡因子更新的那一块,特别的容易弄混人,只要记住四种模型就可以了。两种单旋,两种双旋,还是有点难以理解的,下面一一讲解

1.左单旋

左单旋大概的图示这样子的:

手撕二叉平衡树,C++篇,数据结构,算法

如上图,如果没有插入100,那么此时的二叉平衡树是平衡的,但是此时如果插入100,此时30这个节点的平衡因子是2,所以此时需要旋转来降低这棵树的高度,此时就是左旋。其实此处还分为好几种情况,但是这几种情况都是一样的旋转方法,因为都在60这个节点的右子树中,所以此时就把30当做旋转点,让60左旋,在把60这个节点的左子树链接到30的右指针处就好了。

2.右单旋

手撕二叉平衡树,C++篇,数据结构,算法

和左单旋一样,因为新插入的节点导致30这个节点的平衡因子为-2,所以此时就要旋转来降低这棵树的高度,此时是要右旋,这个和左旋一样,30是旋转点,25进行右旋,把25这个节点的右子树连接到30这个节点的左子树处就可以了。

3.先左旋,在右旋

手撕二叉平衡树,C++篇,数据结构,算法

这个就是先左旋,在右旋,也是插入了新的节点导致的。这里没有写节点具体的值是因为,因为40这个节点的右子树或是左子树中的值不确定,所以就用了一个空节点来代替插入的值。其实就是两次单旋的结果,先把40以30为旋转点进行左旋,再把60当旋转点进行右旋,此时就旋转完成。而30与40的子树怎么连接参考左单旋与右单旋的旋转方式

4.先右旋,在左旋

手撕二叉平衡树,C++篇,数据结构,算法

这个模型就是先右旋,在左旋。先把60当旋转点进行旋转,再把30当旋转点进行旋转,至于子树怎么连接,与先左旋,在右旋相同。

以上就是平衡二叉树的旋转方式,下面来总结一下思路:

1.与二叉搜索树的插入一样

2.链接parent指针

3.更新平衡因子

4.如果左右不平衡,那么就开始旋转

增删查时间复杂度:

首先我们知道的是,他是一个二叉树,所以他的高度是log n,而我们在增删查的时候,我们最坏的结果就是要查叶子结点或者所查的节点不在此树,此时它的时间复杂度就是log n,但是他的空间复杂度也是logn,所以个人认为他是以空间换区时间的一种数据结构,但是他的效率确实很高,而对于我们所说的红黑树,其实严格意义来说也是一种logn的算法,但是他没有平衡二叉树这么严谨,平衡二叉树旋转的次数比较多,但是红黑树却没有,旋转其实也是一种消耗,但是旋转的时间复杂度是O(1),严格来说,有消耗,但是也没那么严重,但是对于红黑树来说,就是尽可能不旋转,减少这种消耗。

对于红黑树的代码以及讲解,下一篇会详细讲解,也会对比AVL树和红黑树的优缺点。期待下一篇内容吧!!谢谢大家支持!!!文章来源地址https://www.toymoban.com/news/detail-692002.html

到了这里,关于手撕二叉平衡树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(58)
  • 手撕二叉树(图解+代码)

    在学习二叉树之前,我们有必要了解一下树的概念和常用术语。接下来以下面这棵树为例来回顾下树相关概念: 树的概念:一种非线性的数据结构,由n(n =0)个节点组成的一个具有层次关系的集合。 树的术语: 节点的度 一个节点含有子树的个数,例如上图中A的度为6. 树的度

    2023年04月22日
    浏览(37)
  • 手撕二叉树

    2024年02月07日
    浏览(39)
  • 数据结构之二叉树和平衡二叉树

    1、二叉树: 2、平衡二叉树:

    2024年04月17日
    浏览(44)
  • 数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)

    目录 基本介绍 平衡因子 平衡二叉树  平衡二叉树的高度  什么是平衡二叉树? 以一个例子来解释一下: 搜索树结点按不同的插入次序,将会导致不同的深度和平均查找长度ASL   在二叉搜索树中查找一个元素:  (a)要找到Jan,需要查找一次;要找到Feb,需要查找两次;

    2023年04月26日
    浏览(66)
  • 数据结构之平衡二叉树详解

    平衡二叉树(balanced binary tree) 又称AVL树(Adelson-Velskii and Landis) 一棵平衡二叉树或者是空树,或者是具有下列性质的 二叉排序树 :         1,左子树与右子树的高度之差的绝对值小于等于1;         2,左子树和右子树也是平衡二叉排序树. 为了方便起见,给每

    2024年02月03日
    浏览(41)
  • 【数据结构】二叉排序树——平衡二叉树的调整

    参考视频: 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 (1)什么是平衡二叉树 平衡二叉树(Balanced Binary Tree)是一种特殊的二叉查找树,它的目的是保持树的高度尽量平衡,以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(39)
  • 数据结构奇妙旅程之二叉平衡树

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年03月11日
    浏览(58)
  • 十道题带你手撕二叉树

    题目: 思路一:( 遍历的方法 ) 将根节点的值与二叉树中的每一个节点存储的val值进行比较,如果不同就返回false,如果全部相同,就返回true。 代码: 思路二: 判断当前根节点的值是否与其左右子节点的值相等,如果不相等就返回 false ,同样,如果递归调用到了节点为

    2023年04月08日
    浏览(41)
  • 数据结构---手撕图解二叉树(含大量递归图解)

    二叉树的几乎所有实现都是依靠递归实现,递归的核心思路是把任何一个二叉树看成根和左右子树,而二叉树递归的核心玩法就是把二叉树的左右子树再看成根,再找左右子树,再看成根… 因此,解决二叉树问题实际上要把二叉树转换成一个一个子树的过程,找到一个一个的

    2024年02月16日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包