算法基础6:二叉树查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第6篇《二叉树查找》,非常赞!希望对大家有帮助,大家会喜欢!

前面系列文章:

归并排序

#算法基础#选择和插入排序

由快速排序到分治思想

算法基础:优先队列

二分查找

1、二叉树

在链接二叉树查找之前我们要了解一下二叉树是个什么玩意。

二叉树指的数一颗最多只有两个两个子树的数据树型数据结构。其两个子树分别称为左子树和右子树,一个在根节点的左边,一个在根节点的右边 这就是一颗二叉树。下面这些都是二叉树。

2、二叉查找树

在了解了二叉树的前提下,我们可以聊聊二叉查找树。二叉查找树是一个特殊的二叉树。他同样具有最多只有两个子树的特性。但是他的特别点在于其左子树大于根节点。其右子树小于根节点。

3、二叉查找树实现查找

因为二叉查找树的特殊特性使用它可以很方便的对队列的的数据进行查找和插入和删除。

器查找实现原理如下:他先找到根节点和根节点对比大小之后,如果大于根节点则去左节点去查找,如果还是大于左节点的话,则继续找左节点的左节点。如果小于左节点的话,则找做节点的右节点,若是查找的节点为空了。则表示不存在这个值。 若是等于了,就表示找到对应的值。同理如果小于根节点则去右节点查找和左节点一样。

具体代码如下:

 public Value get(Key key){
 return get(root, key);
      }
 private Value get(Node x,Key key){
 if(x==null) returnnull;
 intcmp=key.compareTo(x.key);
 if(cmp<0) return get(x.left,key);
 elseif(cmp>0) return get(x.right,key);
 elsereturnx.value;
      }

特性:查找速度 1.39lgN 插入速度 1.39lgN

优缺点:

优点:和二分查找对比起来,插入速度更快二分查找插入的速度是N/2 插入速度是1.39lgN

缺点:查找慢和二分查找对比起来二分查找的查找速度为lgN 所以比二分查找慢39%

应用:

我们之后会说的二三树,红黑树,B-树都是基于二叉查找树扩展实现的,理解了二叉树,理解剩下的这些相对容易些。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-02-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

更新Silverlight ctp到Silverlight beta 1.0

下面是我更新Silverlight ctp到Silverlight beta 1.0的一个纪录,希望对各位同学有帮助。 1、卸载Silverlight ctp ...

1759
来自专栏fangyangcoder

基于FPGA的IIR滤波器

                                                        by方阳

1361
来自专栏10km的专栏

cuda8+cuDNN Faster R-CNN安装塈运行demo

安装cuda cuda8安装参见网上教程 安装cuDNN py-faster-rcnn/caffe-fast-rcnn目前不支持cuDNN5。 如果使用cu...

2916
来自专栏逸鹏说道

Linux上访问SQL Server数据库

.NET跨平台之旅:升级至ASP.NET 5 RC1,Linux上访问SQL Server数据库 今天微软正式发布了ASP.NET 5 RC1(详见Announ...

2955
来自专栏张善友的专栏

Visual Studio Magazine -Mono for Android

Cross-Platform Development With Mono for Android -- Visual Studio Magazine -plat...

17710
来自专栏张善友的专栏

Mono SVN最新代码或者Mono 1.2.5 支持IronPython 2.0

IronPython 2.0基于Dynamic Language Runtime(DLR). Mono开发团队迅速完成了对DLR的支持.IronPython 2...

1856
来自专栏张善友的专栏

每周.NET前沿技术文章摘要(2017-05-17)

汇总国外.NET社区相关文章,覆盖.NET ,ASP.NET等内容,本期包含性能分析这一主题内容

3570
来自专栏用户2442861的专栏

win10 安装 Cygwin

http://preshing.com/20141108/how-to-install-the-latest-gcc-on-windows/

1833
来自专栏张善友的专栏

How does it work in Mono's C# compiler?

Introduction Mono is an Open Source free programming language project. It is an ...

2777
来自专栏码匠的流水账

使用webflux提升数据导出效率

两种方法目前看来用时差不多,不过后者可以避免超时。当然使用传统mvc也可以实现类似效果,就是拿到response的输出流不断地write和flush。不过web...

1952

扫码关注云+社区