算法基础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 条评论
登录 后参与评论

相关文章

来自专栏郭耀华‘s Blog

《剑指offer》全部题目-含Java实现

陆续刷了好久,算是刷完了《剑指offer》,以下全部AC代码,不一定性能最优,如有错误或更好解答,请留言区指出,大家共同交流,谢谢~ 1.二维数组中的查找 在...

4657
来自专栏云霄雨霁

数据压缩----霍夫曼树和霍夫曼压缩

1610
来自专栏数据处理

leetcode222求完全二叉树节点个数

2494
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

504
来自专栏wannshan(javaer,RPC)

JDK PriorityBlockingQueue remove(Object o) 源码分析

先知道PriorityBlockingQueue 是利用数组存储二叉堆实现。最小值(最优先)放在queue[0]位置。 //删除某个元素 public bool...

3377
来自专栏算法channel

二叉树非递归版的中序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

2975
来自专栏武培轩的专栏

LinkedList源码解析(JDK1.8)

1 package java.util; 2 3 import java.util.function.Consumer; 4 ...

2988
来自专栏Java帮帮-微信公众号-技术文章全总结

JavaWeb18-jquery学习笔记(Java全栈开发)

jquery一.筛选 筛选与之前的选择器雷同,筛选提供的都是函数. 1. 过滤 eq(index|-index):获取指定索引的元素.如果是正数,索引从0开始...

3029
来自专栏猿人谷

合并两个排序的链表

题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如下图中的链表1和链表2,则合并之后的升序链表如链表3所示。 ...

1827
来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

3396

扫描关注云+社区