TOC
二叉树
二叉树本身就是非常常见的一种数据结构了，对于这种数据结构当然有一些基本操作 增删改查最大最小等等，一个二叉树的的基本操作都和二叉树的高度成正比，如果一棵树为 AVL，即完全二叉树，那么他的时间成本就是θ（logn），而一颗线性树则为Θ（n^2），
一颗完全二叉树的高度 h 应该是logn + 1
书中提到一个我以前没有注意到的特征，用比较来从一个数组建立一颗二叉树，如果你用中序遍历他，就能获得排序结果。
以下是我的实现，其实完全没必要用 OOP
// 单个节点
class Node {
constructor(val) {
this.val = val
this.left = null
this.right = null
}
}
// 二叉树
class Tree {
constructor() {
this.root = null
}
insert(node, root = this.root) {
if (root === null) {
this.root = node
return
}
if (node.val <= root.val) {
if (root.left === null) {
root.left = node
return
} else {
this.insert(node, root.left)
}
}
if (node.val > root.val) {
if (root.right === null) {
root.right = node
return
} else {
this.insert(node, root.right)
}
}
}
}
// 中序遍历二叉树
const LDR = function(root) {
root.left && LDR(root.left)
console.log(root.val)
root.right && LDR(root.right)
}
const testArr = [5, 1, 66, 7, 89, 1, 2, 7, 4, 5, 1, 9, 2, 8]
let tree = new Tree()
testArr.forEach(i => tree.insert(new Node(i)))
LDR(tree.root)
其实，这种二叉树的插入时间与快排十分相似，Ω(nlgn) Θ(n^2)，他本身非常依赖于插入元素的顺序，越乱的数组插入的越快，相反，最慢情况其实就是当数组已经排序完成，这时候你将会得到一个一直往一个方向发展的线性列表。
那么为什么二叉树的排序和快排的性质如此接近呢？仔细思考就会发现，其实两者他们比较步骤是几乎一样的，只不过快排更倾向于将一个树和所有值相比较，而二叉树则是渐进式的。两者比较的步骤几乎相同，也会产生一颗一样的树，唯一的差别就是比较的顺序是不同的。
故技重施
既然我们已经了解了二叉树排序的基本性质，并且知道它本身和 quicksort 及其相似，那么我们就可以完全套用快速排序的增强方法来增强我们二叉树排序，没错，就是增加随机化机制，由于我们不能修改插入时的步骤，我们将会随机化元素的插入顺序，也就是每次从一个数组中随机取得一个值，并插入到二叉树之中。当然换个方式，先随机化排列一下原数组也是完全可以的。
const testArr = [5, 1, 66, 7, 89, 1, 2, 7, 4, 5, 1, 9, 2, 8]
let tree = new Tree()
testArr.forEach(i => {
let index = parseInt(Math.random() * (testArr.length - 1))
let item = testArr.splice(index, 1)[0]
tree.insert(item)
})
LDR(tree.root)
我们不难发现，对于一颗 BST（binary search tree）而言，其最佳高度就是 logn（完全平衡二叉树），最差情况为根号 n。为了最高的搜索效率，一颗尽可能平衡的二叉树是我们的最佳选择。
二叉树的数据结构形式
其实已经出现了很多方法来构建一颗相对而言比较平衡的树形数据结构，从而获得 logn 的操作时间，比如说 AVL,他的方法就是在树的基础之上加上旋转算法来平衡化整个结构。而这次我们要了解的，是红黑树。
红黑树
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在 1972 年由鲁道夫·贝尔发明的，他称之为”对称二叉 B 树”，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于 1978 年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 {\displaystyle {\text{O}}(\log n)} {\displaystyle {\text{O}}(\log n)}时间内做查找，插入和删除，这里的 {\displaystyle n} n 是树中元素的数目。- wiki
所谓红黑树，就是他的节点是拥有颜色或者说类型的，红节点，黑节点。
红黑树的基本规则
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是 NIL 节点）
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
让我们梳理一下，首先，所有的叶节点都是一个 null 指针，本身内容为空，但我们将它视为一个哨兵，并且其颜色为黑色。其次，所谓的从任一节点到叶节点过程中包含的黑色节点树我们称之为黑高（bh(x)）
一颗红黑树的极限可能高度是2logn(n + 1)，也就是说相比于一颗真正意义上的完美二叉树，红黑树的最差高度也只可能是完美二叉树 log(n + 1)的两倍，看上去很不错。
操作红黑树
其实一颗红黑树真正的难点就在于更新，插入，删除等操作，你的所有操作都必须维持上面的基本特性。一旦破坏他的基本特性，那么他就不能稳定给你带来O(logn)的操作时间。
红黑树的基本操作可以被大致认为有三种
- 上色
- 给周围的节点重新上色
- 旋转
旋转拥有两种情况，左旋，右旋。
左旋的准确定义：对节点 X 和他的的右子树进行左旋操作，使其 X 的右子节点成为 X 的父节点 右旋的准确定义：对节点 X 和他的左子树进行右旋操作，使其 X 的左子节点成为 X 的父节点
无论是左旋还是右旋，肯定是将进行旋转的节点和他的左右子树进行替换，把他换到下面去。
以上的图片有错误，本身情况 2 是为了情况 3 而服务的，只要进去情况 2 则肯定会进去情况 3，情况 2 做的操作目的是为了让他自身与祖父节点形成一条直线。 以上就是左旋和右旋的基本逻辑，要注意观察的就是，旋转的目的在于保证 BST 基本性质不变的情况下能够去调换节点的位置。所以他在旋转过后其子节点左边小右边大的特性的保持不变的。
红黑树的插入
红黑树的最大的难点就在于，要维持性质，而维持性质就意味着我们需要不断的修改整颗树，修改就意味着进一步的破坏性质，为了达到最终的统一，我们需要将冲突不断的从下往上递交，直到递交到最终的根节点，以下是红黑树插入的伪代码
case 4 5 6 与 123 正好相反