美文网首页
[复习]二分搜索树(上)

[复习]二分搜索树(上)

作者: 吴敬悦 | 来源:发表于2021-03-23 23:18 被阅读0次

昨天在做 leetCode 的题时,我发现可以使用搜索树来实现,于是今天就复习一下,现在这个版本是我凭着记忆写出来的,明天我会按照课程再学习一遍并把二分搜素树的改进版本也学习了。昨天的那道题是: LeetCode 数据流中的第 K 大元素(上) ;这篇是没有解决问题的,等下次会使用这个方式再一次尝试。

先定义节点的数据:

    class Node {
      val = undefined;
      leftChild = null;
      rightChild = null;
      constructor(_val, left, right) {
        this.val = _val;
        this.leftChild = left;
        this.rightChild = right;
      }
    }

主要是包含值和两个孩子节点。这里我主要实现添加操作,删除明天补上。下面是实现对应的数据结构了:

    class SearchTree {
      data = null;
      len = 0
      constructor(arr = []) {
        this.initData(arr);
      }

      initData = (data = []) => {
        for (let i = 0; i < data.length; i ++) {
          this.add(data[i])
        }
      }

      _add = (node, e) => {
        // 如果是到最后了,那么就返回一个新节点
        if (!node) {
          return new Node(e, null, null)
        }
        // 如果当前节点比插入的要大,那么插入节点应当插入到左边
        if (node.val > e) {
          node.leftChild = this._add(node.leftChild, e)
        } else {
          node.rightChild = this._add(node.rightChild, e)
        }
        // 最后返回当前节点
        return node;
      }
      add = (ele) => {
        this.data = this._add(this.data, ele)
      }
    }

其实删除的算法也是挺多考虑的,甚至我觉得比添加要麻烦。看递归最好的办法就是看本身的函数实现,也就是明白函数是干什么的,比如我这里添加函数:

if (!node) {
  return new Node(e, null, null)
}

先看这里,当传入的节点为空时则返回新节点;如果不为空,那么将改节点插入到正确的位置,也就是如果插入节点比当前传入节点要大则需要插入到这个节点的右边,否则就是左边;同时返回当前的节点。也就是函数的目的是插入的同时返回本身;因为按刚才说的,应该是这样:

const temNode = new Node(e, null, null)
node[node.val > e ? 'leftChild' : 'rightChild'] = temNode

由于插入的位置不能是存在节点的位置,那么就需要找到最终要插入的位置,所以得继续寻找最终的位置:

if (node.val > e) {
   // 继续添加,这次是从 node.leftChild 的位置上添加
   node.leftChild = this._add(node.leftChild, e)
} else {
   node.rightChild = this._add(node.rightChild, e)
}

这样就能很容易看到递归的代码了,反正现在我是这样看的,不是很复杂都能很快看明白。

相关文章

  • [复习]二分搜索树(上)

    昨天在做 leetCode 的题时,我发现可以使用搜索树来实现,于是今天就复习一下,现在这个版本是我凭着记忆写出来...

  • AVL 树

    一:什么是 AVL 树? 在我的上一篇文章《二分搜索树与二分查找法》中,详细介绍了二分搜索树这种数据结构。二分搜索...

  • [复习]二分搜索树(中)

    今天忙到很晚,所以今天就只弄了删除的部分,而且都只是只能删除一个,不能把相同的都删除;而且算法还不简单,改天改进:...

  • 算法与数据结构系列之[二分搜索树-上]

    前几篇介绍了二叉树以及二叉树的遍历,接下来三篇介绍下二分搜索树。 1.什么是二分搜索树 二分搜索树(Binary ...

  • 手敲数据结构——使用二分搜索树实现Set

    关于实现二分搜索树,可以看前面的文章 手敲数据结构——二分搜索树

  • LeetCode 二叉树和递归专题 6:二分搜索树中的问题

    回顾二分搜索树的定义 二分搜索树的重要性质 二分搜索树的重要性质如下,初学的时候经常会被忽略或者错误地理解: 左子...

  • AVL树,怎么维持平衡性?

    简介 首先AVL树是二分搜索树,如果不知道二分搜索树的童鞋,可以先百度了解一下二分搜索树的基本特征。 那么为什么要...

  • 数据结构-二分搜索树

    二叉树:顾名思义就是每个节点都只能有两个子节点的树结构 二分搜索树 二分搜索树也是二叉树 二分搜索树的每个节点的值...

  • 算法与数据结构系列之[二分搜索树-下]

    上篇贴出了二分搜索树的C语言代码,这篇贴出二分搜索树的java实现代码。

  • 二分搜索树

    什么是二分搜索树?二分搜索树:二分搜索树动态数据结构,里存储的数据必须具有可比性,所以泛型要实现每个结点最多有两个...

网友评论

      本文标题:[复习]二分搜索树(上)

      本文链接:https://www.haomeiwen.com/subject/mfgqhltx.html