专栏首页javascript艺术程序员的内功心法,你不来看看吗?

程序员的内功心法,你不来看看吗?

最近这阵工作,我越来越感受到基础知识能力的重要性。
之前都是在赶进度、做业务逻辑,逃避自己基础薄弱的事实。
最近下定决心,加强之前薄弱的基础。先从自己之前一直似是而非的搜索树的内容开始吧。

在生活中我们经常会使用到搜索的功能。在我们数据量不大的情况下,可以使用每次遍历全部数据,查询我们的目标数据。当数据量增加时,我们遍历的方式就有些力不从心了;也可以将数据的数据排序,使用比较高效的二分查找方式,但是在插入或删除数据时,数组表现就会很慢。所以我们可以结合二分查找查询的高效 + 链表添加删除的高效性来实现高效搜索(符号表)的情况

下面我将列举一些树的内容定义(后续所有的代码使用Java语言实现)

  • 树由节点构成,每个节点都有一个父节点(根结点不存在父节点)
  • 节点包含的链接可以指向不存在的NULL或者其他真实存在的节点
  • 每个节点都可以包含多个子链接,将子链接的个数称为;树的度是指所有的子节点中最大的度(将度为2的树称为二叉树、度为3的树称为三叉树等)。如图1~3示
  • 叶节点:没有子节点的节点 如图-1的B、C、D节点
  • 父节点:有子树的节点是其子树的根节点的父节点 图-1的A节点是B、C、D节点的父节点
  • 子节点:若A节点是B节点的父节点,那么B是A的子节点,子节点也可以成为孩子节点 图-3的A节点是B、C、D的父节点,同时也是H节点的子节点
  • 兄弟节点:具有相同一个父节点的个节点彼此是兄弟节点 图-1的B、C、D

二叉搜索树

定义

  • 每个节点只指向一个父节点,最多包含左右两个子链接
  • 左子边节点的Key小于父节点、右子节点的Key大于父节点 如图-4示
//二叉搜索树的节点定义

查找

//查询算法

查询极值(极大/极小值)

根据查找二叉树的特性,极值存在于叶节点或者只包含一个子节点的父节点中

//查询极小值,一直向左查询,如果没有左节点,则认为当前节点最小 例子:A节点
public TreeNode<T> findMin(TreeNode<T> node){
    if (Objects.isNull(node.getLeft())) {
        return node;
    }
    return findMin(node.getLeft());
}
//查询极大值,一直向右查询,如果没有右节点,则认为当前节点最大 例子:Z节点
public TreeNode<T> findMax(TreeNode<T> node){
    if (Objects.isNull(node.getRight())) {
        return node;
    }
    return findMax(node.getRight());
}

插入

图-7展示了插入Z的作为F右子节点的情况(插入到左子节点的情况类似,不再赘叙)

图-8展示了被插入节点存在的情况。

public void add(T element) {
    if (element == null) {
        throw new RuntimeException("数据不能为NULL");
    }
    TreeNode<T> node = new TreeNode<>();
    node.data = element;
    if (Objects.isNull(root)) {
        root = node;
        return;
    }
    addImpl(root, node);
}
private void addImpl(TreeNode<T> root, TreeNode<T> node) {
    T val = root.data;
    T element = node.data;
    int sub = element.compareTo(val);
    //包含要插入的值,不处理
    if (sub == 0) {
        return;
    }
    //插入的值大于根节点的值,将新节点作为根节点的右子节点
    if (sub > 0) {
        TreeNode<T> right = root.getRight();
        if (Objects.isNull(right)) {
            root.setRight(node);
            return;
        }
        addImpl(right, node);
    } else {        //插入的值小于根节点的值,将新节点作为根节点的左子节点
        TreeNode<T> left = root.getLeft();
        if (Objects.isNull(left)) {
            root.setLeft(node);
            return;
        }
        addImpl(root.getLeft(), node);
    }
}

删除

由于删除节点比较复杂,我们先看下删除极大值(极小值)的情况,为节点删除做好准备工作

删除最小值

由于二叉搜索树的特点二(左子边节点的Key小于父节点、右子节点的Key大于父节点)那么最小值节点要么是叶子节点或者包含右子节点的情况

  • 极小值节点是叶子节点,可以直接移除
  • 极小值节点有一个右子节点,将右子节点替换为父节点(如果还包含左子节点,那么当前节点非最小值)
//移除最小的节点,将返回的值作为根节点
private TreeNode<T> deleteMin(TreeNode<T> node) {
    if (Objects.isNull(node.getLeft())) {   //没有左子节点,返回右子节点
        return node.getRight();
    }
    TreeNode<T> min = deleteMin(node.getLeft());    //递归左子树
    node.setLeft(min);
    return node;
}

删除最大值

和删除最小值的情况相似。只不过递归的是右子树

  • 极大值节点是叶子节点,可以直接移除
  • 极大值节点有一个左子节点,将左子节点替换为父节点(如果还包含右子节点,那么当前节点非最大值)
//移除node节点的最大值,使用返回值替换原节点

删除节点

我们将删除节点的情况归纳如下

  • 被删除节点是叶子节点,可以直接移除
  • 被删除节点只包含一个子节点(左子节点或者右子节点),我们需要需要将子节点替换到父节点
  • 被删除节点包含两个子节点,如果直接移除E节点,那么子节点D、F将会丢失。我们需要转换思路,将包含两个子节点的情况转换为上两种情况。下面我们介绍下如何处理(T.Hibbard 1962年提出的方法,膜拜巨佬
    • 我们使用前驱节点(后续节点)的值替换被删除节点,然后删除前驱节点(后继节点)
    • 前驱节点:当前节点的左子树中的最大值
    • 后继节点:当前节点的右子树中的最小值
//删除element的节点,返回根结点的引用
public TreeNode<T> delete(T element, TreeNode<T> node){
    if (Objects.isNull(node)) {
        return null;
    }
    T val = node.data;
    int res = val.compareTo(element);
    if (res < 0) {          //被删除节点在node的右子树
        TreeNode<T> rNode = delete(element, node.getRight());
        node.setRight(rNode);
    } else if (res > 0) {   //被删除节点在node的左子树
        TreeNode<T> lNode = delete(element, node.getLeft());
        node.setLeft(lNode);
    } else {                //node为被删除节点
        //包含一个子节点,使用子节点替换父节点
        if (Objects.isNull(node.getLeft())) {   
            return node.getRight();
        }
        if (Objects.isNull(node.getRight())) {
            return node.getLeft();
        }
        //左右节点均存在,使用后继节点代替,移除后继节点
        TreeNode<T> tmp = node;
        node = findMin(node.getRight());
        TreeNode<T> rNode = deleteMin(tmp.getRight());
        node.setRight(rNode);
        node.setLeft(tmp.getLeft());
    }
    return node;
}

至此,我们已经完成了二叉搜索树的增加、查询、删除的方法。我们发现二叉搜索树的实现并不困难,并且在大多数场景下也能正常运行。二叉搜索树在极端情况的性能也是不可忍受的。

后面我们将讲述一种在任何场景初始化,运行时间都将是对数级的(下一篇预告平衡查找树

本文是在工作之余整理出来的,难免出现逻辑纰漏、排版错误,还请各位客官理解,同时欢迎各位留言和我交流分享!

本文分享自微信公众号 - javascript艺术(gh_4e5484fd6b52),作者:郭里奥

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

原始发表时间:2021-04-19

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员的内功心法-234树

    红黑树、B树、B+树,都是软件开发中一个比较难理解和掌握的知识点。他们的本质依然是平衡二叉搜索树。如果直接去学习红黑树、B树、B+树的知识点,无异于雾里看花。这...

    javascript艺术
  • 程序员的内功心法-AVL树

    接上篇文章《二叉搜索树》了解到二叉搜索树在极端情况也不能满足我们对于查询性能的要求。

    javascript艺术
  • 这些高情商程序猿的操作,你确定不来看看吗?

    ? ? 说到程序员,大家能想到什么?格子衫?还是发际线?还是对着电脑改bug的场景。 ? 同样作为以为编程大(cai)师(ji)的小E,其实还有一个烦恼,那就...

    腾讯NEXT学位
  • 那些阻碍程序员成长的小细节,看看你有吗?

    拿到开发任务后,直接上手写代码。 缺少必要的沟通与设计,返工的机率极大。前后端数据的交互格式,功能潜在的关联点不清晰,接口调用方功能是否完备,存储结构的设计,复...

    MavenTalker
  • 108个程序员的笑话,你都看得懂吗?

    1、程序猿最烦两件事,第一件事是别人要他给自己的代码写文档,第二件呢?是别人的程序没有留下文档。 2、程序猿的读书历程:x语言入门—>x语言应用实践—>x语言高...

    智能算法
  • 不骗人的程序员,日子一定没法过,不信你看...

    用户6543014
  • 神级程序员教你如何写代码——十年编程内功心法

    写代码就是学一门语言然后开始撸代码吗?看完了我一系列文章的同学或者本身已经就是老鸟的同学显然不会这么认为。编程是一项非常严谨的工作!虽然我们自嘲为码农,但是这工...

    企鹅号小编
  • 14万程序员挑战过的算法题,看看你处于哪个阶段?(附答案)

    程序员都想挑战这四道算法趣题!通过挑战你也可以看到自己大体处于哪个级别。 在挑战之前,先介绍下问题的具体形式: 每个问题大致分为“问题”和“详解”两部分。 请各...

    BestSDK
  • 「核心基础篇」Guide的Java后端书架来啦!都是Java程序员必看的书籍?

    封面是在武汉租的房子里的一个小书架,基本都是今年买的书,所以看着不是很多。每次看完一本书之后,我都会带回家里,避免占位置以及搬家的时候太麻烦了。

    Guide哥
  • 20 个关于程序员的笑话,看懂了,你就不会羡慕工资高了!

    我们作为程序员,整天编写代码,整夜调试,写给成千上万行代码。可能这个编程也不一定是他们最喜欢或者最擅长干的事情。

    肉眼品世界
  • 程序员看过来!6499元Mac mini带回家!让你写代码的速度快上30倍!

    这次发布会的主角是:iPad Pro、MacBook Air、Mac mini、Apple Pencil。

    镁客网
  • 看完这篇还不懂高并发中的线程与线程池你来打我(内含20张图)

    你可能会有疑问,讲多线程为什么要从CPU说起呢?原因很简单,在这里没有那些时髦的概念,你可以更加清晰的看清问题的本质。

    范蠡
  • 零基础Python-第一个程序

    BIF 就是 Built-in Functions,内置函数。为了方便程序员快速编写脚本程序(脚本就是要编程速度快快快!!!),Python 提供了非常丰富的内...

    用户6901119
  • 代码洁癖系列(一):什么是整洁代码

    作为一个代码洁癖患者,我最大的愿望就是世界和平……对不起,拿错剧本了,最大的愿望就是将对代码的洁癖传播给每一个人,净化所有的代码。这是一个宏大的愿望,但我会一直...

    Jackeyzhe
  • 程序员每天该做的事

      最好的方式是写工作日志,把自己今天完成了什么事情,遇见了什么问题都记录下来,日后翻看好处多多   

    ccf19881030
  • STC单片机程序是如何下载进单片机的?看完还不懂你来找我

    这个问题我们分两部分来说,一部分是单片机端是如何实现的,另一部分是电脑端是如何实现的,下面我们慢慢BB。

    单片机技术宅
  • 国产程序员陋习,写在农历猴年前

    工作这么多年了,接触过一些外国程序员也接触过不少国产程序员。 觉得国产程序员还是有些陋习的,当然不是所有人都有,只是比较常见而已。 大家随便看看,当是娱乐就好了...

    麦克-堂
  • 程序员最糟心的8件事,只有经历过的才能看懂

    当程序员面对比翻书还快的修改需求时,内心一定是崩溃的,应该已经把对方枪毙5分钟了! ? 那么,在这个互相伤害的世界里,还有哪些是你们已经经历和必将经历的呢,让...

    BestSDK
  • 程序员怎样才能达到编程的最高境界

          程序员怎样才能达到编程的最高境界?最高境界绝对不是你去编两行代码,或者是几分钟能写几行代码,或者是用什么所谓的可视化工具产生最少的代码这些工作,这都...

    landv

扫码关注云+社区

领取腾讯云代金券