[数据结构] 二叉搜索树基本操作

定义

二叉搜索树是一种特殊的二叉树,其定义如下:

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

操作

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))

参考文章

[1] 二叉搜索树 & 平衡树 - OI Wiki

[2] 二叉搜索树_百度百科 (baidu.com)

[3] 数据结构——二叉搜索树详解-CSDN博客

[4] 流程图语法 | Mermaid 中文网 (nodejs.cn)

热门相关:弃妇种田忙   勇闯天涯   豪门24小时:吻别霸道前夫   豪门退婚妻:宝贝,再嫁我一次!   盖世双谐