二叉排序树BST与堆的区别 |
您所在的位置:网站首页 › bsi和bsm的区别 › 二叉排序树BST与堆的区别 |
原文出处:https://blog.csdn.net/UP19910522/article/details/49945785 在二叉排序树中,每个结点的值均大于其左子树上所有结点的值,小于其右子树上所有结点的值,对二叉排序树进行中序遍历得到一个有序序列。所以,二叉排序树是结点之间满足一定次序关系的二叉树。堆是一个完全二叉树,并且每个结点的值都大于或等于其左右孩子结点的值(这里的讨论以大根堆为例),所以,堆是结点之间满足一定次序关系的完全二叉树。
具有n个结点的二叉排序树,其深度取决于给定集合的初始排列顺序,最好情况下其深度为log n,最坏情况下其深度为n; 具有n个结点的堆,其深度即为堆所对应的完全二叉树的深度log n 。
在二叉排序树中,最小值结点是最左下结点,其左指针为空;最大值结点是最右下结点,其右指针为空。在大根堆中,最小值结点位于某个叶子结点,而最大值结点是大根堆的堆顶(即根结点,数组的首元素)。
二叉排序树是为了实现动态查找而设计的数据结构,它是面向查找操作的,在二叉排序树中查找一个结点的平均时间复杂度是O(log n); 堆是为了实现排序而设计的一种数据结构,它不是面向查找操作的,因而在堆中查找一个结点需要进行遍历,其平均时间复杂度是O(n)。 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |