BST(2) - RB(1) - 左偏红黑树

基本概念

LLRB 是特化后的红黑树，基本来源是一个 2008年 Robert Sedgewick （原始红黑树的两位联合发明人之一）的教学 PPT ，和红黑树一样，基本也不太行，实现复杂，不直观，而且删除操作使用了假交换，很不体面。

LLRB 名气很大，但是基本上也找不到什么介绍资料，大家抄得都是来自原作者的同一份 Slide 。而且它在代码上如果不使用递归版本，那几乎就是红黑树代码，与其说它是红黑树的变种，不如说它还是红黑树本身。

一般说它的节点颜色指得是节点的父链接的颜色，但这种定义只是为了方便与2-4树的实现做对比。从代码实现角度，仍然看作节点本身的颜色是一点儿问题都没有！

左偏指得是3-节点的红连接只能在左边，也就是在黑父节点的孩子是一黑一红的时候，红节点只能在左边。当出现在右边的时候要左旋到左边。

实在是鸡肋，不太想花很长时间只是为了实现一个并不简单的递归版本的红黑树。

可以参考

1. OI-WIKI 上的中文介绍以及下面我的评论
2. Sedgewick Analysis of Algorithms meeting at Maresias (Apr 2008) 版本的 Slide

对比 RB ，LLRB的变化仅在于能提出一个递归实现的 插/删 版本，并且这个版本也简单不到哪儿去；

对于展开版本的实现，根本就不如 RB 。