JS数据结构之二叉查找树(BST)
源码
点击这里前往Github获取本文源码。
介绍
二叉查找树(Binary Search Tree, BST)也叫做有序二叉树。对于树中的每个节点,都要满足左子树的所有项比它小,右子树所有项比它大。由于这个要求,每次操作最优情况的时间复杂度都可以达到 O(log n),因为一次比较可以过滤掉一半。
但是,在极端情况下,它会退化为一个普通的链表,此时再进行操作的时间复杂度就会是 O(n) 了。
这个问题需要平衡二叉树来解决,本文只讨论普通的二叉查找树。
实现
逐个函数来分析。
创建节点
定义一个用来生成节点的函数node
:
function createNode(val) {
return { val, left: undefined, right: undefined }
}
这个函数就是返回一个对象,没什么好说的。
查找
考虑BST的性质:对于任意一个节点,左子树的所有项都比它小,右子树的所有项都比它大。所以,我们可以写出下列代码:
function contains(node, val) {
if (!node) {
return false
}
if (val < node.val) {
return contains(node.left, val)
} else if (val > node.val) {
return contains(node.right, val)
}
return true
}
尽管比较简单,这里也说一下执行过程
- 如果
node
为空,直接返回false
。考虑到有null
和undefined
两种可能性,这里就直接用取反运算符来判断是否为空了。 - 如果要查找的值比当前节点的值小,就去左子树查找;如果大,就去右子树查找。
- 既不大于也不小于,那就是相等,返回
true
。
后续的算法与这些步骤都是类似的。
插入
同样是考虑BST的性质,步骤会在下方解析,先展示代码:
function insert(node, val) {
if (!node) {
return createNode(val)
}
if (val < node.val) {
node.left = insert(node.left, val)
} else if (val > node.val) {
node.right = insert(node.right, val)
}
return node
}
因为这些都是递归实现,所以比如第一行的逻辑实际上要到最后一步才执行,确实阅读起来是有点反人类的。
- 判断当前节点是否为空,如果是的话就返回一个新的节点。
- 如果要插入的值比当前节点的值小,就去左子树插入;如果大,就去右子树插入。
- 无论有没有进入
if
块,都返回当前节点
看到这里,我一开始不是很理解为什么诸如第6行要写成node.left = insert(node.left, val)
的形式,这里分析一下
- 如果
node.left
为空,那么insert(node.left, val)
就会返回一个新的节点,成功执行了插入的操作。 - 如果
node.left
不为空,那么insert(node.left, val)
返回的还是node.left
,此时插入已经在更深的层次完成。
读者可以在纸上演算一遍插入的过程,我当时就是根据代码自己演算这个过程之后就能大概理解了。
删除
删除操作的难度系数更大一些,但是核心思想上和上面的插入并无不同之处,代码如下:
function remove(node, val) {
if (!node) {
return node
}
if (val < node.val) {
node.left = remove(node.left, val)
} else if (val > node.val) {
node.right = remove(node.right, val)
} else if (node.left && node.right) {
// Find minimum value
let min = node.right
while (min.left) {
min = min.left
}
node.val = min.val
node.right = remove(node.right, node.val)
} else {
node = node.left || node.right
}
return node
}
我们根据图片来分析,我们要在下面这个BST中删除值为2的节点:
下面步骤中的node
会被标黄,表示当前节点;val表示要删除的值。
- 比较
val
与node.val
的大小
-
val
比node.val
的值小,执行从左子树删除的操作。
-
val
与当前节点的值相等,并且左右子树都不为空。
- 从右子树找到最小值,就是这里标绿的节点,并且把它赋值给当前节点。
- 从右子树把刚才获得的最小值3删掉。
- 此时进入了新的递归调用,
val
为3
,它小于当前节点值。
- 从左子树删除
val
值。
- 此时的节点与
val
相同,但是左右子树是空。
- 将它赋值为
node.left || node.right
,这里就是undefined
。
- 最深层的递归函数执行结束,返回上一层函数,是
node.left = remove(node.left, val)
。
- 执行结束,再把这个节点本身返回给上一层函数。
- 执行结束,把这个节点本身返回到最外层函数。
执行完毕,成功删除了指定的节点。看起来多,那是因为我把每一层递归调用都放出来了,包括递归函数调用结束后返回上一层的时候我也列出来了。实际上,关键步骤是,把当前节点的值赋值为右子树里的最小值,和删除右子树里的最小值。
参考
相关文章
- js书写原生ajax,JS 原生ajax写法
- js面试题及答案2020_JS面试题大全
- Js排序算法_js 排序算法
- JS数据结构之哈希表(散列表)
- js定时器与延时器_JS做定时器倒计时
- JS设置定时器_js设置定时器
- JS字符串转换为JSON的四种方法
- js 数组去除重复数据-5 个提升你 JS 编码水平的实例
- 如何让别人看不懂你的 JS 代码?
- 【JS 逆向百例】猿人学系列 web 比赛第五题:js 混淆 - 乱码增强,详细剖析
- vue.js客服系统实时聊天项目开发(十七)解决url get传参后进行base64解密问题
- 使用NVM安装Node.js
- JS使用自定义的方法初始化数组
- JS操作CSS样式(非常详细)
- Linux上的JS压缩工具(js压缩工具linux)
- 利用 JS 实现 Redis 的连接(js连接redis)
- JS实时链接Oracle让数据库访问更便捷(js实时连接oracle)
- 使用JS操作Oracle数据库探索潜在可能性(js和oracle数据库)
- JavaScript探索之旅掌握Oracle和JS的完美融合(js与oracle)
- js实现图片预加载(js操作Image对象属性complete,事件onload异步加载图片)
- js修改input的type属性及浏览器兼容问题探讨与解决
- JS禁用浏览器退格键实现思路及代码
- js高效去除数组重复元素示例代码
- js获取当前地址JS获取当前URL的示例代码
- js检测网络是否具体连接功能的代码
- js实现正方形颜色从下往上升的效果