您当前的位置: 首页 >  搜索

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【数据结构与算法】二叉堆与二叉搜索树的区别

星拱北辰 发布时间:2020-02-18 09:52:26 ,浏览量:0

问题描述

记得刚学习数据结构的时候,就容易混淆二叉堆和二叉搜索树,其实虽说堆也是一种完全二叉树,但二者差别还是挺大的,本文试做分析。

逻辑结构

二叉堆和二叉搜索树都是结点带权重,并在父子结点间满足某种规则的数据结构。

二叉堆是一种完全二叉树,分大根堆、小根堆两种,子结点总是大于或小于父结点。 大根堆,顾名思义,根是最大的,每个子结点都要小于父结点,不区分左右儿子谁大谁小,也不必保证某个“孙子结点”一定要小于另一个“儿子结点”。 小根堆恰恰相反,根是最小的,每个子结点都要大于父结点,不区分左右儿子谁大谁小,也不必保证某个“孙子结点”一定要大于另一个“儿子结点”。

二叉搜索树是一种特殊的二叉树,左儿子结点小于父结点,右儿子结点大于父结点。 所谓的AVL树、红黑树等复杂一些的树状数据结构,很多都是二叉搜索树优化得到的。

存储结构

二叉堆和二叉搜索树看似都是“树”,实则在存储结构上差别很大。

我们也知道,顺序存储和链接存储是两种基本的存储结构。顺序存储减少了指针等的额外空间浪费,没有结点这个问题,却在某个元素的增删后的调整上很麻烦,且必须在内存中连续分配;链接存储反是。

由于二叉堆是一种完全二叉树,所以可以按照 id 编号,通过数组存取,更好的是用顺序表(Java党参考java.util.ArrayList,C++党参考STL-vecter),根据 id 访问父结点或子结点,既节约了指针空间的结构性开销,也

关注
打赏
1660750074
查看更多评论
立即登录/注册

微信扫码登录

0.0428s