LLRB左倾红黑树

Left-leaning red-black BST 1.红黑树的一种定义： A BST such that: ・ No node has two red links connected to it.  没有任何一个节点同时和两条红链接相连。 ・ Every path from root to null link has the same number of black links.  任何空链接到根节点路径上的黑链接数相同。 ・ Red links lean left. 红链接均为左链接。 2.红黑树总是有等价的2-3树对应 抽象意义上的等价，实际红黑树的实现还是二叉树。 命题G:一棵大小为N的红黑树的高度不会超过 2lgN 难以理解  红黑树的最坏情况是它所对应的2-3树中构成最左边的路径结点全部都是3-结点而其余均为2-结点。 命题H:一棵大小为N的红黑树中，根节点到任意结点的平均路径长度为~1.00lgN An equivalent definition一种等价定义 "perfect black balance" 3.Insertion in a LLRB tree: Java implementation 插入一个新节点，默认颜色为红色 Same code for all cases. 需要做以下几种情况的翻转： ・Right child red, left child black:rotate left. ・Left child, left-left grandchild red: rotate right. ・Both children red:flip colors.

private Node put(Node h, Key key, Value val) { if (h == null) return new Node(key, val, RED); int cmp = key.compareTo(h.key); if (cmp < 0) h.left = put(h.left, key, val); else if (cmp > 0) h.right = put(h.right, key, val); else if (cmp == 0) h.val = val; if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); return h; } 注解：最坏情况下各种操作的时间复杂度依然可以保持在O(lgN) Exercise: 1.In the extreme case, the red-black BST has only blacks links. A red-black BST of height h with no red links has 1 + 2 + 4 + ... + 2^h = 2^(h+1) - 1 nodes 2. 插入元素，树的高度反而有可能会降低 Consider inserting N keys in descending order into an initially empty red-black BST. Then, after each insertion, the height of the tree either strictly increases or remains unchanged. //In general, there is no reason to except the height to be monotonically nondecreasing. As a counterexample, after inserting the keys 7, 6, 5, 4, 3 and 2 into an initially empty red-black BST, the height is 3; after inserting the key 1, the height decreases to 2.