| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> 红黑树(全图解) -> 正文阅读 |
|
[数据结构与算法]红黑树(全图解) |
什么是红黑树?红黑树就是一种平衡二叉树,说它平衡的意思是它不会出现左子树与右子树的高度之差不会大于1,左子树和右子树保持一种平衡的关系。 5个性质:
如图:? ? 为什么红黑树能自平衡?红黑树自平衡靠的是三种操作:左旋、右旋、变色。 变色:节点的颜色由红变黑或由黑变红 左旋:以某个节点作为支点(旋转节点),其右子节点变为旋转节点的父节点,右子节点的左子节点变为旋转节点的右子节点,左子节点保持不变。 如图:? 右旋:以某个节点作为支点(旋转节点),其左子节点变为旋转节点的父节点,左子节点的右子节点变为旋转节点的左子节点,右子节点保持不变。? 如图: 红黑树查找?因为红黑树是一颗二叉平衡树,并且查找不会破坏树的平衡,所以查找跟二叉平衡树的查找无异:
?红黑树的插入插入操作包括两部分工作:
查找插入的父结点很简单,跟查找操作区别不大:
注意:插入节点,必须为红色,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。但如果插入结点是黑色,那么插入位置所在的子树黑色结点总是多1,必须做自平衡。 插入的情况有很多,下面将列举出来。 在开始每个情况的讲解前,我们还是先来约定下,如图:
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年3日历 | -2025/3/15 23:42:22- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |