初識二叉搜尋樹

寫在前面

我們今天來談一個比較簡單的話題，算是二叉樹的進階，但是裡面的内容我們都是說過了，主要是為了後面的比較難得二叉樹做準備，先來看看今天的内容吧.

搜尋二叉樹

這個是我們學習下面AVL樹,紅黑樹的基礎,今天的就比較簡單了.

什麼是搜尋二叉樹

這個也可以叫二叉搜尋樹,反正名字是不重要的,關鍵是它的條件要求.二叉搜尋樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:

若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
它的左右子樹也分别為二叉搜尋樹

可以這麼說,一般二叉搜尋樹的中樹節點裡面的值是不相等的,當然我們也可以存放相等的,那麼就變成的另外的一棵樹了,這是在後面談的.

搜尋樹的時間複雜度

大家看一次名字你就會發現,二叉搜尋樹,肯定主要的内容是搜尋啊,這裡我們看一下他們是如何搜尋的.

我們拿到一個值,去和根節點去比,入過比他大,就去右子樹中找,比他小,就去左子樹中找,相等就找到了,這就是二叉搜尋的流程.

那麼我想問問,它的時間複雜度是多少?大家一看,這不就是查找樹的高度次嗎,應該是O(lgN)吧?記住,這是搜尋二叉樹最大為誤區,它的時間複雜度是 O(N),主要是這個樹太過正常,如果是一顆不正常的樹,你就會發現了.

二叉搜尋的周遊

要是仔細的朋友,你就會發現,二叉搜尋樹的中序周遊就是一個升序的數組,這一點也是二叉搜尋樹的特點.

實作二叉搜尋樹

我們先來實作一個簡單的二叉搜尋樹,先來看看它的底層是什麼樣的,後面來更好的了解它的應用.

準備節點

這個倒是挺簡單的,一般而言,想這些節點的都是用struct來聲明和定義類的,這裡我們還用了模闆,不過也沒有什麼可以說的.

template<class T>
struct BSTreeNOde
{
    public:
    BSTreeNOde(const T& x = T())
        :left(nullptr)
            , right(nullptr)
            , _key(x)
        {
        }

    BSTreeNOde* left;
    BSTreeNOde* right;
    T _key;
};

二叉搜尋樹

現在我們就可以開始它的是實作了,我們發現,隻需要準備一個成員變量來存放根節點就可以了.

template<class T>
class BSTree
{
 public:
    typedef BSTreeNOde<T> Node; // 名字有點 長
 public:
    BSTree()
        :_root(nullptr)
    {}

 private:
    Node* _root;
};

中序周遊

我們先來一個中序周遊,主要是為了後面的插入删除等好驗證.

大家先說一下,下面的代碼可以嗎?

void inorder(Node* root)
{
    if (root == nullptr)
        return;
    inorder(root->left);
    cout << root->_key << " ";
    inorder(root->right);
}

看着挺行的,裡面的考慮的也比較周全,可惜存在一個問題,我們在類外如何調用這個函數要知道,我們是無法拿到根節點的啊,除非你再寫一個得到根節點的函數.

這裡我們需要在把這個函數封裝一層,這樣為了更好的使用,下面的才是很可以的

public:    
    void inorder()
    {
        _inorderR(_root);
    }

private:
    void _inorderR(Node* root)
    {
        if (root == nullptr)
            return;
        _inorderR(root->left);
        cout << root->_key << " ";
        _inorderR(root->right);
    }

插入資料

從這裡開始就可以變得難一些了,我們需要考慮的事情就有點多了.

這裡面存在一個難點,就是我們找到了一個可以插入的玩位置,如何确定父節點,是以這裡需要找一個節點記錄夫節點,這樣才可以.

bool insert(const T& val)
{
    // 頭一次 插入
    if (_root == nullptr)
    {
        _root = new Node(val);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur != nullptr)
    {
        if (val > cur->_key)
        {
            parent = cur;
            cur = cur->right;
        }
        else if (val < cur->_key)
        {
            parent = cur;
            cur = cur->left;
        }
        else
        {
            // 這裡 我們不允許 插入相同的 值
            return false;
        }
    }

    // 判斷一些插入 左子樹  還是  右子樹
    if (parent->_key < val)
        parent->right = new Node(val);
    else
        parent->left = new Node(val);

    return true;
}

我們先來驗證一下,看看是不是插入成功了.

int main()
{
  BSTree<int> b;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  int sz = sizeof(a) / sizeof(int);

  for (int i = 0; i < sz; i++)
  {
    b.insert(a[i]);
  }
  b.inorder();
  cout << endl;
  // 插入個 相同的
  b.insert(8);
  b.inorder();

  return 0;
}

遞歸版本

這裡面遞歸版本應該是比較難了解,準确說遞歸的都很難,我們這裡來解釋一下吧,這裡你就會發現引用的好處.

public:
    bool insertR(const T& val)
    {
        return _insertR(_root, val);
    }

private:

    bool _insertR(Node*& root, const T& val)
    {
        if (root == nullptr)
        {
            root = new Node(val);
        }

        // 
        if (val > root->_key)
            _insertR(root->right, val);
        else if (val < root->_key)
            _insertR(root->left, val);
        else
            return false;

        return true;
    }

我來解釋一下這個函數,主要是這個遞歸函數.

首先,我們先看最簡單的一種情況,第一次插入資料,那麼我們要修改的是_root,遞歸函數函數裡面存在的是root,不過不要擔心,要知道,我們傳入的是參數的别名,是以這裡我們可以直接修改.

那麼現在就存在下面的一個問題了,我們在其他位置插入資料,我們看一下過程

我們依次遞歸,直到我們編譯器找到root為空時,這樣就可以直接指派,因為root是引用,而且這個引用還确定;了我們插入的是左子樹還是右子樹.

這裡也來驗證一下.

int main()
{
  BSTree<int> b;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  int sz = sizeof(a) / sizeof(int);

  for (int i = 0; i < sz; i++)
  {
    b.insertR(a[i]);
  }
  b.inorder();
  return 0;
}

删除資料

删除資料是這裡面最難的,我們先來啃一下這個骨頭.删除資料分為下面四種情況,其中有着一種情況可以歸到其他兩種裡面的任何一種.

記住,即使是删除節點後,這棵二叉樹也應該是二叉搜尋樹.

删除節點無左子樹和右子樹
删除節點無左子樹
删除節點無右子樹
删除節點存在左子樹和右子樹

這裡面也就第四種情況比較困難,第一中可以歸納到下面的兩種的任意一種,這裡我們歸納到了無左子樹這種了.我們先解決前三中種情況.

先把函數的架構搭出來,我們需要一個節點記錄要删除節點的父親節點.

bool erase(const T& val)
{
    if (_root == nullptr)
        return false;
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur != nullptr)
    {
        if (val > cur->_key)
        {
            parent = cur;
            cur = cur->right;
        }
        else if (val < cur)
        {
            parent = cur;
            cur = cur->left;
        }
        // 找到了 要删除的節點了
        else
        {
            //  左子樹 為空  或者  左子樹  和  右子樹  都為空
            if (cur->left == nullptr)
            {
               
            }
            // cur 一個 右為空
            else if (cur->right == nullptr)
            {

            }
            // 左子樹  和  右子樹  都為空
            else
            {

            }
        }
    }
    return false;
}

沒有左子樹或者沒有左子樹和右子樹

// cur 左 右  左一個 為空 或者 都為空
if (cur->left == nullptr)
{
    // 首先 要判斷 删除的節點是 頭節點   這樣  parent = nullptr
    if (cur == _root)
    {
        _root = cur->left;
        delete cur;
        return true;
    }

    // 判斷 要删除的 節點  是 父節點的左子樹 還是 右子樹
    if (cur == 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->right;
        delete cur;
        return true;
    }

    if (cur == parent->left)
    {
        parent->left = cur->right;
    }
    else
    {
        parent->right = cur->right;
    }
    delete cur;
    return true;
}

既存在左子樹又存在右子樹,這個情況是二叉搜尋樹中最難的了,我們需要現象如何來删除這個節點.這裡存在兩個方法

找到要删除節點中左子樹中最大值的節點 ,交換節點的值删除它
找到要删除節點中右子樹中最小值的節點 ,交換節點的值删除它

這樣我們就可以删除我們想要的值了.我們這裡是找右節點中最小的值.

else
{
    Node*  minParent = cur;
    Node*  minRight = cur->right;
    while (minRight->left)
    {
        minParent = minRight;
        minRight = minRight->left;
    }
    // 交換 或者  直接覆寫
    std::swap(minRight->_key, cur->_key);

    // 删除 所在的節點
    if (minParent->left == minRight)
    {
        minParent->left = minRight->right;
    }
    else
    {
        minParent->right = minRight->right;
    }
    delete minRight;
}

到這裡我們就把删除給寫好了,.我們先來測試一下,後面再說遞歸的版本.

int main()
{
  BSTree<int> b;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  int sz = sizeof(a) / sizeof(int);

  for (int i = 0; i < sz; i++)
  {
    b.insertR(a[i]);
  }
  b.inorder();
  for (int e : a)
  {
    b.erase(e);
  }

  b.inorder();

  return 0;
}

遞歸版本

這裡面也是一個困難啊,和上面一個遞歸一樣,都使用的引用.這裡還需要分為三種情況,不過前提是需要找到删除的節點.

public:    
    bool eraseR(const T& val)
    {
        _eraseR(_root, val);
    }
private:
    bool _eraseR(Node*& root,const T& val)
    {

    }

這裡面還是分為四種情況,我們直接說吧,都挺簡單的,這裡面我們可以直接給root指派原因還是在于我們傳入的是引用,這個引用就是父節點的左子樹或者右子樹,而且還隻能唯一确定.

bool _eraseR(Node*& root,const T& val)
{
    if (root == nullptr)
    {
        return false;
    }
    if (root->_key > val)
    {
        _eraseR(root->left, val);
    }
    else if (root->_key < val)
    {
        _eraseR(root->right, val);
    }
    // 找到了
    else
    {
        // 還分為 四種 情況
        if (root->left == nullptr)
        {
            Node* cur = root;
            root = root->right;
            delete cur;
        }
        else if (root->right == nullptr)
        {
            Node* cur = root;
            root = root->left;
            delete cur;

        }
        else
        {
            Node* minRight = root->right;
            while (minRight->left != nullptr)
            {
                minRight = minRight->left;
            }
            // 這是一個好東西   
            swap(root->_key, minRight->_key);
            // 這裡 遞歸  删除  要知道 現在 val所在的節點 一定是 沒有左子樹的
            return _eraseR(root->right, val);
        }
        return true;
    }
    return false;
}

我們也來驗證一下吧.

int main()
{
  BSTree<int> b;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  int sz = sizeof(a) / sizeof(int);

  for (int i = 0; i < sz; i++)
  {
    b.insertR(a[i]);
  }
  b.inorder();
  for (int e : a)
  {
    b.eraseR(e);
    b.inorder();
    cout << endl;
  }

  b.inorder();

  return 0;
}

查找資料

這裡的就簡單了,我這裡也不啰嗦了,直接上代碼.

Node* find(const T& key)
{
    if (_root == nullptr)
        return nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (key > cur->_key)
        {
            cur = cur->right;
        }
        else if (key < cur->_key)
        {
            cur = cur->left;
        }
        else
        {
            return cur;
        }
    }
    return nullptr;
}

如果你要是這們寫這就有問題了,我們拿到了指針,這就意味者我們可以修改節點裡面的值,那就麻煩了,因為你不确定你修改過的值還是否構成搜尋二叉樹.

我們這裡改一下節點的值,用const修飾.

template<class T>
struct BSTreeNOde
{
    public:
    BSTreeNOde(const T& x = T())
        :left(nullptr)
            , right(nullptr)
            , _key(x)
        {
        }

    BSTreeNOde* left;
    BSTreeNOde* right;
    const T _key;
};

但是還是存在問題的 ,想一想,我們在删除資料的時候交換了節點的值,這就出現了另一個問題,因為const修飾的常量就不能被修改了,這裡我就不給出解決的代碼了,隻說下思路.我們還是用const修飾,交換節點的值改成交換節點,當然,他們原本的指向也應該合理的變化.

遞歸寫法

public:
    Node* findR(const T& key)
    {
        return _findR(_root, key);
    }
private:
    Node* _findR(Node* root,const T& key)
    {
        if (root == nullptr)
            return nullptr;

        if (key > root->_key)
            return _findR(root->right,key);

        else if (key < root->_key)
            return _findR(root->left, key);

        else
            return root;
    }

完善一下二叉樹搜尋樹

我們把它的拷貝構造等幾個函數給寫一下就可以了,這臉都是挺簡單的,而且說實話我們也不是太常用.

拷貝構造

我們完善一下代碼就可以了

private:
    Node* CopyTree(Node* root)
    {
        if (root == nullptr)
        {
            return nullptr;
        }
        Node* copyNode = new Node(root->_key);

        copyNode->left = CopyTree(root->left);
        copyNode->right = CopyTree(root->right);
        return copyNode;
    }
public:
    BSTree(const BSTree<T>& b)
        :_root(nullptr)
    {
            _root = CopyTree(b._root);
    }

析構函數

private:
    void DestoryTree(Node* root)
    {
        if (root == nullptr)
            return;
        DestoryTree(root->left);
        DestoryTree(root->right);
        delete root;
    }
public:
    ~BSTree()
    {
        DestoryTree(_root);
        _root = nullptr;
    }

operator=

BSTree<T>& operator=(BSTree b)
{
    swap(_root, b._root);
    return *this;
}

我們這裡來測試一下就好了,沒有什麼可以談的.

int main()
{
  BSTree<int> b1;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  int sz = sizeof(a) / sizeof(int);

  for (int i = 0; i < sz; i++)
  {
    b1.insertR(a[i]);
  }
  
  BSTree<int> b2(b1); // 拷貝構造
  BSTree<int> b3;
  b3 = b1; // operater = 

  b2.inorder();
  cout << endl;

  b3.inorder();
  cout << endl;

  return 0;
}

應用

相比較其他的,我這裡更想談談它的應用.

初識二叉搜尋樹

寫在前面

搜尋二叉樹

什麼是搜尋二叉樹

搜尋樹的時間複雜度

二叉搜尋的周遊

實作二叉搜尋樹

準備節點

二叉搜尋樹

中序周遊

插入資料

遞歸版本

删除資料

遞歸版本

查找資料

遞歸寫法

完善一下二叉樹搜尋樹

拷貝構造

析構函數

operator=

應用

K模型

KV模型

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希

初識二叉搜尋樹

寫在前面

搜尋二叉樹

什麼是 搜尋二叉樹

搜尋樹的時間複雜度

二叉搜尋的周遊

實作二叉搜尋樹

準備節點

二叉搜尋樹

中序周遊

插入資料

遞歸版本

删除資料

遞歸版本

查找資料

遞歸寫法

完善一下二叉樹搜尋樹

拷貝構造

析構函數

operator=

應用

K模型

KV模型

繼續閱讀

什麼是搜尋二叉樹