搜索樹的概念

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

1. 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
2. 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
3. 它的左右子樹也分別為二叉搜索樹
   下圖就是一棵二叉搜索樹，可以對應上面性質加深理解：
   

查找操作

實作思想：

實作代碼：

// O(樹的高度)
 public boolean find(int key) {
        Node current = root;
        while (current != null) {
            if (key == current.key) {
                return true;
            } else if (key < current.key) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        return false;
    }

插入操作

實作思想：

1. 如果樹為空樹，即根 == null，直接插入
2. 如果不時空樹，按照查找邏輯確定插入位置，插入新節點，這里需要引入兩個變數

實作代碼：

// O(樹的高度)
 public void insert(int key) {
        if (root == null) {
            root = new Node(key);
            return;
        }
        Node parent = null;
        Node current = root;
        while (current != null) {
            if (key == current.key) {
                throw new RuntimeException("BST 中不允許重復的 key: " + key);
            } else if (key < current.key) {
                parent = current;
                current = current.left;
            } else {
                parent = current;
                current = current.right;
            }
        }

        // 1. 把關鍵字裝入結點中
        Node node = new Node(key);
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
    }

洗掉操作

設待洗掉節點為cur，待洗掉節點的雙親節點為parent
有以下三種情況：

實作代碼：

  // O(樹的高度)
    public boolean remove(int key) {
        Node parent = null;
        Node current = root;
        while (current != null) {
            if (key == current.key) {
                // 洗掉 current 中的 key
                removeNode(parent, current);
                return true;
            } else if (key < current.key) {
                parent = current;
                current = current.left;
            } else {
                parent = current;
                current = current.right;
            }
        }

        return false;
    }

    // O(1)
    private void removeNode(Node parent, Node current) {
        if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (current == parent.left) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (current == parent.left) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else {
            Node goat = current.right;
            Node goatParent = current;
            while (goat.left != null) {
                goatParent = goat;
                goat = goat.left;
            }

            // 替換
            current.key = goat.key;
            // 洗掉 goat 結點
            if (goatParent == current) {
                goatParent.right = goat.right;
            } else {
                goatParent.left = goat.right;
            }
        }
    }

改的操作

改的操作和查一模一樣，只不過在找到目標節點之后修改它的數值即可，