本文主要讲解一下最近听说的红黑树，看看是什么鬼神。图片来自Pexels二叉树满足以下两个条件的树就是二叉树：是有序树（如果把树中每个节点的子树都看成是从左到右有序的（即不能互换），则这棵树称为有序树）。树中包含的每个节点的度数不能超过2，即只能为0、1或2。简单理解，二叉树是一种树结构，每个节点最多有两个分支（即有没有分支度大于2)的节点。通常分支被称为“左子树”或“右子树”。二叉搜索树在了解红黑树之前，免不了先了解一下什么是二叉搜索树。维基百科上的定义：二叉搜索树（英文：BinarySearchTree），又称二叉搜索树、有序二叉树（orderedbinarytree）或排序二叉树（sortedbinarytree），是指一棵空树或一棵具有的二叉树以下属性。如果任一节点的左子树不为空，则左子树上所有节点的值都小于其根节点的值；如果任一节点的右子树不为空，则右子树上所有节点的值都大于或等于其根节点的值；任何节点的左子树和右子树也是二叉搜索树。图解理解：上图为查找值为29的节点，步骤如下：查根节点41，由于41>29，看41的左孩子20，因为20<29，查20、29的右孩子，发现正好是要检查的节点。退化的二叉搜索树存在一个非常严重的问题。如果数据从大到小，或者从小到大插入，都会导致二叉搜索树退化为单链表，俗称“压接”。左跛：比如插入的数据是{5,4,3,2,1}（从大到小），如下图：右跛：比如插入的数据是{1,2,3,4,5}（从小到大），如下图所示：为了解决这个问题，有一些解决方案，就是balance，可以让树趋于平衡。这种自平衡树称为平衡树。一棵平衡树（BalanceTree，BT）是指任意节点的子树的高度差小于等于1。常见的平衡树有AVL树（二叉平衡搜索树）、B树（多路平衡搜索树）,2-3树,2-3-4树),红黑树等.AVL树AVL树（以发明人Adelson-Velsky和Landis的首字母缩写命名），是指任意节点的两棵子树的高度差不超过1的平衡树。也称为自平衡二叉搜索树。AVL树可以解决上述二叉搜索树中的右手问题。比如插入的数据是{1,2,3,4,5}（从小到大），如下图所示：AVL树不会调整符合高度差的结构，使得二进制树趋于平衡。2-3树2-3树指的是一棵自平衡树，每个子节点（internalnode，内部节点）要么有两个子节点和一个数据元素，要么有三个子节点和两个数据元素，它的所有叶子节点都有同样的高度。简单的说，2-3树的非叶子节点有两个叉或者三个叉，所以更容易理解为2-3叉树。也就是说，有两个子节点和一个数据元素的节点也称为2节点，有3个子节点和2个数据元素的节点也称为3节点，所以整棵树称为2-3树.所有的叶子点都在树的同一层级和同一高度：性质一：满足二叉搜索树的性质。属性2：一个节点可以存储一个或两个元素。属性3：每个节点都有两个或三个子节点。创建2-3树的常规插入操作如下：Insertanelementintoa2-node:Insertanelementintoatreecontainingone3-node:2-3-4树的含义如下：2个节点：包含两个子节点和一个数据元素。3节点：包含三个子节点和一个数据元素。4节点：包含四个子节点和一个数据元素。2-3-4树，它的每个非叶子节点要么是2个节点，要么是3个节点，要么是4个节点，并且可以自平衡，所以叫2-3-4树。规则如下：规则一：添加新节点时，该节点不会添加到空位置，而是添加到最后一个叶子节点。规则二：四个节点可以分解成一棵由三个2-节点组成的树，分解后的新树的根节点需要向上与父节点合并。插入原来的2-3-4树，如下图：对于上图中的2-3-4树，插入一个节点17，因为规则1，节点17不会加入节点[16,18,20]，而是与该节点融合。由于规则2，节点[16,17,18,20]是4-node，将节点拆成一棵新树，拆分18作为子树的根节点。这时候树暂时失去平衡，我们需要向上合并分裂子树的根节点。同理，由于规则2，节点[6,10,14,18]是一个4节点，将节点拆成一棵新树，并以14作为子树的根节点进行拆分，而2-3是完成-4树的构建。总结一下插入节点的过程，无非就是要遵守两个规则，那么，有2-3棵树，2-3-4棵树，是不是还有2-3-4-5棵树，2-3-4-5--...-n棵树的存在性如何？其实是有的，世人称这种树为一个名字：B-tree。B-treeB-tree表示一种树，它允许一个节点有两个以上的子节点。同时也是自平衡的，叶子节点的高度是一样的。因此，为了更好的区分一棵B-tree属于哪一类树，我们赋予它一个新的属性：Degree：一个节点可以指向其他节点的箭头数。度数为3的B树表示一个节点最多有三个子节点，这是2-3树的定义。度为4的B树表示一个节点最多有四个子节点，这是2-3-4树的定义。图4的B树实例：红黑树R-BTree，全称Red-BlackTree，又名“红黑树”，是一种特殊的二叉搜索树。红黑树的每个节点都有一个存储位表示该节点的颜色，可以是红色（Red）或黑色（Black）。如何理解红黑树经典的红黑树，如下图（省略了叶子节点全黑的NIL节点）：如第二张图所示，将红黑树与2-3-4树比较，是否找到，红黑树是2-3-4树：每个节点要么是黑色要么是红色。根节点是黑色的。每个叶节点(NIL)都是黑色的。注意：这里的叶子节点是指为空（NIL或NULL）的叶子节点！如果一个节点是红色的，它的子节点必须是黑色的。由于红黑树的每个节点都是由2-3-4树转化而来，所以两个红色节点不能连续出现，否则会有4个节点，违反了规则2。而红黑树的每个黑色节点是3个节点中最中间的值，或者2个节点中的其中一个值。从一个节点到其后代的所有路径都包含相同数量的黑色节点。原因：2-3-4树中红黑树的黑色节点代表一棵有1个节点的2-3-4树，2-3-4树是同一子树，深度相同，平衡，所以从一个节点到它的后代的所有路径都包含相同数量的黑色节点。如下图，蓝色代表黑色节点：注意以下几点：特征（3）中的叶节点只是空（NIL或null）节点。属性(5)确保没有路径是其他路径的两倍。因此，红黑树是一种比较接近平衡的二叉树。红黑树虽然本质上是一颗二叉搜索树，但是它在二叉搜索树的基础上增加了着色和相关属性，使得红黑树相对平衡，从而保证了红黑树的查找、插入和删除。blacktree时间复杂度最差是O(logn)。如上例所示，我们只需要将红黑树看成一棵2-3-4树，改变对应的颜色或者进行左手和右手操作就可以达到使红黑树成为红黑树的目的。黑树平衡。如何维护红黑树的结构当我们插入一个新的节点时，如何保证红黑树的结构仍然能够满足以上五个特征呢？树的旋转分为左旋和右旋。下面我们就借助下图分别介绍左手和右手操作。①左旋的原始状态：过程图：结束图：如上图所示，当对某个目标节点E进行左旋操作时，我们假设其右孩子S不为NIL。Left-handing以S到E的链为“枢轴”，使S成为子树的新根，S的左孩子成为E的右孩子。②右手原始状态图：过程图：结束图：与左手类似，当对某个目标节点S进行右手操作时，我们假设其右子节点S不为NIL。Left-handing以S到E的链为“枢轴”，使S成为子树的新根，S的左孩子成为E的右孩子。红黑树的应用广泛，主要存储有序数据，其时间复杂度为O(logn)，效率非常高。比如Java集合中的TreeSet和TreeMap，C++STL中的set和map，Linux的虚拟内存管理都是通过红黑树实现的。作者：海马编辑：陶家龙来源：https://www.cnblogs.com/linzworld/p/13720477.html
