二叉搜索樹

基本概念

二叉搜索樹(BST,Binary Search Tree)

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:

• 若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值
• 若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值
• 它的左右子樹也分別為二叉搜索樹

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

二叉搜索樹/二叉查找樹也稱二叉排序樹,因為二叉排序樹的中序遍歷結果是升序

常用結論

二叉搜索樹的左子樹一定小于根,右子樹一定大于根, 結合定義遞歸子樹 可以得到

• 左子樹的最右節(jié)點是左子樹的最大節(jié)點,右子樹的最右節(jié)點是右子樹的最大節(jié)點.

• 左子樹的最左節(jié)點是左子樹的最小節(jié)點,右子樹的最左節(jié)點是右子樹的最小節(jié)點.

• 二叉搜索樹的最小節(jié)點是左子樹的最左節(jié)點,最大節(jié)點是右子樹的最右節(jié)點

用途

實際情況很少直接使用搜索二叉樹,多是根據(jù)搜索二叉樹的高效搜索特性,衍生出更為實用的高階數(shù)據(jù)結構,例如平衡二叉搜索樹(AVL樹,紅黑樹)等...

1. K模型：K模型即只有key作為關鍵碼，結構中只需要存儲Key即可，關鍵碼即為需要搜索到的值。( 在不在 的問題)
   比如：給一個單詞word，判斷該單詞是否拼寫正確，具體方式如下：
   以詞庫中所有單詞集合中的每個單詞作為key，構建一棵二叉搜索樹
   在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。

還有如:門禁系統(tǒng),車庫系統(tǒng)等...

1. KV模型：每一個關鍵碼key，都有與之對應的值Value，即的鍵值對。該種方
   式在現(xiàn)實生活中非常常見： ( 通過一個值查找另一個值 )
   比如英漢詞典就是英文與中文的對應關系，通過英文可以快速找到與其對應的中文，英
   文單詞與其對應的中文就構成一種鍵值對；
   再比如統(tǒng)計單詞次數(shù)，統(tǒng)計成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出
   現(xiàn)次數(shù)就是就構成一種鍵值對。

還有如:通訊錄

二叉搜索樹的性能分析

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。

對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度的函數(shù)，即結點越深，則比較次數(shù)越多。
但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結構的二叉搜索樹：

最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數(shù)為：$log_2 N$ ( $log_2 N$ )
最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數(shù)為：$\frac{N}{2}$ ( $\frac{N}{2}$ )

二叉搜索樹的操作

查找

1. 從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
2. 最多查找高度次，走到到空，還沒找到，這個值不存在。

插入

1. 樹為空，則直接新增節(jié)點，賦值給root指針(第一個節(jié)點就是root)
2. 樹不空，按二叉搜索樹性質查找插入位置，插入新節(jié)點

特別地

• 同樣一組數(shù)據(jù),插入順序不同,得到的二叉樹也不同

• 當插入的值已存在時,插入失敗(不考慮multi)

刪除

首先查找元素是否在二叉搜索樹中，如果不存在，則返回.

否則,根據(jù)樹的結構定義,可以得到3種情況

1. 要刪除的結點無孩子結點
2. 要刪除的結點只有左孩子或右孩子時
3. 要刪除的結點有左、右孩子結點

看起來有待刪除節(jié)點有4中情況，實際情況:

• 要刪除的結點無孩子結點時,直接刪除

• 要刪除的結點只有左孩子或右孩子時,將左孩子或右孩子給父親

  1. 要刪除的結點可能是父親的左孩子或者是右孩子,有2*2種情況(要刪除的結點是父親的左孩子或右孩子)

  2. 左右孩子都是空時,也滿足情況,因此可以合并無孩子結點情況

  3. 在1的前提下,恰好是根節(jié)點,也是一種情況(讓另外一個孩子做根即可)

• 要刪除的結點有左右孩子(子樹)時,需要找一個既要比左子樹大也要比右子樹小的節(jié)點來補上.

  根據(jù) 遞歸定義 得知,只有左孩子的最右結點和右孩子的最左結點符合條件,二選一即可

  當選擇使用右孩子的最左結點時,有以下三種情況(與是不是根無關)

  1. 要刪除的結點的右子樹的最小結點恰好是要刪除結點的右孩子.

  2. 要刪除的結點的右子樹的最小結點沒有右孩子.

  3. 要刪除的結點的右子樹的最小結點有右孩子

     

     (上圖舉例分析)

代碼實現(xiàn)

BSTree.hpp

template
struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;

    BSTreeNode(K key) 
    :_key(key),_left(nullptr),_right(nullptr)
    {}
};

template
class BSTree {
public:
    using Node = BSTreeNode;
    BSTree() = default;
    BSTree(const BSTree& bst) {
        _root = Copy(bst._root);
    }
    BSTree& operator=(BSTree bst) { //拷貝復用
        swap(_root,bst.root);
        return *this;
    }
    ~BSTree() {
        Destroy(_root);
    }

public:
    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            _root->_key = key;
            return true;
        }
        BSTreeNode* cur = _root;
        BSTreeNode* parent = _root;
        while (cur) {
            if (key < cur->_key) {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key) {
                parent = cur;
                cur = cur->_right;
            }
            else {
                return false;
            }
        }
        //走出循環(huán),說明樹中不存在該節(jié)點, 可以插入
        cur = new BSTreeNode(key);
        if (key < parent->_key) {

            parent->_left = cur;
        }
        else {
            parent->_right = cur;
        }
        return true;
    }

    bool Find(const K& key) {
        if (_root == nullptr) return false;

        Node* cur = _root;
        while (cur) {
            if (key < cur->_key) {
                cur = cur->_left;
            }
            else if (key > cur->_key) {
                cur = cur->_right;
            }
            else {
                return true;
            }
        }
        // 從循環(huán)出來,說明沒找著
        return false;
    }

    bool Erase(const K& key) {
        if (_root == nullptr) return false;

        Node* cur = _root;
        Node* parent = _root;

        while (cur) {
            if (key < cur->_key) {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key) {
                parent = cur;
                cur = cur->_right;
            }
            else {
                //沒有左孩子
                if (cur->_left == nullptr) {
                    if (cur == _root) {
                        _root = cur->_right;
                    }
                    else if (parent->_left == cur) {
                        parent->_left = cur->_right;
                    }
                    else {
                        parent->_right = cur->_right;
                    }
                    delete cur;
                    return true;
                }
                //沒有右孩子
                else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    }
                    if (parent->_left == cur) {
                        parent->_left = cur->_left;
                    }
                    else {
                        parent->_right = cur->_left;
                    }
                    delete cur;
                    return true;
                }
                //有左右孩子
                else {
                    //找右孩子(子樹)的最小結點/最左結點
                    Node* rightMin = cur->_right;  //明確不為空
                    Node* rightMinParent = cur;
                    while (rightMin->_left) {
                        rightMinParent = rightMin;
                        rightMin = rightMin->_left;
                    }
                    // 刪除右子樹最小結點有3種情況(與是不是根無關)
                    //1. 要刪除的結點右子樹最小結點恰好是自己的右孩子.
                    //2. 要刪除的結點的右孩子的左子樹的最左結點沒有右孩子.
                    //3. 要刪除的結點的右孩子的左子樹的最左結點有右孩子.
                    //結論解析: 復用刪除單結點代碼,進行刪除rightMin即可
                    K tmp = rightMin->_key;
                    Erase(rightMin->_key); //只能從根開始遍歷,性能損失,但是二分查找很快,損失不大(理想情況,BST只學習用)
                    cur->_key = tmp;
                    return true;
                } //有左右孩子的情況 
            } //找到了_繼續(xù)處理的過程
        }//循環(huán)找的過程
        //循環(huán)結束,說明沒找到
        return false;
    }//Erase [end]

    void InOrder() {
        _InOrder(_root);
        std::cout << std::endl;
    }

    bool InsertR(const K& key) {
        _InsertR(_root, key);
    }

    bool EraseR(const K& key) {
        return _EraseR(_root,key);
    }

private:

    //此處返回值不能使用指針引用,雖然一定情況下可以使用(不推薦),至少目前不能引用空值.
    Node* Copy(const Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* newRoot = new Node(root->_key);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }

    //用不用引用無所謂,好習慣做到底
    //(析構子節(jié)點時,父節(jié)點兩個成員會成為垂懸指針,但是接下來父親也要析構了,指針變量也隨之回收)
    void Destroy(Node*&root) {
        if (root == nullptr) {
            return ;
        }
        Destroy(root->_left);
        Destroy(root->_right);

        std::cout<_key<<" ";
        delete root; //釋放加自動置空
    }

    //練習遞歸+引用 -- 代碼更加簡潔
    bool _EraseR(Node*& root, const K&key) {
        //走到空,說明沒找到,返回false
        if (root == nullptr) {
            return false;
        }

        //大于走右邊,小于走左邊
        if (key > root->_key) {
            return _EraseR(root->_right,key);
        }
        else if(key_key) {
            return _EraseR(root->_left,key);
        }
        //找到了
        else {
            if (root->_left == nullptr) {
                Node* del = root;
                root = root->_right;
                delete del;
                return true;
            }
            else if (root->_right == nullptr) {
                Node* del = root;
                root = root->_left;
                delete del;
                return true;
            }
            //有左右孩子
            else {
                Node* leftMax = root->_left;
                //找左子樹最大結點
                while (leftMax->_right) {
                    leftMax = leftMax->_right;
                }
                std::swap(root->_key, leftMax->_key);
                return _EraseR(root->_left, key);    //直接從左孩子開始遞歸刪除.
            }
        }

    }

    //練習遞歸+引用指針的玩法,僅練習
    bool _InsertR(Node*& root, const K& key) { //引用的妙用,跨棧幀直接訪問實參
        if (root == nullptr) {
            root == new Node(key);
            return true;
        }
        if (key == root->_key) return false;
        return (key > root->_key) ? _InsertR(root->_right, key) : _InsertR(root->_left, key);
    }

    void _InOrder(Node* root) {
        if (root == nullptr)  return;
        _InOrder(root->_left);
        std::cout << root->_key << " ";
        _InOrder(root->_right);
    }

private:
    BSTreeNode* _root = nullptr;
};

test.cc

void test() {
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    BSTree bst;
    for (int i : a) {
        bst.Insert(i);
    }
    bst.InOrder();

    ////Find
    //std::cout << std::boolalpha << bst.Find(8) << std::endl; //true
    //std::cout << std::boolalpha << bst.Find(9) << std::endl; //false

    BSTree cp(bst);
    cp.InOrder();

    //測試兩孩子的三種情況即可
    bst.Erase(8);  //1. 要刪除的結點的右子樹的最小結點恰好是要刪除結點的右孩子.
    bst.Erase(10); //2. 要刪除的結點的右子樹的最小結點沒有右孩子
    bst.Insert(5); //構造有右孩子的最小結點
    bst.Erase(3);  //3. 要刪除的結點的右子樹的最小結點有右孩子
    bst.Erase(4);
    bst.Erase(7);
    bst.Erase(1);
    bst.Erase(14);
    bst.Erase(13);
    bst.Erase(6);
    bst.Erase(5);
    bst.InOrder();

    //禁止顯式調用析構函數(shù) --> 雙重釋放
    //bst.~BSTree();
    //cp.~BSTree();
    
}

int main() {
    test();
}