Question

1.定义与性质

（1）定义

红黑树字义：满足(a) 每个结点或是红的，或是黑的(b) 根结点是黑的(c) 每个叶结点（NIL）是黑的(d) 如果一个结点是红的，则它的两个儿子是黑的(e) 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点的二叉查找树称为红黑树。

黑高度定义：从某个结点 x 出发（不包括该结点）到达一个叶结点的任意一条路径上的黑色结点的个数称为 x 的黑高度。

（2）性质

红黑树确保没有一条路径会比其它路径长出两倍。

一棵有 n 个内结点的红黑树的高度至多为 2lg(n+1)

2.结构

（1）红黑树结点结构

struct node
{
  node *left;
  node *right;
  node *p;
  int key;
  bool color;
};

（2）红黑树结构

struct Red_Black_Tree
{
  node *root;//根结点
  node *nil;//哨兵
};

3.红黑树上的操作

SEARCH

PREDECESSOR

MINIMUM

MAXIMUM

INSERT

DELETE