什么是树？树是一种特殊的图，不包含回路的连通无向树。
正因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。
一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点，那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。一棵树有且只有一个根结点。
没有父结点的结点称为根结点（祖先）。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶结点，称为内部结点。二叉树是一种特殊的树。二叉树的特点是每个结点最多有两个儿子，左边的叫做左儿子，右边的叫做右儿子，或者说每个结点最多只有两棵子树。
严格的递归定义：二叉树要么为空，要么由根结点、左子树和右子树组成，而左子树和右子树分别是一棵二叉树。
有两种特殊的二叉树：
如果二叉树中每个内部结点都有两个儿子，这样的二叉树叫做满二叉树。一棵深度为h且有(2^h)-1个结点的二叉树。如果一棵二叉树除了最右边位置上有一个或者几个叶结点缺少外，其他都是丰满的，那么这样的二叉树叫做完全二叉树。若设二叉树的高度为h，除了第h层外，其他各层（1~h-1）的结点数都达到最大个数，第h层从右向左连续缺若干结点。满二叉树是一种特殊的或者极其完美的完全二叉树。
一种特殊的完全二叉树。
如果所有父结点比子结点小，称为最小堆。如果所有父结点比子节点大，称为最大堆。防止单链查找树的出现。
结点是红色或者黑色根结点是黑色每个叶子结点都是黑色的空结点（NULL）每个红色结点的两个子结点都是黑色的从任意结点到其每个叶子节点的所有路径都包含相同的黑色节点。通过变色和旋转（左、右）调整和维持红黑树平衡。
为了重新符合红黑树的规则，尝试把红色结点变为黑色，或者把黑色结点变为红色。
逆时针旋转红黑树的两个结点，使得父结点被自己的右孩子取代，而自己成为自己的左孩子。
顺时针旋转红黑树的两个结点，使得父结点被自己的左孩子取代，而自己成为自己的右孩子
