查找-二叉樹搜索樹

1 思想

二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹： 1.若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值； 2.若任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值； 3.任意節點的左、右子樹也分別為二叉查找樹。 4.沒有鍵值相等的節點（no duplicate nodes）。 複雜度: 插入和查找的時間複雜度均為O(logN), 最壞為O(N)

2 插入

1. 如果當前結點是null，則創建新結點返回。
2. 如果插入結點比當前結點值大，則插入其右孩子結點中。
3. 如果插入結點比當前結點值小，則插入其左孩子結點中。
4. 複雜度: 平均 O(logn) 最壞O(n)

<code>public Tree insert(Tree root, int val) {
     if (root == null) {
         return new Tree(val);
     }
     if (val == root.val) {
         return root;
     } else if (val > root.val) {
         root.right = insert(root.right, val);
     } else {
         root.left = insert(root.left, val);
     }
     return root;
 }
/<code>

3 查找

3.1 某個值

思想:查找方式有點類型二分查找方法，知識這裡採用的樹結構進行存儲。首先與根結點進行判斷:

1. 如果當前結點為null，則直接放回Null。
2. 如果當前結點值與查找值相同則返回當前結點.
3. 如果當前結點值小於查找值，則遞歸地到當前結點的右孩子查找
4. 如果當前結點值大於查找值，則遞歸地到當前結點的左孩子查找。 時間複雜度: 平均O(logn) 最壞O(n)

<code>public Tree search(Tree root, int val) {
 if(root == null) {
     return null;
 }
 if(root.val == val) {
     return root;
 } else if(root.val > val) {
     return search(root.left, val);
 } else {
     return search(root.right, val);
 } 

}/<code>

3.2 查找最小值

思想:根據二叉搜索樹的特點，最小結點都是在最左結點上或者如果根結點無左孩子便是其本身.

<code>public Tree min(Tree root) {
    if(root == null) {
        return null;
    }
    if (root.left != null) {
        return min(root.left);
    }
    return root;
}/<code>

3.3 查找最大結點

思想: 同最小結點。

<code>public Tree max(Tree root) {
    if(root == null) {
        return null;
    }
    if (root.right != null) {
        return max(root.right);
    }
    return root;
}/<code>

4 刪除

4.1 刪除最小結點

思想:找到根結點最左結點，如果其不存在右孩子則直接刪除，否則用右孩子替換最左結點。需要注意的是根結點可能為null和不存在做孩子的情況。

<code>public Tree deleteMin(Tree root) {
    if(root == null) {
        return null;
    }
    if(root.left != null) {
        root.left = deleteMin(root.left);
    } else if (root.right != null) {
        return root.right;
    }
    return null;
}/<code>

4.2 刪除最大結點

思想: 與刪除最小結點類型，根據二叉搜索樹的特性，最大結點是根結點的最右孩子。所以只要找到最右孩子結點，其存在左結點的話就用左結點替換否則直接刪除.

<code>public Tree deleteMax(Tree root) {
    if(root == null) {
        return null;
    }
    if(root.right != null) {
        root.right = deleteMax(root.right);
    } else if(root.left != null) {
        return root.left;
    }
    return null;
}/<code>

4.3 刪除某個結點

思想:要刪除一個結點首先需要找到該結點的位置，採用上面的查找方式進行查找。找到結點後就是刪除的問題的，可以按照下面的策略進行刪除。

1. 如果一個結點無左孩子和右孩子，那麼就可以直接刪除
2. 如果只存在一個孩子結點，則用孩子結點替換。
3. 如果存在兩個孩子結點，那麼可以用其左孩子最大的結點或右孩子最小結點替換，並刪除最左孩子結點或最右孩子結點。

<code>public Tree delete(Tree root, int val) {
    if(root == null) {
        return null;
    }
    if(root.val == val) {
        if(root.left == null && root.right == null) {
            return null;
        } else if(root.left!= null && root.right != null) {
            Tree leftBig = max(root.left);
            root.val = leftBig.val;
            root.left = delete(root.left, leftBig.val);
        } else if(root.left != null){
            return root.left;
        } else {
            return root.right;
        }
    } else if(root.val < val) {
        root.right = delete(root.right, val);
    } else {
        root.left = delete(root.left, val);
    }
    return root;
}/<code>

參考: http://www.cnblogs.com/vamei/archive/2013/03/17/2962290.html http://blog.jobbole.com/79305/

閱讀更多 醉人Ryu 的文章

關鍵字: 不完美媽媽 空樹 二叉樹