红黑树简介

引用：https://www.cnblogs.com/yyxt/p/4983967.html

http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml

http://www.sohu.com/a/201923614_466939

https://www.cnblogs.com/slgkaifa/p/6780299.html

维基百科

 

1. 树的导览

1. 树由节点（Nodes）和 边（edges）构成。
2. 树有根节点（root），边（deges），父节点（parent），子节点（child），叶节点（leaf）。
3. 如果最多只允许两个子节点，即所谓的二叉树（binary tree）。
4. 不同的节点如果拥有相同的父节点，则彼此互为兄弟节点（siblings）。
5. 根节点至任何节点之间有唯一路径（path），路径所经过的边数，成为路径长度（length）。
6. 根节点至任一节点的路径长度，即所谓该节点的深度（depth）。
7. 根节点的深度永远是0。 整棵树的高度，便以根节点的高度来代表。
8. 某节点至其最深子节点（叶节点）的路径长度，成为该节点的高度（height）。
9. 节点A->B 之间如果存在（唯一）一条路径，那么A 称为B的祖代（ancestor），B称为A的子代（descendant）。任何节点的大小（size）是指其所有子代（包括自己）的节点总数。

2、二叉树

所谓二叉树（binary tree），其意义是：“任何节点最多只允许两个子节点”。

3、红黑树

红黑树是一个二叉树，是一个平衡二叉搜索树。

1.  左子树上所有的节点的值均小于或等于他的根节点的值
2.  右子数上所有的节点的值均大于或等于他的根节点的值
3. 根是黑色。
4. 其他节点是红色或黑色。
5. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
6. 如果一个结点是红的，那么它的两个儿子都是黑的。
7. 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。