[数据结构] 二叉搜索树基本操作
定义
二叉搜索树是一种特殊的二叉树，其定义如下：
- 空树是二叉搜索树。
- 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
- 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
操作
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))