https://www.cnblogs.com/yyxt/p/4983967.html

树的基本概念

1. 树的导览

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

红黑树

性质：
（1）每个结点要么是红的要么是黑的。

（2）根结点是黑的。
（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
（4）如果一个结点是红的，那么它的两个儿子都是黑的。
（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。