文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 电脑基础知识 > 二叉查找树
侵权投诉

二叉查找树

二叉查找树

一、二叉查找树:

查找树是一种数据结构,它支持多种动态集合操作,包括search,minimum,maximum,predecessor,successor,insert以及delete。

在二叉查找树上执行的基本操作时间与树的高度成正比。对于一棵含有n个结点的完全二叉树,这些操作的时间复杂度为O(log2n)。但是,如果树是含有n个结点的线性链,则这些操作的最坏情况下的运行时间为O(n)。

(一)二叉查找树的概念:

二叉查找树(BST,Binary Search Tree)又称二叉排序树或二叉搜索树,它或者是一棵空树,或者是一棵具有如下性质的非空二叉树:

(1)若它的左子树不空,则左子树上所有节点的值均不大于它的根节点的值; (2)若它的右子树不空,则右子树上所有节点的值均不小于它的根节点的值; (3)它的左、右子树也分别为二叉查找树。

等价定义:若以中序遍历二叉查找树,则会产生一个所有节点关键字值的递增序列。 例如:右下图的树,中序遍历得到的数值为(3,12,24,37,45,53,61,78,90,100)。

二叉查找树之所以又称为二叉排序树,因为它是“排过序”的二叉树,但并非是“用于排序”的二叉树。

不难发现,二叉查找树这种数据结构的优势在于它的有序性,这是其它类似功能的数据结构无法达到的。比如有序线性表虽然有序,但是插入算法的时间复杂度为O(n);堆的插入算法虽然时间复杂度为O(log2n),但是堆并不具有有序性。因此,我们要充分发挥二叉查找树的优势,就要充分利用其有序性和插入、查找算法的高效性。所以,如果要经常对有序数列进行“动态”的插入或查找工作,就可以采用二叉查找树来实现。

二叉查找树

二叉查找树

依据二叉查找树的定义,我们知道:具有相同结点集的二叉查找树,可能的形态很不同。例如对于集合{1,2,3}所建立的二叉查找树就可能是下图所示的五种形态的任一种。

二叉查找树

二叉查找树

二叉查找树

二叉查找树

(二)二叉查找树的数据结构

第1页

你可能喜欢

热门文档

相关文档

  • 数据结构实验报告六—BST(二叉查找树)实现动态查找表

    数据结构实验报告六—BST(二叉查找树)实现动态查找表_工学_高等教育_教育专区。C++数据结构实验报告六—BST(二叉查找树)实现动态查找表BST...

  • 二叉查找树、平衡树和B-树

    在根指针T所指二叉排序树中 二叉排序树用二叉链表存储。 二叉排序树用二叉链表存储 在根指针T 递归地查找关键字等于key的记录,若查找成功, key的记录 递归地查找...

  • Java数据结构之二叉查找树

    Java数据结构之二叉查找树_计算机软件及应用_IT/计算机_专业资料。介绍二叉查找树类的具体实现和相关性质。Java数据结构之二叉查找树二叉查找树是二叉树在查找领域的一...

  • 二叉查找树

    1、二叉排序树的定义 、 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者 是空树,或者是满足如下性质的二叉...

  • 二叉查找树

    二叉查找树报告人:朱贡睿 报告时间:2010.11.07 报告地点:计算机楼401 上讲内容回顾——散列表 散列表 上讲内容回顾直接寻址表 散列表 散列函数乘法散列发 除法...

  • 二叉查找树、平衡树和B-树 2

    在二叉排序树上的操作 1)查找例:在如下二叉排序树中查找关键字为24的记录。 24?45 继续在左 子树中查找 12 3 24?37 继续在左 子树中查找 37 45 24?12 ...

  • 二叉查找树,算法,排序

    二叉查找树,算法,排序_IT/计算机_专业资料。讲解二叉查找树的算法二叉查找树维基百科,自由的百科全书 自由的百科全书(重定向自二叉排序树) 3 层二叉查找树 二叉查...

  • bst二叉查找树

    二叉查找树(BST) 一、需求分析 利用二叉查找树(BST)实现一个动态查找表。 (1) 使用二叉树(BST)来实现。 (2) 二叉树使用链式结构(二叉链表)实现。 (3) ...

  • 二叉查找树实现代码及运行结果

    二叉查找树实现代码及运行结果_IT/计算机_专业资料。以C语言实现的二叉查找树。实现了一下基本操作:构造空表、销毁表、搜索指定关键字的元素、插入新元素、删除指定...

  • 二叉搜索树

    二叉搜索树_IT/计算机_专业资料。C语言二叉搜索树二叉搜索树定义 ? 查找 ? 二叉搜索树创建 ? 插入 ? 删除 示例 ? 二叉搜索树性能分析 ? 课后练习P197 10.4 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email