红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
而树的内容又以二叉树作为重点，先来复习一下基础知识
BST树:
二叉搜索树(Binary Search Tree，简写BST)，又称为二叉排序树，属于树的一种，通过二叉树将数据组织起来，树的每个节点都包含了健值key、数据值data、左子节点指针、右子节点指针。其中健值key是最核心的部分，它的值决定了树的组织形状;数据值data是该节点对应的数据，有些场景可以忽略，举个例子，key为身份证号而data为人名，通过身份证号找人名;左子节点指针指向左子节点;右子节点指针指向右子节点。
特点:
-
左右子树也分别是二叉搜索树。
-
左子树的所有节点key值都小于它的根节点的key值。右子树的所有节点key值都大于他的根节点的key值。二叉搜索树可以为一棵空树。
-
一般来说，树中的每个节点的 key值都不相等，但根据需要也可以将相同的key值插入树中。
AVL树:
AVL树，也称平衡二叉搜索树，AVL是其发明者姓名简写。AVL树属于树的一种，而且它也是一棵二叉搜索树，不同的是他通过一定机制能保证二叉搜索树的平衡，平衡的二叉搜索树的查询效率更高。
特点:
-
AVL树是一棵二叉搜索树。
-
AVL树的左右子节点也是AVL树。
-
AVL树拥有二叉搜索树的所有基本特点。
-
每个节点的左右子节点的高度之差的绝对值最多为1，即平衡因子为范围为[-1,1]。
还有一个就是今天我们讨论的重点：红黑树，我们就来看一下
红黑(Red-black)树
是一种自平衡二叉查找树，1972年由Rudolf Bayer发明，它与AVL树类似，都在插入和删除操作时能通过旋转操作保持二叉查找树的平衡，以便能获得高效的查找性能。它可以在O(logn)时间内做查找，插入和删除等操作。红黑树是2-3-4树的一种等同，但有些红黑树设定只能左边是红树，这种情况就是2-3树的一种等同了。对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
特点:
-
节点是红色或黑色。根节点是黑色。
-
每个叶节点(NIL节点)是黑色的。
-
每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
-
最长路径不超过最短路径的2倍。