满二叉树

满二叉树有如下特点：

• 除最后一层无任何子节点 (opens new window)外，每一层上的所有结点都有两个子结点。

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

完全二叉树

若设二叉树的深度为k，除第k层外，其他各层（1～（k-1）层）的节点数都达到最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树。

二叉查找树

二叉查找树又叫二叉搜索树。主要特点如下，

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 左、右子树也分别为搜索二叉树；
• 没有键值相等的结点。

基于二叉查找树的这种特点(左小右大)，我们在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。

这种情况也是满足二叉查找树的条件，然而，此时的二叉查找树已经近似退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，可想而知，我们必须不能让这种情况发生，为了解决这个问题，于是我们引申出了平衡二叉树。

平衡二叉树

平衡二叉树有如下特点：

• 非叶子节点最多拥有两个子节点；
• 非叶子节值大于左边子节点、小于右边子节点；
• 树的左右两边的层级数相差不会大于1;
• 没有值相等重复的节点;

平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。于是，通过平衡树，我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。

红黑树

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点：

• 具有二叉查找树的特点;
• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据;
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的;
• 每个节点，从该节点到达其可达的叶子节点是所有路径，包含相同数目的黑色节点;