一、今天完成的事情：

     昨天赵佬说看了的红黑二叉树，其实也只记得了为了解决普通二叉树生成不均衡的问题，别的也忘记的差不多了，今天重新补了一下知识点。

      红-黑二叉树的设计思想

     红-黑树的设计思想应该是，利用 红-黑这两种节点颜色来追踪二叉树的平衡状况， 重新着色(recolor)这个操作就是动态刷新各节点颜色，如果发现树开始出现不平衡状况，就使用 左旋(left rotate)或者右旋(right rotate)来改变树的结构。 把图(tree 2) 和(tree 3) 反过来看，它们都是不平衡树，对 (tree 2)进行右旋，或对(tree 4)进行左旋都能得到(tree 3)这样的平衡树。 左旋的实质是增加左树的高度而减少右树的高度，右旋反之。 这样交替运用这三个操作，我们就可以构建一颗平衡的二叉树。

红-黑二叉树的数据结构

  1)叶子节点(leaf child)，和 内部节点(internal node)

     红黑二叉树的每个节点都增加了2个指针，叫做 leaf child，它永远存在，而且永远都是 child，原二叉树节点，叫做 internal node。

  2) 左旋，右旋， 重新着色(recolor)

       左旋，右旋， 重新着色(recolor) 是红-黑二叉树的三个基本操作。

   3) 规则

      3.1) 根节点和 叶子节点(leaf child) 节点必须是黑节点， 内部节点(internal node)非黑即红。

      3.2) 从根节点开始到每条子路径的叶子节点(leaf child)，所有的黑节点数目相同。

      3.3)  红节点的父亲节点必须是黑节点。

我们用java来表示红黑树:

private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node {
   Key key;
   Value val;
   Node left, right;
   boolean color;// color of parent link
}

private boolean isRed(Node x) {
   if (x == null) return false;
   return x.color == RED;
}

其中左转是思想：

/* left rotate */
private Node rotateLeft(Node h) {
   assert isRed(h.right);
   Node x = h.right;
   h.right = x.left;
   x.left = h;
   x.color = h.color;
   h.color = RED;
   return x;
}

右转的思想：

/* right rotate */
private Node rotateRight(Node h) {
  assert isBlack(h.left);
  Node x = h.left;
  h.left= x.right;
  x.right= h;
  x.color = h.color;
  h.color = BLACK;
  return x;
}

关于查找和删除这些操作在文章里提到的很多：

http://blog.csdn.net/kartorz/article/details/8865997

http://blog.csdn.net/h3243212/article/details/52819734#red-black-bsts红黑树

可以多去看一看

二、遇到的问题：无

三、明天计划的事情：

四、收获：仔细想象以前设计大佬的的设计思想真的太厉害了。