专栏首页五分钟学算法懵逼树上懵逼果:学习二分搜索树

懵逼树上懵逼果:学习二分搜索树

懵逼二叉树

懵逼树上懵逼果,

懵逼树下你和我。

一人一颗懵逼果,

一起学二分搜索。

数组、栈、队列、链表都是线性结构,树则是另外一种极其重要的数据结构。

树的种类有很多种,我们先从简单的 二分搜索树 开始树的学习。

二分查找法

二分查找法定义

是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束; 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空,则代表找不到。 这种搜索算法每一次比较都使搜索范围缩小一半。

动画演示

动画说明

注意:二分查找的前提是数列必须是有序的。

  • 目标是搜索数字 5
  • 首先,检查有序数列中心的数字,这里查找到时数字 4
  • 4 与 将要搜索的数字 5 进行比较,由于 4 小于 5,图中可以发现 5 在 4 的右边
  • 这时,就不需要观察 4 左边的数字了,置灰删除掉
  • 检查剩余有序数列中心的数字,这时是 5
  • 找到了这个数字

二叉查找树(Binary Search Tree)基础

二叉查找树也可叫做二分查找树。 它不仅可以查找数据,还可以高效地插入、删除数据。 特点:每个节点的key值大于左子节点,小于右子节点。 注意它不一定是完全的二叉树。

class Node {
  E e;
  Node left;  // 左孩子
  Node right; // 右孩子
}

二叉查找树有两个属性:

  • 所有节点都比左子树中的节点大
  • 所有节点都小于右子树中的节点

通过这两个属性,可以推断出以下结论:

  • 二叉查找树最小的节点位于最顶端节点的最左边子树行的末尾(如图数字 3 )
  • 二叉查找树的最大节点位于最顶端节点的最右边的子树行的末尾(如图数字 28 )

通过以下方式的进行添加元素与删除元素的操作,可以保留二叉查找树的完整性。

我们通过两组添加元素,三组删除元素,一组查找元素的操作来理解二叉查找树的属性性质。

添加元素操作

核心思想:从根节点开始找插入的位置,满足二叉搜索树的特性,比左子节点大,比右子节点小.

步骤:

  • 从根节点开始,先比较当前节点,如果当前节点为null那么就插入到这个节点。
  • 如果上面的节点不是null,那么和当前节点比较,如果小于节点就往左子树放,如果大于节点就往右子树放。
  • 然后分别对左子树或者右子树递归的递归进行如上 1 、 2 步骤的操作

添加元素 1

  • 从二叉查找树的最顶端节点开始,去找到附加节点的正确位置
  • 由于 1 < 15 , 向左走
  • 1 < 9 ,继续向左走
  • 1 < 3,继续向左走,但因为没有节点在其后序前方,因此将它作为一个新节点进行添加

添加元素 4

  • 同样的从二叉查找树的最顶端节点开始,去找到附加节点的正确位置
  • 由于 4 < 15 , 向左走
  • 4 < 9 ,继续向左走
  • 4 > 3,向右走
  • 4 < 8,向左走,但因为没有节点在其后序前方,因此将它作为一个新节点进行添加
代码实现

删除元素操作

步骤:

  • 找到左子树中找左子树中所有节点的最大的节点
  • 将这个节点赋值到删除节点的位置

删除元素 28

  • 该节点没有子类,直接删除

删除元素 8

  • 该节点有1个子类
  • 目标节点被删除,将子节点移动到已删除节点的位置

删除元素 9

  • 该节点有2个子类
  • 目标节点被删除,从删除节点的左子树中找到最大的节点,将其移到到删除的节点的位置
代码实现

查找元素操作

查找元素 12

  • 同样的,从二叉查找树的最顶端节点开始搜索
  • 12 < 15 ,向左走
  • 12 > 4 ,向右走
  • 找到 12
代码实现

可以看出,使用二叉查找树可以实现高效搜索。

但是如果树接近形成直线,那么搜索效率将极其差,变成了线性搜索。

因此二叉查找树就需要进行改进为平衡二叉树,比较常见的 Balanced Binary Tree有:

  • 红黑树
  • tree
  • AVL tree
  • Splay tree
  • Treap

二分搜索树的遍历

遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。二叉树的遍历有三种:

  • 前序遍历(Preorder Traversal):先访问当前节点,再依次递归访问左右子树
  • 中序遍历(Inorder Traversal):先递归访问左子树,再访问自身,再递归访问右子树
  • 后序遍历(Postorder Traversal):先递归访问左右子树,最后再访问当前节点。

前序遍历

中序遍历

后序遍历

§§

本文分享自微信公众号 - 五分钟学算法(blgczzz),作者:程序员小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-10

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我画了 20 张图,给女朋友讲清楚红黑树

    红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java 的 TreeMap 和 TreeSet 就是基于红黑树实现...

    五分钟学算法
  • 数据结构与算法——2-3-4树

    在前几篇文章中介绍了 2-3 树的定义以及插入删除操作。本篇文章将在 2-3 树的基础上更进一步,介绍比 2-3 树更为复杂的数据结构 2-3-4树 。之所以介...

    五分钟学算法
  • 数据结构与算法——2-3树

    前面讲到了二叉搜索树 (BST) 和二叉平衡树 (AVL) ,二叉搜索树在最好的情况下搜索的时间复杂度为 O(logn) ,但如果插入节点时,插入元素序列本身就...

    五分钟学算法
  • 了解红黑树的起源,理解红黑树的本质

    前面两节,我们一起学习了关于跳表的理论知识,并手写了两种完全不同的实现,我们放一张图来简单地回顾一下:

    彤哥
  • 二叉查找树-增删查和针对重复数据处理的 Java 实现

    大家好,我是多选参数的程序锅,一个正在”研究“操作系统、学数据结构和算法以及 Java 的疯狂猛补生。本篇将带来的是二叉查找树的相关知识,知识提纲如图所示。

    syy
  • 左倾红黑树、右倾红黑树、AA树,你不知道的还有很多!

    上一节,我们一起从二叉树、二叉查找树、平衡树、AVL树、2-3树、2-3-4树、B树,一路讲到红黑树,最后得出红黑树的本质:红黑树就是2-3-4树,请看下图:

    彤哥
  • 面试官问你B树和B+树,就把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    好好学java
  • 面试官问你 B树 和 B+ 树,就把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    范蠡
  • 面试官问你B树和B+树,就把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    zhisheng
  • 面试官问你什么B树和B+树,把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    乔戈里

扫码关注云+社区

领取腾讯云代金券