二叉查找树和二叉堆 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)； 堆是为了实现排序而设计的一种数据结构，它不是面向查找操作的。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/86065.html
