iT邦幫忙

0

【小馬的資結演算法秘笈】(13) Binary Search Tree,方便二分查找的樹

哈囉~ 大家好,
今天跟大家介紹一種很有用的資料結構- Binary Search Tree(簡稱BST),
BST是一種特別的binary tree,它滿足二個特性:

  • 左邊子樹的所有節點都比root來的小
  • 右邊子樹的所有節點都比root來的大

例如下圖所示就是一個BST:
https://ithelp.ithome.com.tw/upload/images/20200520/20117114geTEEiicdc.png
(圖片來源: Geeksforgeeks- Binary Search Tree)

這種結構有一個好處,在樹很「平衡」的狀況下,
(所謂「平衡」指的是每一層左邊的樹跟右樹的樹的節點數量都差不多),
那麼要查找一個數有沒有在這棵樹裡面,只需要O(log n)的時間

比如說上樹要找「6」有沒有在這棵樹裡面呢?
首先從root出發,把目標數字跟root上的「8」比一下,
6比8小,所以6只有可能在左邊的樹,不會在右邊的樹,
一下子就少搜索一半的可能

這個技巧非常像一開始在【小馬的資結演算法秘笈】(1)二分搜索法所提過的二分搜索,
在一個有排序過的陣列中找東西,
也是可以直接從陣列的一半去找

那BST和一般的排序陣列差在哪裡呢?
差別就在於一般的排序陣列不支援動態的插入及刪除元素

如何在BST裡插入、刪除元素?

由於BST是個蠻經典的資料結構,
目前網路上可以查到的資料蠻多的,
暫先附上參考資料:

習題: 找出BST第k小的元素

參考題目: leetcode- 230. Kth Smallest Element in a BST

既然學了BST,就順便練一下相關的題目,
給你一個BST,請找出此樹中第k小的元素,
此題有一個簡單的想法,
BST的特性是如果對它做inorder traversal的話,
那得到的數字便是排序好的,
因為小馬的策略便是直接對這棵樹做inorder traversal,
將結果存進陣列,
再直接回傳陣列index k-1的數字即可(找index k-1是因為陣列的index從0開始)

程式碼如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> arr; 
    int kthSmallest(TreeNode* root, int k) {
        if(arr.empty()){
            inorder(root);
        }
        return arr[k-1];
    }
    
    void inorder(TreeNode* root) {
        if (root){
            inorder(root->left);
            arr.push_back(root->val);
            inorder(root->right);            
        }
    }
};

尚未有邦友留言

立即登入留言