树说-1

食之无味,弃之可惜。仍不知其所用,但无奈于八股。

树,就是一个非空的有限元素集合,其中一个元素为根(root),余下的元素组合成其 子树

每个元素称为节点,节点分 根节点叶子节点。每个节点的子树数目称为节点的

树中,结点的最大高度为此树的 高度 或者 深度

    A
   / \
  B   C
 / \  |\
D  E  F G

此树中A为根节点,DEFG为叶子节点,A的度为2,C的度为3,叶子节点的度为0。高度为3。

二叉树

每个节点的子树数目不多于2的树,称为二叉树。二叉树的子树分左右。其有以下性质:

  1. i层最多有2i-1个节点;

  2. 深度为k的二叉树最多有2k-1个节点;有2k-1个节点的树称为满二叉树;由满二叉树从右到左、从下到上地缺少节点,形成的树,称为完全二叉树。

  3. 对于任意二叉树,节点数为 n,叶子节点数为 n0,度为2的节点数为 n2,度为1的节点数 n3, 有: n = n0 + n1 + n2n = n1 + 2n2 + 1n0 = n2 + 1

  4. N个节点的二叉树,最大深度为N,最小深度为 log(N+1),即完全二叉树。log在此表示以2为底。

  5. n个节点的完全二叉树,从上到下、从左到右地进行编号 i = 1...n,有

    • i=1表示根节点;i>1时,此元素的父节点编号为 i/2 的取整;
    • 2i>n时,此元素无左孩子;否则,其左孩子编号为 2i;
    • 2i+1>n时,此元素无右孩子;否则,其右孩子编号为 2i+1;
    A
   / \
   B   C
  / \
  D E    二叉树
 /
F

    A
   / \
   B  C
  / \ |\
  D E F G   满二叉树

    A
   / \
   B  C
  / \
  D E     完全二叉树

最大堆/最小堆,两者都是完全二叉树。最大堆是指树中的任意节点大于或等于其孩子节点;最小堆反之。

    14
   / \
  10 12
  / \
  6 5 最大堆

    5
   / \
   6 10
  / \
 14 12 最小堆

初始化

最大堆的初始化。

堆首先是完全二叉树。对于任意的一组数据,按照顺序编号,可以看作是一个完全二叉树,但此树就不一定是堆。如果这组数据是存储于连续的空间,如线性表,那么其中父节点和相应的子节点,可以通过父节点编号=子节点编号/2(取整)得到节点之间的关系;如果是链表,还要额外地存储左右子节点和父节点的指针,当然将每个链节点的地址另存储为线性表,从而利用父节点编号=子节点编号/2(取整)公式。

所以,可以利用公式父节点编号=子节点编号/2(取整)减少程序的访问次数。最大堆需要每个子树的根都大于其左右子节点,那么可以从最后一个子树开始初始化。即,当完全二叉树的节点数为n,那么最后子树的根节点编号应该是 n/2。如此,从 n/2 到 1,不断地构造子树成为最大堆,从而整棵树就成为最大堆。 注意 ,这里的子树不仅仅指三个节点,而是某节点下方的子层,子子层等的所有节点。对于由于节点较小,需要下沉时,需要重新构造以下沉节点为根的子树。总的复杂度为O(nlogn),但实际效果要优于此。

如,

      10
     / \
     6  5
    /\  |\
  14 12 1 2   初始状态
  /
 8

      14
     / \
    12  5
    /\  |\
   8 10 1 2   结束
  /
  6

n=8,从8/2=4编号开始。编号4的节点值是14,以此节点为根的子树已经是最大堆了;然后到编号3,节点值是5,这也是最大堆了;编号2,节点值为6,此时需要与左右子节点最大的14进行交换,6下沉,下沉的6改变了以编号4为根的子树结构,所以需要重新构造子树成为堆,6继续下沉;编号1,值为10,小于编号2的14,10下沉,10小于12,下沉右节点。

插入

最大堆的插入操作。插入时,先将新的元素 模拟 放入n+1的位置,再与父节点比较,如果新的元素大于父节点的元素,将父节点元素下移,新元素插入的位置上移。按 n+1 的位置到根节点 这一路径,进行比较,当新的元素大于父节点的元素时,或者到根节点时,比较结束。最后新元素真正插入到相应的位置。由于高度最多是log(n+1),其操作的时间复杂度为O(logn)

1)
    14
   / \
  10 12
  / \
  6 5

2) x 为新元素的模拟初始位置
    14
    / \
   10 12
   / \ |
   6 5 x

3) 当新元素大于 12 时,
父节点元素12下移,新元素要插入的位置x上移
    14
    / \
   10 x
   / \ |
   6 5 12

4) 当新元素不大于父节点元素14时,
新元素才真正地插入到x的位置上。

删除

堆的删除通常指删除根节点中的元素。最大堆中,n的二叉树删除根节点元素后,节点数目会变为n-1。删除根元素后,根节点为空,模拟将原来的最后一个元素放到此根节点的位置上。然后,与此位置的左右孩子节点比较,取最大元素并将其上移,原来最后的元素模拟下移。如此循环,直到原来最后元素大于此位置上的左右孩子节点元素,真正把原来最后元素放入此位置上。由于高度最多是log(n+1),其操作的时间复杂度为O(logn)

1)
    14
   / \
   10 12
  / \
  6 5

2) x 为最后一个元素5的模拟初始位置
    x
   / \
  10 12
  /
 6

3) 把 5 与位置x的左右孩子节点中的元素比较,取最大的元素上移,x 位置下移
    12
   / \
   10 x
  / \
  6 5

4) 当原来最后的元素不小于其位置上的任意元素时,将最后的元素真正放入到x位置。

堆的应用

利用堆进行排序,时间复杂度为O(nlogn)。首先,将一组数据初始化为堆,需要的时间为O(nlogn),然后直接利用堆删除的操作,将根节点提取出来,时间复杂度为O(logn),总的时间为O(nlogn)。这比普通的两个循环的时间复杂度O(n2)要好。

Comments