二叉树相关

:由唯一的起始节点(root)引出n个节点所构成的有限集合。每个节点都可能有若干分支,由此形成了一种层次化的结构。

二叉树:对于树中的每个节点而言,最多有左右两个子节点(节点有左右之分),即:任意节点的度最大为2

  • 二叉树的第n层最多有2的n-1方个节点。
  • 高度为n(规定仅有根节点的树高度为0)的二叉树最多有2的n+1次方-1个节点。

满二叉树:“圆满”的二叉树,树中的所有节点,除叶子以外,其余节点的度都是2。一个节点只有作为叶子,或者度为2的节点时才算是”圆满“的。

  • 同样高度的二叉树中,满二叉数的节点数是最多的,没有任何残缺。

完全二叉树:只有最高层和次高层的节点的度可以小于2,且最高层的节点均集中在左侧连续位置上,期间不能出现空位

  • 同样节点数的二叉树,完全二叉树的高度最小。因为有了节点,必须先考虑去补左边的空位,不能只用于向下生长。

二叉查找树(Binary Search Tree,BST):对于BST中的任意节点,都存储了一个key,这个key值一定比其左子树的所有节点的key值都大,比其右子树的所有节点的key值都小。基于这种规则生长的树,同时完成了对key的排序。

例:以无序数列{ 5, 7, 1, 6, 3, 2, 9, 4, 10, 8 }作为key存入一个普通BST中。操作细节,参考: 《普通BST的基本操作过程》

  • 先根序遍历:5, 1, 3, 2, 4, 7, 6, 9, 8, 10
  • 中根序遍历:1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  • 后根序遍历:2, 4, 3, 1, 6, 8, 10, 9, 7, 5

中根序遍历将得到升序序列。

2-3查找树:它是一种平衡树(B-tree)。与二叉查找树不同,该树中可能存在两种类型的节点,一是常规节点,这里叫“2-节点”,保存一对key-value和两个指针;另一种是“3-节点”,保存两对key-value和三个指针。

二叉查找树在查找、插入和删除操作上的表现优于顺序表和链表的前提是树是平衡(根节点到所有叶子节点的路径长度之间的差值不超过1)的,最好是完美平衡(根节点到所有叶子节点的路径长度都相同)的。平衡的树抑制了树本身的高度,保障了树的操作效率。

  • Insert:O(lgN)
  • Delete:O(lgN)
  • Search:O(lgN)

多数的二叉查找树的形状类似于上图,就算达不到完美平衡,也不至于太极端。不过,向树中插入何种数据是使用者的行为,没法控制。如果插入的key本身是有序的,那么将得到一个“斜树”,此时的树最高,这是最坏情况,二叉查找树退化为线性结构。这种二叉查找树就没有优势了。

  • Insert:O(N)
  • Delete:O(N)
  • Search:O(N)

二叉查找树自身应具备一种维持平衡的特性以保证操作的高效性。2-3查找树是一种维持二叉查找树平衡的方案,它在二叉查找树中引入了3-节点以及自己一套操作逻辑,参考: 《2-3查找树的基本操作过程》 。简单的说,2-3查找树使用3-节点放缓了树的长高,每当有新的key-value对要插入树中时,它首先会与一个2-节点结合成一个3-节点,如果存在符合条件的2-节点的话。这样新插入的key-value对不会在新的一层存在,而是会与其双亲节点共处一层,且在同一个节点内。当该节点会变成4-节点的时候,就会执行2-3树的逻辑,对节点进行拆分,这个拆分操作维护了树的平衡性。在进行拆分的时候,树是有可能长高的,2-3树的生长方向正好与普通的BST生长方向相反。

3-节点用两个key分隔除了三个区间。

  • Insert:O(lgN)
  • Delete:O(lgN)
  • Search:O(lgN)

红黑二叉查找树(Red-Black BST tree):它是对2-3查找树的一种具体实现。通过对BST的链接或节点增加颜色属性,实现了对2-3树的描述。

按照正常的做法,实现2-3树肯定要定义一个用来描述整体的结构,然后还要定义节点结构,由于2-3树种存在两种节点,所以要定义两种。如果是按照这个思路去实现2-3树的话,可能会比较繁琐。首先,2-3查找树是基于二叉查找树的,大部分操作是可以互通的,以这种思路去实现,就是把2-3查找树完全当成了另外一种新的结构,不能复用二叉查找树的实现;其次,定义了新的数据类型:3-节点,可以想到,2-节点与3-节点之间肯定会发生很多交流,在两种不同的结构之间进行操作,势必会产生一些麻烦。

红黑二叉查找树实际是摒弃了上面这种做法,直接基于BST去实现。在BST的链接或节点中增加一些属性而非定义新的节点类型,以此即可完成对2-3树的描述。

有关红黑二叉查找树的操作演示,见: 《红黑BST的基本操作过程》