红黑树
红黑树(Red-Black Tree)1972年德国学者R.Bayer提出平衡二叉B树,1978年Leo J. Guibas和Robert Sedgewick将其重新表述为更容易描述和实现的红黑树。红黑树基本是目前最流行的自平衡二叉树,很多程序语言的数据类型、操作系统的算法都是基于红黑树的。下面先定义松弛红黑树(relaxed red-black tree),然后在松弛红黑树的基础上定义红黑树:
1) 松弛红黑树节点:额外包含一个布尔值的BST节点。为方便称其表示红或黑,对应的节点为红节点或黑节点;
2) 松弛红黑树:由松弛红黑树节点构成的BST,且满足如下性质:
2.1) 红节点如果有孩子,则孩子只能是黑节点;
2.2) 对于任意节点\(x\),从\(x\)到\(x\)子树的所有叶节点的路径中,黑节点数必须相同;
3)… 阅读全文