定義

二叉搜索樹是一種特殊的二叉樹，其定義如下：

1. 空樹是二叉搜索樹。
2. 若二叉搜索樹的左子樹不為空，則其左子樹上所有點的附加權(quán)值均小于其根節(jié)點的值。
3. 若二叉搜索樹的右子樹不為空，則其右子樹上所有點的附加權(quán)值均大于其根節(jié)點的值。
4. 二叉搜索樹的左右子樹均為二叉搜索樹。

操作

CRUD

二叉搜索樹的基本操作有：查詢、新增、刪除；

這些操作的最優(yōu)時間復雜度為 \(O(\log n)\) ，最壞時間復雜度為 \(O(n)\)，隨機構(gòu)建的二叉搜索樹的期望高度為 \(O(\log n)\)。

遍歷

根據(jù)二叉搜索樹的定義可知：二叉搜索樹的中序遍歷結(jié)果是非降序序列。

遍歷二叉搜索樹的時間復雜度是 \(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);

查找最值

• 最小值為二叉搜索樹最左邊的節(jié)點；
• 最大值為二叉搜索樹最右邊的節(jié)點。

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為空，則已到達葉子節(jié)點，找不到指定值；
• 若root的值為target，則搜索到目標值；
• 若root的值大于target，則在root的左子樹中繼續(xù)搜索；
• 若root的值小于target，則在root的右子樹中繼續(xù)搜索。

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

插入一個元素

在以 root 為根節(jié)點的二叉搜索樹中插入一個值為 value 的節(jié)點。

分類討論：

• 若root為空，直接返回一個值為value的新節(jié)點；
• 如果root的值等于value，表示元素已存在，根據(jù)應用場景做相關(guān)處理（有的設(shè)計是節(jié)點的count屬性+1，有的設(shè)計是不做處理）；
• 如果root的值大于value，則在root的左子樹中插入值為value的節(jié)點；
• 如果root的值小于value，則在root的右子樹中插入值為value的節(jié)點。

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;
}

刪除一個元素

在以 root 為根節(jié)點的二叉搜索樹中刪除一個值為 value 的節(jié)點。

分類討論：

• 若root為葉子節(jié)點，則直接刪除；
• 若root只有一個子節(jié)點，則返回這個子節(jié)點；
• 若root有兩個子節(jié)點，一般用右子樹的最小值代替它，然后將它刪除。(具體的操作是將右子樹的最小值賦值給它，然后去右子樹中遞歸刪除這個值，完成“代替”)

function remove(root, value){
    if(root==null)return null;
    
    if(value < root.val){
        // 在左子樹中搜索并刪除目標節(jié)點
        root.left = remove(root.left, value);
        return root;
    }else if(value > root.val){
        // 在右子樹中搜索并刪除節(jié)點
        root.right = remove(root.right, value);
        return root;
    }else{
        // 找到節(jié)點了
        // case 1: 葉子節(jié)點
        if(root.left==null && root.right==null){
            root = null;
            return root;
        }
        
        // case 2: 一個子節(jié)點
        if(root.left==null){
            return root.right;
        }else if(root.right==null){
            return root.left;
        }
        
        // case 3: 兩個子節(jié)點
        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 中文網(wǎng) (nodejs.cn)

最近發(fā)現(xiàn)一個在Markdown里畫圖挺好用的工具，比如上面的二叉樹就是用Mermaid畫的，可以用指令實現(xiàn)一些簡單的圖表繪制。

比如下面這段指令：

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是節(jié)點中的值，(())表示圓形，[]表示矩形；
• -->：箭頭，==>更粗的箭頭；
• &：表示語句的組合，如果沒有這個&，則需要編寫兩行指令分別表示左右子節(jié)點的配置。

效果圖：

參考文章

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

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

[3] 數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹詳解-CSDN博客

[4] 流程圖語法 | Mermaid 中文網(wǎng) (nodejs.cn)