红黑树总结

2012-06-05

5个条件

  1. 结点要么是红色要么是黑色
  2. 根是黑色
  3. 叶子是黑色(空指针的也算作叶子)
  4. 红色结点的两个孩子都为黑
  5. 从根到叶子的每条路径出现的黑色结点数量相同

插入5种情况总结:

  1. 根为空
  2. pb 不必调整
  3. prur 改色 继续向上调整
  4. prub< 旋转,跳到第5步
  5. prub\ 改色 旋转
rbtree