首页
登录 | 注册

二叉查找树和二叉堆

A. 二叉查找树(Binary Search Tree),又称为有序二叉树,排序二叉树,满足以下性质:

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

2)若左子树不为空,左子树上节点值均小于根节点的值。

3)若右子树不为空,右子树上节点值均大于根节点的值。

  二叉查找树中对于目标节点的查找过程类似与有序数组的二分查找,并且查找次数不会超过树的深度。设节点数目为n,树的深度为h,假设树的每层都被塞满(第L层有2^L个节点,层数从1开始),则根据等比数列公式可得h=log(n+1)。即最好的情况下,二叉查找树的查找效率为O(log n)。当二叉查找树退化为单链表时,比如,只有右子树的情况,如下图所示,此时查找效率为O(n)。

二叉查找树和二叉堆

  总之,二叉查找树越是“矮胖”,也就是每层尽可能地被“塞满”(每个父节点均有两个子节点)时,查找效率越高。每层都被塞满时,查找效率最高,最高为O(log n)。当二叉查找树退化为单链表时,查找效率最低,最低为O(n)。

B. 为了解决二叉查找树退化为单链表时查找效率低下的问题,引入了平衡二叉树(AVL,人名)。平衡二叉树的性质如下:

  1)父节点的左右两棵子树的深度之差的绝对值不超过1。

  从平衡二叉树的性质可知,平衡二叉树就是避免了二叉查找树退化为单链表的极端情况。二叉查找树的查找、插入、删除较好时间复杂度是O(log n),最差是O(n)。二叉平衡树保证查找、插入、删除的时间复杂度稳定在O(log n)下。

C. 二叉树的一个应用是堆。介绍堆之前,首先需要了解完全二叉树和满二叉树。

1)满二叉树:二叉树的第i层节点数量为2^(i-1),则称此二叉树为满二叉树。

2)完全二叉树:设二叉树深度为h,前(h-1)层均被填满(每个父节点均有两个子节点),第h层从左至右,只有最右侧子树未被填满,则称此树为完全二叉树。

D. 堆通常可以看作为一棵树。这里的堆是数据结构中的堆而非内存模型中的堆。堆有两个形式:

1)堆中任意节点的值不大于(小于)其子节点的值。    不大于---最小堆   不小于---最大堆

2)堆是一棵完全树。

  二叉堆由一棵完全二叉树组成。堆的实现一般为数组形式。对于下标为i的节点,其父节点下标为floor((i-1)/2)(向下取整),左节点是2*i+1,右节点是2*i+2。一个最小二叉堆以及其数组实现如下所示。

二叉查找树和二叉堆

  将堆顶节点存储到数组第一个位置,然后根据公式,计算其左右节点的存储位置,依此类推。数组最后一个元素必是叶子节点。 

  最小二叉堆插入(入队):从完全二叉树的最后一层上,最右侧的子树开始,依据堆的第1个性质,通过不断向上向下调整插入元素的位置完成插入。初始状态下,在数组末尾加入待插入元素,在调整插入元素位置时,在数组中交换相关元素来体现。向上述最小二叉堆插入元素2的过程如下。

二叉查找树和二叉堆

  最小二叉堆的删除(出队):出队一定是删除堆结构中堆顶节点,也就是数组中第1个元素。出队时,将最右侧子树的最右侧节点(也就是数组中的最后一个元素)A移至堆顶节点,通过不断的向上、向下调整A的位置完成堆顶节点的删除。删除上述最小二叉堆的堆顶节点的过程如下。

二叉查找树和二叉堆

  可以使用堆实现优先队列和“堆排序”。堆的查找、插入、删除都稳定在O(log n),因为堆是一棵完全树,不会退化为单链表。

 

  二叉查找树是为了实现动态查找而设计的数据结构,它是面向查找操作的,在二叉排序树中查找一个结点的平均时间复杂度是O(log n);
  堆是为了实现排序而设计的一种数据结构,它不是面向查找操作的。



2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号