二叉搜索樹的本質-有解無憂

引言

打算寫寫樹形資料結構：二叉查找樹、紅黑樹、跳表和 B 樹，這些資料結構都是為了解決同一個基本問題：如何快速地對一個大集合執行增刪改查，

本篇是第一篇，講講搜索樹的基礎：二叉搜索樹，

基本問題

如何在一千萬個手機號中快速找到 13012345432 這個號（以及相關聯資訊，如號主姓名）？

最笨的方案

把一千萬個手機號從頭到尾遍歷一遍，直到找到該手機號，回傳對應的姓名，其時間復雜度是 O(n)————當然這肯定不是我們要的方案，

最秀的方案

用散串列，可以在 O(1) 的時間復雜度完成查找，

關于散串列的原理和代碼參見演算法（TypeScript 版本），

散串列的問題

散串列的查詢性能非常優秀，插入和洗掉的性能也不賴，但它有什么問題呢？

我們稍微變換一下問題：如何在一千萬個手機號中快速找到在 1301111111 到 13022222222 之間所有的手機號？

和基本問題不同的是，這是個范圍查詢，

散串列的本質是通過對關鍵字（本例中是手機號）執行 hash 運算，將其轉換為陣列下標，進而可以快速訪問，

此處講的陣列是 C 語言意義上的陣列，不是 javascript、PHP 等腳本語言中的陣列，C 語言的陣列是一段連續的記憶體片段，對陣列元素的訪問是通過記憶體地址運算進行的，可在常數時間內訪問陣列中任意元素，

hash 運算的特點是隨機性，這也帶來了無序性，我們無法保證 hash(1301111111) < hash(1301111112)，

無序性使得我們無法在散串列上快速執行范圍查找，必須一個一個比較，時間復雜度又降到 O(n)，

基于有序陣列的二分搜索

如果這一千萬的手機號是排好序的（升序），我們有沒有更好的辦法實作上面的范圍查找呢？

對于排好序的序列，我們如果能快速找到下限（1301111111）和上限（13022222222）所在的位置，那么兩者之間所有的手機號就都是符合條件的，

如何才能快速找到 1301111111 的位置呢？

想想我們是怎么玩猜數字游戲的？

第一次猜 100，發現大了，第二次我們便傾向于猜 50 附近的數————而不是猜 99，如圖：

基于二分查找思想的猜數字游戲

這種思想叫二分法————這種方法可以將問題范圍成倍地縮小，進而可以至多嘗試 \(\log_{2}n\) 次即可找出解，對于一千萬個手機號來說，至多只需要比較 24 次即可找出 1301111111 的位置，相比于一千萬次，簡直是天壤之別，

代碼如下：

interface Value {
    // 為方便起見，這里限定 key 是數值型別
    key: number;
    val: unknown;
}

/**
 * 二分搜索
 * @param arr - 待搜索陣列，必須是按升序排好序的（根據 Value.key）
 * @param key - 搜索關鍵字
 * @reutrn 搜索到則回傳對應的 Value，否則回傳 null
 */
function binSearch(arr: Value[], key: number): Value | null {
    if (arr.length === 0) {
        return null
    }

    // 子陣列左右游標
    let left = 0
    let right = arr.length - 1

    while (left <= right) {
        // 取中
        const mid = left + Math.floor((right - left) / 2)
        const val = arr[mid]

        if (key === val.key) {
            return val
        }

        // key 小于 val 則在左邊找
        if (key < val.key) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return null
}

所以，如果需要對這一千萬個手機頻繁地執行范圍查找，二分搜索法是個不錯的選擇：先對一千萬個手機號執行排序，然后對排好序的序列執行二分搜索，

二分搜索的問題

二分搜索能很快地執行精確查找和范圍查找，但它仍然存在問題，

對一百個元素執行二分搜索，必須能夠在常數時間內定位到第 50 個元素————只有陣列（C 語言意義上的）這種資料結構才能做到，

也就是說，必須用陣列來實作二分搜索，

但陣列有個很大的缺陷：對插入和洗掉操作并不友好，它們都可能會造成陣列元素遷移，

比如要往有序陣列 arr = [1, 2, 3, 4, 5 ..., 100] 中插入元素 0 且繼續保證陣列元素的有序性，則必須先將既有的一百個元素都往右移一位，然后將 0 寫到 arr[0] 位置，洗掉元素則會造成后續元素的左移，

倘若插入和洗掉操作非常頻繁，這種遷移（復制）操作會帶來很大的性能問題，

可見，對有序陣列的查詢可以在 O(\(\log_{2}n\)) 執行，但其寫操作卻是 O(n) 復雜度的，

有沒有什么資料結構能夠讓讀寫操作都能在 O(\(\log_{2}n\)) 內完成呢？

二分搜索的啟發

二分搜索的優勢是能夠在一次操作中將問題范圍縮小到一半，進而能夠在對數的時間復雜度上求得問題的解，不過其劣勢是依賴于陣列，因而其插入和洗掉性能低下，

那么，我們現在的目的便是解決二分搜索的寫（插入和洗掉）性能，

要想提高寫性能，我們的直覺是擺脫陣列這種資料結構的桎梏————是否有別的資料結構代替陣列？

一個很自然的想法是鏈表，鏈表的優勢在于其元素節點之間是通過指標關聯的，這使得插入和洗掉元素時只需要變更指標關系即可，無需實際遷移資料，

// 鏈表的節點定義
interface Node {
    data: Value;
    next: Node;
}

然而，鏈表的劣勢是查詢：它無法像陣列那樣通過下標訪問（而只能從頭節點一個一個遍歷訪問），進而也就無法實作二分法，

如對于陣列 arr = [1, 2, 3, 4, 5]，我們能直接通過 arr[2] 訪問中間元素；但對于鏈表 link = 1 -> 2 -> 3 -> 4 -> 5，由于不是連續記憶體地址，無法通過下標訪問，只能從頭開始遍歷，

那么，我們如何解決鏈表的查詢問題呢？或者說如何用鏈表來模擬有序陣列的二分法呢？

二分法有兩個操作：

取中，快速定位到中間位置的元素（對于有序序列來說就是中位數），
比較，根據第一步取得的元素，決定后續操作：如果相等則回傳；如果比目標大，則取左半部子集繼續操作；如果比目標小，則取右半部子集繼續操作，

那么，如何在鏈表上實作上面兩個操作？

我們先考慮操作二：比較，如果比較結果不相等，則會去左邊或者右邊繼續查找，我們可以改造一下鏈表節點，用左右指標來表示“左邊”和“右邊”，左右指標分別指向左子鏈表和右子鏈表，改造后的節點定義如下：

// 改進的節點定義
interface Node {
    data: Value;
    // 左指標
    left: Node;
    // 右指標
    right: Node;
}

由于改造后的鏈表節點有 left 和 right 兩個指標，相當于一個節點分了兩個叉，故名為二叉，

再考慮操作一：取中，取中將原陣列一分為三：當前元素（中間元素）、左子陣列、右子陣列，

我們可以將它映射到改造后的鏈表中的當前節點、左（left）子鏈表、右（right）子鏈表，查找時，如果當前節點的值小于目標值，則通過 right 指標進入到右子鏈表中繼續查找，反之通過 left 指標進入左子鏈表查找，

陣列轉鏈表

繼續分析之前，我們先從直觀上考察一下改造后的鏈表，分叉后，整個結構不再像單條鏈子，更像一棵樹，于是我們不再稱之為“二叉鏈表”，而是稱作“二叉樹”，對應地，左右子鏈表也更名為“子樹”，

對應陣列看，很容易知道，節點左子樹中的所有元素都小于等于節點元素，右子樹中的所有元素都大于等于節點元素————這是二叉搜索樹最重要（甚至是唯一重要）的性質，

至此，我們用鏈表的節點代替陣列的元素，用節點的左右指標（或者說左右指標指向的兩棵子樹）代替左右子陣列，

現在還剩下最后一個問題：如何將陣列中的每個元素映射到這棵二叉搜索樹（或者叫“改造后的鏈表”）中？

既然二分法是不斷地取陣列（包括左右子陣列）中間位置的元素進行比較，那么我們將取出來的元素從上到下（從樹根開始）依次掛到這棵樹的節點上即可，如此當我們從樹根開始遍歷時，拿到的元素的順序便和從陣列中拿到的一致，

我們以陣列 arr = [1, 2, 3, 4, 5, 6, 7] 為例，看看如何生成對應的二叉搜索樹，

有序陣列轉成二叉搜索樹

如上圖：

先取整個陣列中間元素 4，作為二叉樹的根節點；
取左子陣列的中間元素 2，作為根節點的左子節點；
取右子陣列的中間元素 6，作為根節點的右子節點；
依此遞回處理，直到取出陣列中所有的元素生成二叉樹的節點，整棵二叉樹生成完成；

我們將上面的程序轉換成代碼：

// 二叉搜索樹
class BinSearchTree {
    // 樹根節點
    root: Node;
}

/**
 * 基于已排好序（根據 key）的陣列 arr 構建平衡的二叉搜索樹
 */
function buildFromOrderdArray(arr: Value[]): BinSearchTree {
    const tree = new BinSearchTree()
    // 從樹根開始構建
    tree.root = innerBuild(arr, 0, arr.length - 1)

    return tree
}

/**
 * 基于子陣列 arr[start:end] 構建一棵以 node 為根節點的二叉子樹，回傳根節點 node
 */
function innerBuild(arr: Value[], start: number, end: number): Node {
    if (start > end) {
        // 空
        return null
    } else if (start == end) {
        // 只剩下一個元素了，則直接回傳一個節點
        return { data: arr[start], left: null, right: null }
    }

    /**
     * 使用二分思想構建二叉樹
     */
     
    // 中間元素
    const mid = start + Math.floor((end - start) / 2)
    // 當前節點
    const curr: Node = { data: arr[mid], left: null, right: null }
    
    /**
     * 遞回生成左右子樹
     */
    // 左子樹
    curr.left = innerBuild(arr, start, mid - 1)
    // 右子樹
    curr.right = innerBuild(arr, mid + 1, end)

    return curr
}

二叉搜索樹的查找

二叉搜索樹是基于二分搜索思想構建的，其搜索邏輯也和二分搜索相同，只不過將左右子陣列替換成左右子樹，

以搜索元素 13 為例：

二叉搜索樹查找元素

上圖中搜索步驟：

從根節點開始比較，15 大于 13，到本節點的左子樹繼續搜索；
節點 6 小于 13，到本節點的右子樹繼續搜索；
節點 7 小于 13，到本節點的右子樹繼續搜索；
節點 13 等于 13，找到目標節點，結束；

對比二分搜索可以發現，二叉搜索樹中的 left 和 right 子樹就是對應二分搜索中左右子陣列，兩者的搜索邏輯本質上是一致的，

代碼如下：

class BinSearchTree {
    // 樹根節點
    root: Node;
    
    /**
     * 在以 node 為根的子樹中搜索關鍵字為 key 的節點并回傳該節點
     * 如果沒有找到則回傳 null
     */
    search(key: unknown, node: Node = undefined): Node {
        // 默認取根
        node = node === undefined ? this.root : node
        
        // 遇到 null 節點，說明沒搜到，回傳 null
        if (!node) {
            return null
        }
        
        // 先判斷當前節點
        if (node.data.key === key) {
            // 找到，即可回傳
            return node
        }
        
        // 沒有找到，則視情況繼續搜索左右子樹
        if (key < node.data.key) {
            // 目標值小于當前節點，到左子樹中搜索
            return this.search(key, node.left)
        }
        
        // 目標值大于等于當前節點，到右子樹中搜索
        return this.search(key, node.right)
    }
}

從圖中可見，對于任何元素的搜索，搜索次數不可能大于從根到所有葉節點的最長路徑中節點個數（上圖中是 5），如果用這條路徑的邊來表達的話，搜索次數不可能超過最長路徑邊數加 1，

這個最長路徑的邊數即是整棵樹的高，

對于一顆完美的平衡二叉樹來說，這個高 h = \(\log_{2}n\)，其中 n 是節點數量，因而說二叉搜索樹的查詢時間復雜度是 O(\(\log_{2}n\))，和二分搜索是一致的，

注意上面說的是完美的平衡二叉樹，但二叉搜索樹并不是天生平衡的，所以才引出了各種平衡方案，諸如 2-3 樹、紅黑樹、B 樹等，

特殊查找：最小元素

由于二叉搜索樹中的任意一個節點，其左邊元素總小于該節點，所以要找最小元素，就是從根節點開始一直往左邊找，

如圖：

最小元素

代碼如下：

class BinSearchTree {
    // 樹根節點
    root: Node;
    
    /**
     * 查找以 node 為根的子樹的最小節點并回傳
     */
    min(node: Node = undefined): Node {
        // 默認取根節點
        node = node === undefined ? this.root : node
        
        if (node === null || !node.left) {
            // 如果是空子樹，或者 node.left 是空節點，則回傳
            return node
        }
        
        // 存在左子樹，繼續往左子樹中找
        return this.min(node.left)
    }
}

相對應的是最大值，也就是遞回地往右邊找，此處略，

按序遍歷

對于有序陣列，很容易通過回圈從頭到尾按序遍歷陣列中元素，對應地，如何按序遍歷二叉搜索樹呢？

二叉搜索樹是根據二分法遞回生成的，所以同樣可以用二分法來解決此問題，

對于一棵樹來說，它分為三部分：樹根節點、左子樹、右子樹，其中大小關系是：左子樹 <= 樹根節點 <= 右子樹，所以我們以這個順序遍歷整棵樹，便可以按序輸出，

這種遍歷方式，由于是在中間步驟操作樹根節點，又稱之為中序遍歷，

相應地，按“樹根節點 -> 左子樹 -> 右子樹”的順序遍歷稱之為先序遍歷，按“左子樹 -> 右子樹 -> 樹根節點”的順序遍歷稱之為后序遍歷，

中序遍歷代碼：

class BinSearchTree {
    // 樹根節點
    root: Node;
    
    /**
     * 中序遍歷
     */
    inorder(): Node[] {
        const arr: Node[] = []
        this.innerInorder(this.root, arr)

        return arr
    }

    /**
     * 對 x 子樹執行中序遍歷，遍歷的節點放入 arr 中
     */
    innerInorder(x: Node, arr: Node[]) {
        if (!x) {
            return
        }

        // 先遍歷左子樹
        this.innerInorder(x.left, arr)
        // 自身
        arr.push(x)
        // 右子樹
        this.innerInorder(x.right, arr)
    }
}

范圍查詢

如何在二叉搜索樹上執行范圍查詢？

問題：按序回傳二叉搜索樹中所有大于等于 start 且小于等于 end 的節點集合（即回傳所有節點 x，x 滿足：start <= x <= end），

上面的中序遍歷其實就是一種特殊的范圍查詢：min <= x <= max，所以范圍查詢的思路和中序遍歷一樣，只不過在遍歷時加上范圍限制，

具體來說，什么時候需要去查左子樹呢？當左子樹有可能存在符合條件的元素時需要去查，如果當前節點 x 的值小于范圍下限（start），而 x 的左子樹的值都小于等于 x 的，說明此時其左子樹中不可能存在符合條件的節點，無需查詢；或者，如果 x 的值大于范圍上限（end），而 x 的右子樹的值都大于等于 x 的，說明此時其右子樹中不可能存在符合條件的節點，也無需查詢，其他情況則需要查詢，

范圍查詢

代碼如下：

class BinSearchTree {
    // 樹根節點
    root: Node;
    
    /**
     * 按序回傳所有大于等于 start 且小于等于 end 的節點集合
     */
    range(start: unknown, end: unknown): Node[] {
        const arr: Node[] = []
        this.innerRange(this.root, start, end, arr)
        return arr
    }
    
    /**
     * 在 x 子樹中查找所有大于等于 start 且小于等于 end 的節點并放入 arr 中
     */
    innerRange(x: Node, start: unknown, end: unknown, arr: Node[]) {
        if (!x) {
            return
        }
        
        // 比較節點 x 和 start、end 之間的大小關系
        const greaterThanStart = x.data.key >= start
        const smallerThanEnd = x.data.key <= end

        // 如果當前節點大于等于 start，則需要搜索其左子樹
        if (greaterThanStart) {
            this.innerRange(x.left, start, end, arr)
        }
        
        // 如果 x 在 start 和 end 之間，則符合條件，存入 arr
        if (greaterThanStart && smallerThanEnd) {
            arr.push(x)
        }
        
        // 如果當前節點小于等于 end，則需要搜索其右子樹
        if (smallerThanEnd) {
            this.innerRange(x.right, start, end, arr)   
        }
    }
}

插入操作

對于二叉樹來說，新節點總是被插入到 null 節點（末端）處，

還是以上圖為例，插入新節點 14：

插入元素

如圖所示，插入操作分兩步：

搜索，這一步和查找操作一樣，相當于是搜索這個新節點 14，結果沒搜到，遇到了 null 節點（Node(13).right）；
插入，生成新節點 14 并插入到節點 13 的右側（Node(13).right = Node(14)）；

很明顯，插入操作的時間復雜度也是 O(\(\log_{2}n\))，完美！

插入操作的代碼如下：

class BinSearchTree {
    // 樹根節點
    root: Node;
    
    /**
     * 將元素 data 插入到樹中
     */
    insert(data: Value) {
        // 從根節點開始處理
        // 插入完成后，將新根賦值給 root
        this.root = this.innerInsert(data, this.root)
    }
    
    /**
     * 將元素 data 插入到以 node 為根的子樹中
     * 回傳插入元素后的子樹的根節點
     */
    innerInsert(data: Value, node: Node): Node {
        if (node === null) {
            // 遇到了 null 節點，說明需要插入到該位置
            return { data: data, left: null, right: null }
        }
        
        // 比較 data 和 node 的值，視情況做處理
        if (data.key < node.key) {
            // 待插入的元素小于當前節點，需要插入到當前節點的左子樹中
            node.left = this.innerInsert(data, node.left)
        } else {
            // 插入到右子樹中
            node.right = this.innerInsert(data, node.right)
        }
        
        // 插入完成后，需回傳當前節點
        return node
    }
}

洗掉操作

洗掉操作需要分幾種情況，

情況一：洗掉葉子節點，該節點的 left 和 right 都是 null，

這種情況很簡單，直接刪掉該元素即可，如洗掉節點 9：

洗掉情況一

情況二：待洗掉的節點只有一個子節點，用該子節點代替該節點即可，如洗掉節點 13：

洗掉情況二

以上兩種情況都比較簡單，第三種情況則稍微復雜，

情況三：待洗掉的節點有左右兩個子節點，如圖中節點 6，將 6 洗掉后，我們無法簡單的用其 left 或 right 子節點替代它————因為這會造成兩棵子樹一系列的變動，

前面說過，二叉搜索樹本質上是由有序陣列演化而來，那么我們不妨以陣列的角度看是否有所啟示，

上圖用陣串列示：arr = [2, 3, 4, 6, 7, 9, 13, 15, 18, 17, 20]，該陣列中刪掉元素 6 后，如何才能讓陣列中其他元素調整次數最少（這里不考慮遷移，因為二叉樹不存在遷移開銷）？

自然是直接用 6 的前一個（4）或者后一個（7）元素替代 6 的位置，其中 4 恰恰是 6 左邊子陣列中的最大值，而 7 恰恰是其右邊子陣列中的最小值，

我們不妨用右邊子陣列中最小值（7）來替代 6————映射到二叉搜索樹中便是節點 6 的右子樹的最小節點，

前面已經討論過二叉搜索樹中最小值的求解邏輯：順著節點左子樹（left）一直遞回查找，直到 node.left 等于 null，該 node 便是最小值————也就是說，一棵樹的最小節點不可能有左子節點，即最小節點最多有一個子節點，這便是情況一或者情況二，

那么能否用右子樹中最小節點（7）替代當前節點（6）呢？無論從有序陣列還是從二叉搜索樹本身角度看，都很容易證明是可以的（替換后仍然符合二叉搜索樹的性質），

因而，情況三可以作如下處理：

將右子樹中最小節點的 data 賦值給當前節點；
洗掉右子樹中最小節點；

洗掉情況三

代碼如下：

class BinSearchTree {
    // 樹根節點
    root: Node;
    
    // ...
    
    /**
     * 洗掉 key 對應的節點
     */
    delete(key: unknown) {
        const node = this.search(key, this.root)
        if (!node) {
            // key 不存在
            return
        }
        
        this.root = this.innerDelete(this.root, node)
    }
    
     /**
     * 洗掉子樹 current 中 del 節點，并回傳操作完成后的子樹根節點
     */
    innerDelete(current: Node, del: Node): Node {
        /**
         * 當前節點即為待洗掉節點
         */
        if (current === del) {
            // 情況一：當前節點沒有任何子節點，直接洗掉
            if (!current.left && !current.right) {
                return null
            }
            
            // 情況二：只有一個子節點
            if (current.left && !current.right) {
                // 只有左子節點，用左子節點替換當前節點
                return current.left
            }
            
            if (current.right && !current.left) {
                // 只有右子節點，用右子節點替換當前節點
                return current.right
            }
            
            // 情況三：有兩個子節點
            // 取右子樹的最小節點
            const minNode = this.min(current.right)
            // 用最小節點的值替換當前節點的
            current.data = https://www.cnblogs.com/linvanda/archive/2023/04/03/minNode.data
            // 洗掉右子樹中的最小節點
            current.right = this.innerDelete(current.right, minNode)

            return current
        }
        
        /**
         * 當前節點不是待洗掉節點，視情況遞回從左或右子樹中洗掉
         */
        if (del.data.key < current.data.key) {
            // 待洗掉節點小于當前節點，從左子樹洗掉
            current.left = this.innerDelete(current.left, del)
        } else {
            // 待洗掉節點大于當前節點，繼續從右子樹洗掉
            current.right = this.innerDelete(current.right, del)
        }
        
        return current
    }
}

很容易證明，洗掉操作的時間復雜度也是 O(\(\log_{2}n\))，

二叉搜索樹的問題

由上面的插入操作可知，二叉搜索樹新增節點時總是往末端增加新節點，這種操作方式有個問題：當我們一直朝同一個方向（一直向左或者一直向右）插入時，便很容易出現傾斜，

比如我們向一棵空樹中依次插入 1, 2, 3, 4, 5：

const tree = new BinSearchTree()
tree.insert({ key: 1, val: 1 })
tree.insert({ key: 2, val: 2 })
tree.insert({ key: 3, val: 3 })
tree.insert({ key: 4, val: 4 })
tree.insert({ key: 5, val: 5 })

得到的二叉樹如下：
傾斜二叉樹

二叉樹退化成了普通鏈表，所有的操作退化為 O(n) 復雜度！

所以在插入和洗掉二叉樹節點時，需要執行額外的操作來維護樹的平衡性，后面將要介紹的紅黑樹和 B 樹就是兩種非常著名的解決方案，

總結

散串列能很好地解決精確查詢（O(1) 復雜度），但無法解決范圍查詢（必須 O(n) 復雜度）；
基于有序陣列的二分搜索能很好地解決精確查詢和范圍查詢（O(\(\log_{2}n\)) 復雜度），但無法解決插入和洗掉（必須 O(n) 復雜度）；
基于二分搜索思想改進的鏈表（二叉搜索樹）能很好地解決查詢（包括范圍查詢）、插入和洗掉，所有的操作都是 O(\(\log_{2}n\)) 的時間復雜度；
二叉搜索樹中以任意節點作為根的子樹仍然是一棵二叉搜索樹，這個特點很重要，它是遞回操作的關鍵；
二叉搜索樹存在節點傾斜問題，會降低操作性能，極端情況下會退化成普通鏈表，所有的操作都退化到 O(n) 復雜度；
為解決二叉搜索樹的傾斜問題，實際應用中需引入相關平衡方案，本系列的后序文章將介紹三種常見的方案：紅黑樹、跳表和 B 樹；

本文中的示例代碼采用 TypeScript 語言實作，且用遞回法寫的，完整代碼參見二叉搜索樹（遞回法），非遞回法代碼參見二叉搜索樹（回圈法），

本文來自博客園，作者：林子er，轉載請注明原文鏈接：https://www.cnblogs.com/linvanda/p/17283480.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549060.html

標籤：其他

上一篇：阿里云EMAS移動測驗最佳實踐｜馬來西亞第一大電子錢包通過EMAS測驗提效6倍

下一篇：Low-Code，一定“low”嗎？