上一篇《TypeScript数据结构与算法：AVL树》实现了Typescript中自平衡的AVL树的数据结构与算法，本篇继续进一步实现性能更加优秀的红黑树(red–blacktree)。
虽然AVL树已经实现了二叉搜索树的平衡，但是由于每次添加和删除节点时都会涉及到再平衡操作，所以会比较复杂费时。所以在工业级应用中，都会用另一种近似平衡树算法红黑树来实现。
这次断更很长时间，就是因为红黑树花费我了大量的时间来学习和理解。这是至今为止遇到的最难写的数据结构的代码，虽然现在理解了原理，但是让我离线手写我仍然写不出来。而且红黑树和其他数据结构有个最大的区别：普通的数据结构都是设计出来的，但是红黑树是由2-3树``推导出来的数学模型。
具体的推导过程我就不把经典复述一遍了，感兴趣的同学可以看《算法第四版》的页到页，详细讲述了2-3树如何实现自平衡以及如何把2-3树映射成等价的左倾红黑树。值得一提的是，该书的作者RobertSedgewick正是红黑树的发明者。学习完之后有几个深刻体会：
对于2-3树等价的红黑树来说，由于2-3树的三叉节点被变为了3个二叉节点树，所以红黑树中的红颜色就代表着这里是2-3树中的三叉节点。AVL树的高度接近log?N；对于2-3树来说，由于节点可以为二叉或三叉，所以平衡后高度不会超过log?N，也不会低于log?N；而对于2-3树等价的红黑树来说，由于三叉节点被变为了2层，所以平衡后高度不会超过2log?N。很关键的一点，只要看见红黑树的红色节点（链接），别把它当成子节点，把它抻平，就能理解2-3树和左倾红黑树的对应关系，如下图所示：另外，左倾红黑树还有另外一些推导出来的性质：
红链接均为左链接；没有任何一个节点同时和两条红链接相连（也就是说红色节点不能相邻或者为兄弟节点）；该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同（也就是说把红色抻平后，各个叶子节点的高度相差不会超过1）。具体的红黑树的算法实现过程我就不赘述了，按照我的理解把算法第四版的左倾红黑树TypeScript代码实现如下：
红黑树代码节点类红黑树节点类RedBlackNode继承自之前实现的二叉搜索树的节点类Node：
import{Node}from"./node";//节点颜色枚举值exportenumColors{RED=0,BLACK=1}//红黑树节点，继承自普通NodeexportclassRedBlackNodeKextendsNodeK{left:RedBlackNodeK;right:RedBlackNodeK;//红黑树节点有color特殊属性color:Colors;constructor(publickey:K){super(key);//节点的默认颜色为红色this.color=Colors.RED;}/***
description:返回节点是否为红色*/isRed():boolean{returnthis.color===Colors.RED;}/***description:位运算反转节点的颜色*/flipColor(){this.color=1^this.color;}}红黑树类同样，红黑树类RedBlackTree也继承自之前实现的二叉搜索树类BinarySearchTree。在实现RedBlackTree的代码时，参照的算法四中已经实现的红黑树类的JAVA代码。
import{defaultCompare,ICompareFunction,Compare}from"../util";importBinarySearchTreefrom"./binary-search-tree";import{RedBlackNode,Colors}from"./models/red-black-node";exportdefaultclassRedBlackTreeTextendsBinarySearchTreeT{protectedroot:RedBlackNodeT;constructor(protected