专栏首页小浩算法第39期:小白一看就会的 BST 删除!

第39期:小白一看就会的 BST 删除!

在两节中,我们了解了BST(二叉搜索树)的概念,并且知道了如何在BST中查找一个元素。那我们又如何在BST中去删除一个元素呢?我们将通过本节的例题进行学习! 下面我们仍然通过例题进行讲解。

01、题目分析

第450题:删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  • 首先找到需要删除的节点;
  • 如果找到了,删除它。

说明:要求算法时间复杂度为 O(h),h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。
    5
   / \
  2   6
   \   \
    4   7

强烈建议先学习之前两节内容! 以达到最好的学习效果!

02、复习巩固

先复习一下,二叉搜索树(BST)的特性:

  • 若它的左子树不为空,则所有左子树上的值均小于其根节点的值
  • 若它的右子树不为空,则所有右子树上的值均大于其根节点得值
  • 它的左右子树也分别为二叉搜索树

如下图就是一棵典型的BST:

03、图解分析

明确了概念,我们进行分析。我们要删除BST的一个节点,首先需要找到该节点。而找到之后,会出现三种情况。

1、待删除的节点左子树为空,让待删除节点的右子树替代自己。

2、待删除的节点右子树为空,让待删除节点的左子树替代自己。

3、如果待删除的节点的左右子树都不为空。我们需要找到比当前节点小的最大节点(前驱),来替换自己

或者比当前节点大的最小节点(后继),来替换自己。

分析完毕,我们一起看代码怎么实现吧。

04、GO语言示例

这里我们给出通过后继节点来替代自己的方案(请后面自行动手实现另一种方案):

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val {
        root.Left = deleteNode( root.Left, key )
        return root
    }
    if key > root.Val {
        root.Right = deleteNode( root.Right, key )
        return root
    }
    //到这里意味已经查找到目标
    if root.Right == nil {
        //右子树为空
        return root.Left
    }
    if root.Left == nil {
        //左子树为空
        return root.Right
    }
    minNode := root.Right
    for minNode.Left != nil {
        //查找后继
        minNode = minNode.Left
    }
    root.Val = minNode.Val
    root.Right = deleteMinNode( root.Right )
    return root
}


func deleteMinNode( root *TreeNode ) *TreeNode {
    if root.Left == nil {
        pRight := root.Right
        root.Right = nil
        return pRight
    }
    root.Left = deleteMinNode( root.Left )
    return root
}

执行结果:

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

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

原始发表时间:2020-09-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第38期:BST 的搜索(小白必看)

    在上一节中,我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢?和普通的二叉树又有何不同?我们将在本节内容中进行学习! 下面我们仍然通过例题进行讲解。

    程序员小浩
  • 基本算法|图解各种树(二)

    01 — 二叉搜索树 基本算法|图解各种树(一) 二叉搜索树,又称为二叉排序树,简写为 BST,它与线性表,链表,二叉树间的关系,二维链表近似是二叉树,BST继...

    double
  • 平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

    平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严...

    Angel_Kitty
  • 野生前端的数据结构基础练习(7)——二叉树

    一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

    大史不说话
  • 漫画:二叉树系列 第五讲(BST的删除)

    在两节中,我们了解了BST(二叉搜索树)的概念,并且知道了如何在BST中查找一个元素。那我们又如何在BST中去删除一个元素呢?我们将通过本节的例题进行学习!

    程序员小浩
  • 【43期】盘点那些必问的数据结构算法题之二叉树基础

    来自:juejin.im/post/5ba3bb52e51d450e942f3031

    良月柒
  • 跳跃表深入理解

    redis 中 zset 是一个有序非线性的数据结构,它底层核心的数据结构是跳表。跳表(skiplist)是一个特俗的链表,相比一般的链表,有更高的查找效率,其...

    CodingCode
  • Treap——堆和二叉树的完美结合,性价比极值的搜索树

    Treap本质上也是一颗BST(平衡二叉搜索树),和我们之前介绍的SBT是一样的。但是Treap维持平衡的方法和SBT不太一样,有些许区别,相比来说呢,Trea...

    TechFlow-承志
  • 数据结构(二):二叉搜索树(Binary Search Tree)

    二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

    zhipingChen

扫码关注云+社区

领取腾讯云代金券