树，有二叉树、二叉查找树、平衡树、平衡二叉树、红黑树等等。本文分别罗列每种树的原理及使用案例，深入了解『树』这一数据结构

一、树

1. 定义

   树（树状图）是一种数据结构 (opens new window)，它是由n（n>=1）个有限结点组成一个具有层次关系的集合 (opens new window)。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

2. 特点：

   1. 每个结点有零个或多个子结点；
   2. 没有父结点的结点称为根结点；
   3. 每一个非根结点有且只有一个父结点；
   4. 除了根结点外，每个子结点可以分为多个不相交的子树；

二、二叉树

1. 定义

   二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

2. 满二叉树和完全二叉树

   • 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。
   • 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

三、二叉查找树（二叉搜索树，二叉排序树）

1. 定义

   二叉查找树又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

   1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

   2) 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

   3) 左、右子树也分别为二叉排序树；

   4) 没有键值相等的节点。

2. 性质

   对二叉查找树进行中序遍历，即可得到有序的数列。它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。二叉查找树的高度决定了二叉查找树的查找效率。

四、平衡二叉树（AVL树）

1. 定义

   平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。

   最小二叉平衡树的节点的公式如下：

   • F(n)=F(n-1)+F(n-2)+1

   这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

   

   

2. AVL树

六、红黑树：

• 变换操作：

  1. 变色： 黑 -> 红， 红 -> 黑
  2. 左旋：
  3. 右旋：

• 变换规则： 旋转和颜色变化规则： 所有插入点默认为红色

  1. 变颜色的情况：当前结点的父亲是红色，且它的祖父结点的另一个子结点（即叔叔结点）也是红色：
     1. 把父结点设为黑色；
     2. 把叔叔结点也设为黑色；
     3. 把祖父结点设为红色；
     4. 把当前要操作的指针定义到祖父结点；
     5. 分析祖父结点变换规则；
  2. 左旋： 当前父结点是红色，叔叔是黑色，且当前结点是右子树时，以父结点为根进行左旋
  3. 右旋： 当前父结点是红色，叔叔是黑色，且当前结点是左子树时：
     1. 把父结点变为黑色；
     2. 把祖父结点变为红色；
     3. 以祖父结点作为根进行右旋；