美文网首页
二叉排序树(查找树)

二叉排序树(查找树)

作者: Arya鑫 | 来源:发表于2017-08-23 15:11 被阅读41次

1.什么是二叉排序树呢?(Binary Sort Tree)

二叉排序树具有以下几个特点。

(1)若根节点有左子树,则左子树的所有节点都比根节点小(就是左子树结点要比双亲结点小)。

(2)若根节点有右子树,则右子树的所有节点都比根节点大(就是右子树结点要比双亲结点大)。

(3)根节点的左,右子树也分别为二叉排序树。


2.构造一棵二叉排序树的目的

其实并不是为了排序,而是为了提高查找和插入删除的效率。

下面是二叉排序树的图示,通过图可以加深对二叉排序树的理解。可以看到,根结点50的左边所有的子结点都比它小,根结点50的右边所有的子结点都比它大


3.下面是二叉排序树常见的操作及思路。

(1)插入节点(要先进行查找,查找结束后,没有,就在那个位置进行插入)

思路:比如我们要插入数字20到这棵二叉排序树中。那么步骤如下:

1)首先将20与根节点进行比较,发现比根节点小,所以继续与根节点的左子树30比较。

2) 发现20比30也要小,所以继续与30的左子树10进行比较。

3) 发现20比10要大,所以就将20插入到10的右子树中。

(2)查找节点(递归)

比如我们要查找节点10,那么思路如下:

1) 还是一样,首先将10与根节点50进行比较大小,发现比根节点要小,所以继续与根节点的左子树30进行比较。

2) 发现10比左子树30要小,所以继续与30的左子树10进行比较。

3) 发现两值相等,即查找成功,返回10的位置。

(3)删除节点(不能因为删除了结点,而让这棵树变得不满足二叉树的特性)

删除节点的情况相对复杂,主要分以下三种情形:

1) 删除的是叶节点(即没有孩子节点的)。比如20,删除它不会破坏原来树的结构,最简单。如图所示。

2) 删除的是单孩子节点。比如90,删除它后需要将它的孩子节点与自己的父节点相连。情形比第一种复杂一些。

3) 删除的是有左右孩子的节点。

这种情况会稍微复杂一些,我们采用覆盖,再删除的方式进行解决。也就是曲线解决。直接将有左子树也有右子树的结点干掉似乎不是很好实现,因为这样会破坏二叉排序树的结果。我们可以间接的去做。可以分为下方的两步。

第一步:查找删除结点右子树中最小的那个值,也就是右子树中位于最左方的那个结点。然后将这个结点的值的父节点记录下来。并且将该节点的值赋给我们要删除的结点。也就是覆盖。

第二步:然后将右子树中最小的那个结点进行删除,该节点肯定符合上述三种情况的某一种情况,所以可以使用上述的方法进行删除。


四、二叉排序树与堆的区别

在二叉排序树中,每个结点的值均大于其左子树上所有结点的值,小于其右子树上所有结点的值,对二叉排序树进行中序遍历得到一个有序序列。所以,二叉排序树是结点之间满足一定次序关系的二叉树

堆是一个完全二叉树,并且每个结点的值都大于或等于其左右孩子结点的值(这里的讨论以大根堆为例),所以,堆是结点之间满足一定次序关系的完全二叉树。

具有n个结点的二叉排序树,其深度取决于给定集合的初始排列顺序,最好情况下其深度为log n(表示以2为底的对数),最坏情况下其深度为n;

具有n个结点的堆,其深度即为堆所对应的完全二叉树的深度log n 。

在二叉排序树中,某结点的右孩子结点的值一定大于该结点的左孩子结点的值;

在堆中却不一定,堆只是限定了某结点的值大于(或小于)其左右孩子结点的值,但没有限定左右孩子结点之间的大小关系。

在二叉排序树中,最小值结点是最左下结点,其左指针为空;最大值结点是最右下结点,其右指针为空。

在大根堆中,最小值结点位于某个叶子结点,而最大值结点是大根堆的堆顶(即根结点)。

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

堆是为了实现排序而设计的一种数据结构,它不是面向查找操作的,因而在堆中查找一个结点需要进行遍历,其平均时间复杂度是O(n)。


http://www.cnblogs.com/ludashi/p/6004024.html

http://blog.csdn.net/gisredevelopment/article/details/49945785

http://www.cnblogs.com/GumpYan/p/5754731.html

http://www.cppblog.com/guogangj/archive/2009/10/26/99502.html


相关文章

  • 数据结构题目59:二叉排序树的查找

    题目:二叉排序树的查找。解题思路:其查找过程是:若二叉排序树为空,则查找失败,结束查找,返回信息null;否则,将...

  • Binary Search Tree

    如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为 ,其查找效率为 ,近似于折半查找。如果二叉排序树完全不平衡...

  • 《数据结构与算法》知识点(四)

    第七章 查找 顺序查找、折半查找、索引查找、分块查找是静态查找,动态查找有二叉排序树查找,最优二叉树查找,键树查找...

  • 二叉排序树

    1、二叉树的二叉链表结点结构定义 2、二叉排序树--查找 递归查找二叉排序树T中,是否存在key;指针f指向T的双...

  • 【数据结构】二叉排序树(Binary Sort Tree)(建立

    二叉排序树定义 二叉排序树(Binary Sort Tree),又称二叉查找树。它是一颗空树,或者具有下列性质: ...

  • 二叉查找树

    一、二叉查找树(BTS) 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Searc...

  • 二叉排序树

    二叉排序树百度百科定义 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search...

  • 数据结构--查找

    查找分类 有序查找(二分查找、插值查找、斐波拉契查找) 线性索引查找 二叉排序树 散列表

  • 数据结构学习第四弹 二叉排序树

    二叉排序树又称为二叉搜索树或二叉查找树,这是一种插入、删除和检索记录效率都很高的树结构 二叉排序树概念 二叉排序树...

  • 查找

    静态查找顺序查找 折半查找 散列查找 动态查找二叉排序树 散列查找 ASL(平均查找长度) - 衡量查找算法效率的...

网友评论

      本文标题:二叉排序树(查找树)

      本文链接:https://www.haomeiwen.com/subject/yqwddxtx.html