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

相关文章

来自专栏老马说编程

(45) 神奇的堆 / 计算机程序的思维逻辑

前面几节介绍了Java中的基本容器类,每个容器类背后都有一种数据结构,ArrayList是动态数组,LinkedList是链表,HashMap/HashSet是...

1999
来自专栏好好学java的技术栈

“365算法每日学计划”:06打卡-单向循环链表

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

451
来自专栏大数据和云计算技术

算法基础7:平衡查找树概述

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第7篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

3199
来自专栏程序员维他命

YYCache 源码解析(一):使用方法,架构与内存缓存的设计

YYCache是国内开发者ibireme开源的一个线程安全的高性能缓存组件,代码风格简洁清晰,阅读它的源码有助于建立比较完整的缓存设计的思路,同时也能巩固一下双...

1041
来自专栏算法channel

Leetcode|二叉树非递归版后序遍历

二叉树的非递归版后序遍历,首先定义TreeNode如下: """ TreeNode class """ class TreeNode(object): ...

3164
来自专栏codingforever

经典算法巡礼(七) -- 排序之堆排序

很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现...

312
来自专栏彭湖湾的编程世界

【算法】堆排序学习笔记

参考资料 《算法(第4版)》          — — Robert Sedgewick, Kevin Wayne 什么是二叉堆 在了解堆排序之前, 最重要的当...

2188
来自专栏desperate633

一篇文章搞懂红黑树的原理及实现2-3-4 Tree(2-3-4树)红黑树左倾红黑树的删除操作删除红黑树最小节点删除任意节点总结

二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找...

1462
来自专栏云霄雨霁

查找----基于二叉查找树

950
来自专栏云霄雨霁

数据结构----二叉堆和优先权队列

1380

扫码关注云+社区