[数据结构] 二叉搜索树基本操作
定义
二叉搜索树是一种特殊的二叉树,其定义如下:
- 空树是二叉搜索树。
- 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。
- 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
操作
CRUD
二叉搜索树的基本操作有:查询、新增、删除;
这些操作的最优时间复杂度为 \(O(\log n)\) ,最坏时间复杂度为 \(O(n)\),随机构建的二叉搜索树的期望高度为 \(O(\log n)\)。
遍历
根据二叉搜索树的定义可知:二叉搜索树的中序遍历结果是非降序序列。
遍历二叉搜索树的时间复杂度是 \(O(n)\)。
let arr = [];
function traverse(root){
if(root==null)return;
traverse(root.left);
arr.push(root.val);
traverse(root.right);
}
traverse(root);
console.log(arr);
查找最值
- 最小值为二叉搜索树最左边的节点;
- 最大值为二叉搜索树最右边的节点。
function findMinNode(root){
while(root.left!==null){
root = root.left;
}
return root;
}
function findMaxNode(root){
while(root.right!==null){
root = root.right;
}
return root;
}
搜索
递归搜索,分类讨论:
- 若
root
为空,则已到达叶子节点,找不到指定值; - 若
root
的值为target
,则搜索到目标值; - 若
root
的值大于target
,则在root
的左子树中继续搜索; - 若
root
的值小于target
,则在root
的右子树中继续搜索。
function search(root, target){
if(root==null)return null;
if(root.val == target){
return root;
}else if(target < root.val){
return search(root.left, target);
}else{
return search(root.right, target);
}
}
插入一个元素
flowchart TD
id1((30)) --> id2((15)) & id3((41))
id3((41)) --> id4((35)) & id5((48))
id4((35)) --> id6((33)) & id7((36))
在以 root
为根节点的二叉搜索树中插入一个值为 value
的节点。
分类讨论:
- 若
root
为空,直接返回一个值为value
的新节点; - 如果
root
的值等于value
,表示元素已存在,根据应用场景做相关处理(有的设计是节点的count
属性+1,有的设计是不做处理); - 如果
root
的值大于value
,则在root
的左子树中插入值为value
的节点; - 如果
root
的值小于value
,则在root
的右子树中插入值为value
的节点。
function insert(root, value){
if(root==null)return new TreeNode(value);
if(root.val > value){
root.left = insert(root.left, value);
}else if(root.val < value){
root.right = insert(root.right, value);
}else{
// root.val == value
}
return root;
}
删除一个元素
flowchart TD
id1((30)) --> id2((15)) & id3((41))
id3((41)) --> id4((35)) & id5((48))
id4((35)) --> id6((33)) & id7((36))
在以 root
为根节点的二叉搜索树中删除一个值为 value
的节点。
分类讨论:
- 若
root
为叶子节点,则直接删除; - 若
root
只有一个子节点,则返回这个子节点; - 若
root
有两个子节点,一般用右子树的最小值代替它,然后将它删除。(具体的操作是将右子树的最小值赋值给它,然后去右子树中递归删除这个值,完成“代替”)
function remove(root, value){
if(root==null)return null;
if(value < root.val){
// 在左子树中搜索并删除目标节点
root.left = remove(root.left, value);
return root;
}else if(value > root.val){
// 在右子树中搜索并删除节点
root.right = remove(root.right, value);
return root;
}else{
// 找到节点了
// case 1: 叶子节点
if(root.left==null && root.right==null){
root = null;
return root;
}
// case 2: 一个子节点
if(root.left==null){
return root.right;
}else if(root.right==null){
return root.left;
}
// case 3: 两个子节点
const findMinNode = (root)=>{
while(root.left!==null){
root = root.left;
}
return root;
}
const rightMin = findMinNode(root.right);
root.val = rightMin.val;
root.right = remove(root.right, rightMin.val);
return root;
}
}
题外话——Mermaid
Mermaid官方文档:流程图语法 | Mermaid 中文网 (nodejs.cn)
最近发现一个在Markdown里画图挺好用的工具,比如上面的二叉树就是用Mermaid画的,可以用指令实现一些简单的图表绘制。
比如下面这段指令:
flowchart TD
id1((30)) --> id2((15)) & id3((41))
id3((41)) --> id4((35)) & id5((48))
id4((35)) --> id6((33)) & id7((36))
flowchart
:流程图;TD
:从上到下的绘制方向;id*
:标识符,和变量名一个道理;((val))
:val
是节点中的值,(())
表示圆形,[]
表示矩形;-->
:箭头,==>
更粗的箭头;&
:表示语句的组合,如果没有这个&
,则需要编写两行指令分别表示左右子节点的配置。
效果图:
flowchart TD
id1((30)) --> id2((15)) & id3((41))
id3((41)) --> id4((35)) & id5((48))
id4((35)) --> id6((33)) & id7((36))