Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（十七）：二叉排序樹
前面已經(jīng)介紹了二叉樹的存儲和遍歷，今天這篇教程我們以二叉排序樹為例，來演示如何對二叉樹的節(jié)點(diǎn)進(jìn)行「增刪改查」。開始之前，我們先來介紹什么是二叉排序樹，以及為什么要引入這種二叉樹。
什么是二叉排序樹
我們前面已經(jīng)介紹了很多數(shù)據(jù)結(jié)構(gòu)，比如數(shù)組、鏈表、哈希表等，數(shù)組查找性能高，但是插入、刪除性能差，鏈表插入、刪除性能高，但查找性能差，哈希表的插入、刪除、查找性能都很高，但前提是沒有哈希沖突，此外，哈希表存儲的數(shù)據(jù)是無序的，哈希表的擴(kuò)容非常麻煩，涉及到哈希沖突時，性能不穩(wěn)定，另外，哈希表用起來爽，構(gòu)造起來可不簡單，要考慮哈希函數(shù)的設(shè)計(jì)、哈希沖突的解決、擴(kuò)容縮容等一系列問題。
有沒有一種插入、刪除、查找性能都不錯，構(gòu)建起來也不是很復(fù)雜，性能還很穩(wěn)定的數(shù)據(jù)結(jié)構(gòu)呢？這就是我們今天要介紹的數(shù)據(jù)結(jié)構(gòu) —— 二叉排序樹。
二叉排序樹也叫二叉搜索樹、二叉查找樹，它是一種特殊的二叉樹，我們重點(diǎn)關(guān)注「排序」二字，二叉排序樹要求在樹中的任意一個節(jié)點(diǎn)，其左子樹中的每個節(jié)點(diǎn)的值，都要小于這個節(jié)點(diǎn)的值，而右子樹節(jié)點(diǎn)的值都大于這個節(jié)點(diǎn)的值，所以這么看來，二叉排序樹是天然有序的。如果按照上篇教程講的中序遍歷，得到的結(jié)果將是一個從小到大的有序數(shù)據(jù)集：
但是構(gòu)造二叉排序樹的目的，并不是為了排序，而是為了提高查找、插入和刪除的速度。不管怎么說，在一個有序數(shù)據(jù)集上查找數(shù)據(jù)肯定比無序數(shù)據(jù)集要快，同時二叉排序樹這種非線性結(jié)構(gòu)，也非常有利于插入和刪除的實(shí)現(xiàn)。
下面我們就來看看如何實(shí)現(xiàn)二叉排序樹的插入、查找和刪除以及它們對應(yīng)的時間復(fù)雜度。
定義二叉排序樹
首先，我們需要定義好表示二叉樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，還是通過二叉鏈表來存儲二叉排序樹，為了提高代碼的復(fù)用性，我們將上篇教程定義的 Node 結(jié)構(gòu)體抽取出來放到獨(dú)立的 node.go 文件：
package mainimport ("fmt")// Node 通過鏈表存儲二叉樹節(jié)點(diǎn)信息type Node struct {Data interface{}Left *NodeRight *Node}func NewNode(data interface{}) *Node {return &Node{Data: data,Left: nil,Right: nil,}}func (node *Node) GetData() string {return fmt.Sprintf("%v", node.Data)}
然后，我們新建一個search.go文件定義下二叉排序樹對應(yīng)的結(jié)構(gòu)體，只需要根節(jié)點(diǎn)作為入口即可獲取整棵樹的結(jié)構(gòu)：
package main
type BinarySearchTree struct {root *Node}// NewBinarySearchTree 初始化二叉排序樹func NewBinarySearchTree(node *Node) *BinarySearchTree {return &BinarySearchTree{root: node,}}
這里我們通過結(jié)構(gòu)體組合的方式聲明二叉排序樹的根節(jié)點(diǎn)是一個 Node 類型的指針，并為其定義了一個構(gòu)造函數(shù)。
二叉排序樹的插入
接下來，我們按照二叉排序樹的定義，實(shí)現(xiàn)二叉排序樹節(jié)點(diǎn)的插入方法：
// Insert 插入數(shù)據(jù)到二叉排序樹func (tree *BinarySearchTree) Insert(data interface{}) error {var value intvar ok boolif value, ok = data.(int); !ok {return errors.New("暫時只支持int類型數(shù)據(jù)")}if node := tree.root; node == nil {// 二叉排序樹為空，則初始化tree.root = NewNode(value)return nil} else {// 否則找到要插入的位置插入新的節(jié)點(diǎn)for node != nil {if value < node.Data.(int) {if node.Left == nil {node.Left = NewNode(value)break}node = node.Left} else if value > node.Data.(int) {if node.Right == nil {node.Right = NewNode(value)break}node = node.Right} else {return errors.New("對應(yīng)數(shù)據(jù)已存在，請勿重復(fù)插入")}}return nil}}
如果是空樹，則將其作為根節(jié)點(diǎn)，否則判斷插入節(jié)點(diǎn)數(shù)據(jù)與當(dāng)前節(jié)點(diǎn)數(shù)據(jù)值的大小，如果小于當(dāng)前節(jié)點(diǎn)數(shù)據(jù)值，則遞歸遍歷左子樹，找到對應(yīng)的位置插入，如果大于當(dāng)前節(jié)點(diǎn)數(shù)據(jù)值，則遞歸遍歷右子樹找到對應(yīng)的位置插入。
我們可以寫一段簡單的測試代碼測試節(jié)點(diǎn)插入方法：
func main() {tree := NewBinarySearchTree(nil)tree.Insert(3)tree.Insert(2)tree.Insert(5)tree.Insert(1)tree.Insert(4)fmt.Println("中序遍歷二叉排序樹：")midOrderTraverse(tree.root)fmt.Println()}
這里我們使用了上一篇編寫的中序遍歷方法 midOrderTraverse，對應(yīng)的打印結(jié)果如下：
二叉排序樹的查找
二叉排序樹的刪除比較復(fù)雜，我們先來看查找邏輯的實(shí)現(xiàn)，查找實(shí)現(xiàn)非常簡單，和插入邏輯類似，依次遞歸比較就好了，直到目標(biāo)節(jié)點(diǎn)數(shù)據(jù)值和待查找的數(shù)據(jù)值一致，則返回該節(jié)點(diǎn)的指針，或者返回空，表示沒有找到：
// Find 查找值為data的節(jié)點(diǎn)func (tree *BinarySearchTree) Find(data int) *Node {if node := tree.root; node == nil {// 二叉排序樹為空返回空return nil} else {// 否則返回值等于data的節(jié)點(diǎn)指針for node != nil {if data < node.Data.(int) {node = node.Left} else if data > node.Data.(int) {node = node.Right} else {return node}}return nil}}
在上一步編寫的測試代碼基礎(chǔ)上，我們可以通過編寫如下代碼打印找到節(jié)點(diǎn)的對象信息。
fmt.Println("查找值為 3 的節(jié)點(diǎn)：")node := tree.Find(3)fmt.Printf("%v\n", node)fmt.Println("查找值為 10 的節(jié)點(diǎn)：")node = tree.Find(10)fmt.Printf("%v\n", node)
執(zhí)行代碼，打印結(jié)果如下：
二叉排序樹的刪除
二叉排序樹的刪除相對而言要復(fù)雜一些，需要分三種情況來處理：
第一種情況：如果要刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們只需要直接將父節(jié)點(diǎn)中指向要刪除節(jié)點(diǎn)的指針置為 nil。比如下圖中的刪除節(jié)點(diǎn) 55。
第二種情況：如果要刪除的節(jié)點(diǎn)只有一個子節(jié)點(diǎn)（只有左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)），我們只需要更新父節(jié)點(diǎn)中指向要刪除節(jié)點(diǎn)的指針，讓它指向要刪除節(jié)點(diǎn)的子節(jié)點(diǎn)就可以了。比如下圖中的刪除節(jié)點(diǎn) 13。
第三種情況：如果要刪除的節(jié)點(diǎn)有兩個子節(jié)點(diǎn)，這就比較復(fù)雜了。我們需要先找到這個節(jié)點(diǎn)的右子樹中節(jié)點(diǎn)值最小的節(jié)點(diǎn)，把它替換到要刪除的節(jié)點(diǎn)上，然后再刪除掉這個最小節(jié)點(diǎn)。因?yàn)樽钚」?jié)點(diǎn)肯定沒有左子節(jié)點(diǎn)（如果有左子節(jié)點(diǎn)，那就不是最小節(jié)點(diǎn)了），所以，我們可以應(yīng)用上面兩條規(guī)則來刪除這個最小節(jié)點(diǎn)。比如下圖中的刪除節(jié)點(diǎn) 18。（同理，也可以通過待刪除節(jié)點(diǎn)的左子樹中的最大節(jié)點(diǎn)思路來實(shí)現(xiàn)）
根據(jù)上面的思路，我們給出二叉排序樹節(jié)點(diǎn)刪除邏輯的實(shí)現(xiàn)代碼：
// Delete 刪除值為 data 的節(jié)點(diǎn)func (tree *BinarySearchTree) Delete(data int) error {if tree.root == nil {return errors.New("二叉樹為空")}p := tree.rootvar pp *Node = nil // p 的父節(jié)點(diǎn)// 找到待刪除節(jié)點(diǎn)for p != nil && p.Data.(int) != data {pp = pif p.Data.(int) < data {// 當(dāng)前節(jié)點(diǎn)值小于待刪除值，去右子樹查找p = p.Right} else {// 否則去左子樹查找p = p.Left}}if p == nil {return errors.New("待刪除節(jié)點(diǎn)不存在")}// 待刪除節(jié)點(diǎn)有兩個子節(jié)點(diǎn)，需要將待刪除節(jié)點(diǎn)值設(shè)置為該節(jié)點(diǎn)右子樹最小節(jié)點(diǎn)值，再刪除右子樹最小節(jié)點(diǎn)if p.Left != nil && p.Right != nil {minP := p.Right // 右子樹中的最小節(jié)點(diǎn)minPP := p // minP 的父節(jié)點(diǎn)// 查找右子樹中的最小節(jié)點(diǎn)for minP.Left != nil {minPP = minPminP = minP.Left}p.Data = minP.Data // 將 minP 的數(shù)據(jù)設(shè)置到 p 中p = minP // 下面就變成刪除 minP 了pp = minPP}// 應(yīng)用待刪除節(jié)點(diǎn)只有左/右子節(jié)點(diǎn)的邏輯var child *Nodeif p.Left != nil {child = p.Left} else if p.Right != nil {child = p.Right} else {child = nil}if pp == nil {// 刪除跟節(jié)點(diǎn)tree.root = nil} else if pp.Left == p {// 僅有左子節(jié)點(diǎn)pp.Left = child} else if pp.Right == p {// 僅有右子節(jié)點(diǎn)pp.Right = child}return nil}
在之前測試代碼的基礎(chǔ)上，編寫節(jié)點(diǎn)刪除方法的測試代碼：
fmt.Println("刪除值為 3 的節(jié)點(diǎn)：")err := tree.Delete(3)if err != nil {fmt.Printf("%v\n", err)} else {fmt.Println("刪除成功")}fmt.Println("中序遍歷刪除節(jié)點(diǎn)后的二叉排序樹：")midOrderTraverse(tree.root)fmt.Println()
執(zhí)行 search.go，打印結(jié)果如下：
二叉排序樹的時間復(fù)雜度
不論是插入、刪除、還是查找，二叉排序樹的時間復(fù)雜度都等于二叉樹的高度，最好的情況當(dāng)然是滿二叉樹或完全二叉樹，此時根據(jù)完全二叉樹的特性，時間復(fù)雜度是 O(logn)，性能相當(dāng)好，最差的情況是二叉排序樹退化為線性表（斜樹），此時的時間復(fù)雜度是 O(n)，所以二叉排序樹的形狀也很重要，不同的形狀會影響最終的操作性能，這也就引入了學(xué)院君接下來要繼續(xù)深入介紹的二叉樹內(nèi)容 —— 平衡二叉樹和紅黑樹。
（本文完）
學(xué)習(xí)過程中有任何問題，可以通過下面的評論功能或加入「Go 語言研習(xí)社」與學(xué)院君討論：
本系列教程首發(fā)在 geekr.dev，你可以點(diǎn)擊頁面左下角閱讀原文鏈接查看最新更新的教程。