手撕二叉平衡树

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

#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.左单旋

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

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

2.右单旋

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

3.先左旋,在右旋

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

4.先右旋,在左旋

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

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

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

2.链接parent指针

3.更新平衡因子

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

增删查时间复杂度:

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

对于红黑树的代码以及讲解,下一篇会详细讲解,也会对比AVL树和红黑树的优缺点。期待下一篇内容吧!!谢谢大家支持!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/101783.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

TypeScript学习 + 贪吃蛇项目

TypeSCript简介 TypeScript是JavaScript的超集。它对JS进行了扩展&#xff0c;向JS中引入了类型的概念&#xff0c;并添加了许多新的特性。TS代码需要通过编译器编译为JS&#xff0c;然后再交由JS解析器执行。TS完全兼容JS&#xff0c;换言之&#xff0c;任何的JS代码都可以直…

IP地址、网关、网络/主机号、子网掩码关系

一、IP地址 IP地址组成 IP地址分为两个部分&#xff1a;网络号和主机号 &#xff08;1&#xff09;网络号:标识网段&#xff0c;保证相互连接的两个网段具有不同的标识。 &#xff08;2&#xff09;主机号:标识主机&#xff0c;同一网段内&#xff0c;主机之间具有相同的网…

构建稳定的爬虫系统:如何选择合适的HTTP代理服务商

在构建一个稳定、高效的爬虫系统中&#xff0c;选择合适的HTTP代理服务商是至关重要的一步。本文将介绍如何选取可靠且性能优秀的HTTP代理服务供应商&#xff0c;来完成搭建一个强大而稳定的爬虫系统。 1.了解不同类型和特点 -免费公开代理服务器:提供免费但可能存在限制或不…

opencv鼠标事件函数setMouseCallback()详解

文章目录 opencv鼠标事件函数setMouseCallback()详解1、鼠标事件函数&#xff1a;&#xff08;1&#xff09;鼠标事件函数原型&#xff1a;setMouseCallback()&#xff0c;此函数会在调用之后不断查询回调函数onMouse()&#xff0c;直到窗口销毁&#xff08;2&#xff09;回调函…

优秀的ui设计作品(合集)

UI设计师需要了解的九个Tips 1.图片类APP排版突破 规则是死的&#xff0c;人是活的。很多时候&#xff0c;如果需求是比较宽要尝试突破原则&#xff0c;用一些另类的排版方式&#xff0c;其实也是做好设计的本质。在图片类app中&#xff0c;错落一些的排版会使你的作品更有魅力…

怎么将pdf合并成一个?将pdf合并成一个的方法

在日常工作和学习中&#xff0c;我们经常会遇到需要将多个PDF文件合并成一个的情况。这不仅能够提高文件管理的便捷性&#xff0c;还能节省存储空间并使阅读更加流畅。那么&#xff0c;怎么将pdf合并成一个呢&#xff1f;在本文中&#xff0c;我将为您介绍几种简单实用的方法&a…

xml

1.xml 1.1概述【理解】 万维网联盟(W3C) 万维网联盟(W3C)创建于1994年&#xff0c;又称W3C理事会。1994年10月在麻省理工学院计算机科学实验室成立。 建立者&#xff1a; Tim Berners-Lee (蒂姆伯纳斯李)。 是Web技术领域最具权威和影响力的国际中立性技术标准机构。 到目前为…

C++/C:pass-by-value(值传递)与pass-by-reference(引用传递)

一、C的引用&#xff08;reference&#xff09; 1.1、引用的概念 c中新增了引用&#xff08;reference&#xff09;的概念&#xff0c;引用可以作为一个已定义变量的别名。 Declares a named variable as a reference, that is, an alias to an already-existing object or f…

docker 笔记1

目录 1.为什么有docker ? 2.Docker 的核心概念 3.容器与虚拟机比较 3.1传统的虚拟化技术 3.2容器技术 3.3Docker容器的有什么作用&#xff1f; 3.4应用案例 4. docker 安装下载 4.1CentOS Docker 安装 4.2 Docker的基本组成 &#xff1f;&#xff08;面试&#xff09…

2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书海口经济学院图书馆

2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书海口经济学院图书馆

基于 Debian 12 的 Devuan GNU+Linux 5 为软件自由爱好者而生

导读Devuan 开发人员宣布发布 Devuan GNULinux 5.0 “代达罗斯 “发行版&#xff0c;它是 Debian GNU/Linux 操作系统的 100% 衍生版本&#xff0c;不包含 systemd 和相关组件。 Devuan GNULinux 5 基于最新的 Debian GNU/Linux 12 “书虫 “操作系统系列&#xff0c;采用长期支…

路由器的简单概述(详细理解+实例精讲)

系列文章目录 华为数通学习&#xff08;4&#xff09; 目录 系列文章目录 华为数通学习&#xff08;4&#xff09; 前言 一&#xff0c;网段间通信 二&#xff0c;路由器的基本特点 三&#xff0c;路由信息介绍 四&#xff0c;路由表 五&#xff0c;路由表的来源有哪些…

【笔记】常用 js 函数

数组去重 Array.from(new Set()) 对象合并 Object.assign . 这里有个细节&#xff1a;当两个对象中含有key相同value不同时&#xff0c;会以 后面对象的key&#xff1a;value为准 保留小数点后几位 toFixed 注意&#xff1a; Number型&#xff0c;用该方法处理完&#xff0c;会…

前端开发之Element Plus的分页组件el-pagination显示英文转变为中文

前言 在使用element的时候分页提示语句是中文的到了element-plus中式英文的&#xff0c;本文讲解的就是怎样将英文转变为中文 效果图 解决方案 如果你的element-plus版本为2.2.29以下的 import { createApp } from vue import App from ./App.vue import ElementPlus from …

react css 污染解决方法

上代码 .m-nav-bar {background: #171a21;.content {height: 104px;margin: 0px auto;} }import React from "react"; import styles from ./css.module.scssexport default class NavBar extends React.Component<any, any> {constructor (props: any) {supe…

详解 SpringMVC 中获取请求参数

文章目录 1、通过ServletAPI获取2、通过控制器方法的形参获取请求参数3、[RequestParam ](/RequestParam )4、[RequestHeader ](/RequestHeader )5、[CookieValue ](/CookieValue )6、通过POJO获取请求参数7、解决获取请求参数的乱码问题总结 在Spring MVC中&#xff0c;获取请…

移动基站ip的工作原理

原理介绍 Basic Principle 先说一下概念&#xff0c;大家在不使用 WIFI 网络的时候&#xff0c;使用手机通过运营商提供的网络进行上网的时候&#xff0c;目前都是在用户端使用私有IP&#xff0c;然后对外做 NAT 转换&#xff0c;这样的情况就导致大家统一使用一些 IP 段进行访…

springmvc没有绿标,怎么配置tomcat插件运行?

一、添加插件后&#xff0c;刷新&#xff0c;自动从maven仓库下载tomcat插件 二、写好项目后&#xff0c;添加tomcat配置 三、即可点击绿标运行

数据结构day07(栈和队列)

今日任务 链式队列&#xff1a; head.h #ifndef __HEAD_H__ #define __HEAD_H__#include <stdio.h> #include <stdlib.h>typedef int datatype; typedef struct link_list{datatype data;struct link_list* next; }link,*linkp; typedef struct circulate_line_t…