資料結構-Binary Search Tree 二元樹

A data structure that consists of nodes in a parent/child relationship.

樹跟鏈結的差異

List: linear
Trees: none linear

二元樹 Binary Search Tree

每個父節點最多有兩個子節點，每個父節點左邊的子節點會比自己小，右邊的子節點會比自己大。

Big O of BST

不保證
Searching — O(logn)
Insertion — O(logn)

定義節點 Node

定義節點 Node 的 class，再去定義 Singly linked list 的 class。

定義 Binary Search Tree

🎰 接著實作尋訪 & 插入新節點

700. Search in a Binary Search Tree

var searchBST = function(root, val) {
    if(!root) return null;
    let current = root;
    while(current) {
        if (current.val > val) {
            current = current.left;
        } else if (current.val <val) {
            current = current.right;
        } else {
            return current;
        }
    }
    return null
};

找尋值，首先確認樹不是空的。接著把 root 設定給 current 變數，當 current 存在時，就去和要找的數字 val 比較。如果 val 比較小的話，代表在節點的左方，反之亦然。如果一樣的話，代表找到答案。

701. Insert into a Binary Search Tree

var insertIntoBST = function(root, val) {
    let newNode = new TreeNode(val);
    if(root == null) {
        root = newNode;
        return root;
    }
    
    let current = root;
    while(true) {
        if (val < current.val) {
            if(current.left == null) {
                current.left =  new TreeNode(val);
                return root
            } else {
                current = current.left
            }
        } else if (val > current.val) {
            if(current.right == null) {
                current.right = new TreeNode(val);
                return root
            } else {
                current = current.right
            }
        }
    } 
};

如果一開始的樹是空的，設定一個節點給它即完成。如果有節點的話，去判斷節點是否比要插入的值大，大的話往左，小的話往右。走到最底層，設定一個新的節點給該值，最後返回 root。

🚪 前往題目：LeetCode-Binary Search Tree二元樹

📐✏️ 📏

若有任何錯誤請在下方留言～🙏 Thanks!