完全二叉树,满二叉树,平衡二叉树,搜索二叉树,红黑树

满二叉树:

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点

完全二叉树:

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。如下图

满二叉树都是完全二叉树

完全二叉树依次填满直至满二叉树的阶段,每一个树都是完全二叉树

二叉搜索树

它是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

• 若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
• 若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

平衡二叉树定义(AVL)：

它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

红黑树

红黑树大值定义和平衡二叉树相同,但是具有以下几个特点

• 性质1. 节点是红色或黑色。
• 性质2. 根节点是黑色。
• 性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 详情点击参考链接https://www.jianshu.com/p/1bbb19156454

红黑树和平衡二叉树的区别

1.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。 2.平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。

红黑树颜色的作用

红黑树使用红黑二色进行“着色”，目的是利用颜色值作为二叉树的平衡对称性的检查，只要插入的节点“着色”满足红黑二色的规定，最短路径与最长路径不会相差的太远，红黑树的节点分布就能大体上达至均衡。