R-B Tree，全程Red-Black Tree，中文译为红黑树。它是一种特殊的二叉查找树，它的每个节点上都有存储位表示节点的颜色，可以是红或者黑。
红黑树应用比较广泛，主要是用来存储有序的数据，它的时间复杂度为O（lgn），效率那是杠杠的高呀。
例如，Java集合中的TreeSet和TreeMap以及Linux虚拟内存的管理，就是通过红黑树来实现的。
红黑树的特点：
（1）每个节点为红或黑两种
（2）根节点为黑色
（3）每个叶子节点是黑色（注：这里的叶子节点，是指为空（NIL或NULL）的叶子节点！）
（4）如果一个节点是红色的，则它的子节点必须为黑色
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点（该特性确保没有一条路径会比其他路径长出俩倍，因而，红黑树是相对比较接近平衡的二叉树。）
示意图如下：
红黑树基本操作：
（1）添加：第一步，将红黑树当做一棵二叉查找树，将节点插入；第二步，将节点着色为红色；第三步，通过旋转和重新着色等方法来修正该树，使之重新成为一棵红黑树
旋转示意图：
（1）左旋转：
（2）右旋转：
红黑树概述 红黑树的插入 红黑树的删除
需要先了解红黑树，这是之前分析红黑树的文章。之前在分析红黑树时，我认为红黑树=二叉查找树+红黑平衡，关于二叉查找树...
AVL树AVL树 算法红黑树红黑树 B站
https://zhuanlan.zhihu.com/p/24367771红黑树简介红黑树插入红黑树删除
红黑树 红黑树、2-3树的简单定义: 实现红黑树的基本结构以及添加操作(维护定义，左旋、右旋、颜色反转) 红黑树与...
啥是红黑树，红黑树 = 二叉树
彻底理解红黑树（一）之 二叉搜索树彻底理解红黑树（二）之 插入彻底理解红黑树（三）之 删除 前言 红黑树的插入情况...
彻底理解红黑树（一）之 二叉搜索树彻底理解红黑树（二）之 插入彻底理解红黑树（三）之 删除 前言 红黑树的删除情况...
红黑树 红黑树是每个节点都带有颜色属性（红色或黑色）的二叉查找树。红黑树也属于自平衡二叉查找树。 红黑树具有如下性...
源码分析大纲 数据结构解析 红黑树试下原理刨析 数据结构解析 1.红黑树 1.1 红黑树概念 红黑树（Red Bl...
本文标题：红黑树
本文链接：https://www.haomeiwen.com/subject/wpzpdftx.html
网友评论