二叉查找樹實現原理分析

Vir1632 7年前發布 | 64K 次閱讀 二叉樹 算法

引言

二叉查找樹是一種能將鏈表插入的靈活性和有序數組查找的高效性結合起來的一種重要的數據結構，它是我們后面學習紅黑樹和AVL樹的基礎，本文我們就先來看一下二叉查找樹的實現原理。

二叉查找樹的定義

二叉查找樹最重要的一個特征就是：每個結點都含有一個 Comparable 的鍵及其相關聯的值，該結點的鍵要大于左子樹中所有結點的鍵，而小于右子樹中所有結點的鍵。

下圖就是一個典型的二叉查找樹，我們以結點 E 為例，可以觀察到，左子樹中的所有結點 A 和 C 都要小于 E ，而右子樹中所有的結點 R 和 H 都要大于結點 E 。

二叉查找樹

在實現二叉查找樹中相關操作之前我們先要來定義一個二叉查找樹，由于Java中不支持指針操作，我們可以用內部類 Node 來替代以表示樹中的結點，每個Node對象都含有一對鍵值(key和val)，兩條鏈接(left和right)，和子節點計數器(size)。另外我們還提前實現了 size() ,  isEmpty() 和 contains() 這幾個基礎方法，三種分別用來計算二叉樹中的結點數目，判斷二叉樹是否為空，判斷二叉樹中是否含有包含指定鍵的結點。

public class BST<Key extends Comparable<Key>, Value> {
    private Node root;             // root of BST
    private class Node {
        private Key key;           // sorted by key
        private Value val;         // associated data
        private Node left, right;  // left and right subtrees
        private int size;          // number of nodes in subtree
        public Node(Key key, Value val, int size) {
            this.key = key;
            this.val = val;
            this.size = size;
        }
    }
    // Returns the number of key-value pairs in this symbol table.
    public int size() {
        return size(root);
    }
    // Returns number of key-value pairs in BST rooted at x.
    private int size(Node x) {
        if(x == null) {
            return 0;
        } else {
            return x.size;
        }
    }
    // Returns true if this symbol table is empty.
    public boolean isEmpty() {
        return size() == 0;
    }
    // Returns true if this symbol table contains key and false otherwise.
    public boolean contains(Key key) {
        if(key == null) {
            throw new IllegalArgumentException("argument to contains() is null");
        } else {
            return get(key) != null;
        }
    }
}

查找和插入操作的實現

查找操作

我們先來看一下如何在二叉樹中根據指定的鍵查找到它相關聯的結點。查找會有兩種結果：查找成功或者不成功，我們以查找成功的情形來分析一下整個查找的過程。前面我們提到了二叉查找樹的一個重要特征就是：左子樹的結點都要小于根結點，右子樹的結點都要大于根結點。根據這一性質，我們從根結點開始遍歷二叉樹，遍歷的過程中會出現3種情況：

  1. 如果查找的鍵key小于根結點的key，說明我們要查找的鍵如果存在的話肯定在左子樹，因為左子樹中的結點都要小于根結點，接下來我們繼續遞歸遍歷左子樹。
  2. 如果要查找的鍵key大于根結點的key，說明我們要查找的鍵如果存在的話肯定在右子樹中，因為右子樹中的結點都要大于根節點，接下來我們繼續遞歸遍歷右子樹。
  3. 如果要查找的鍵key等于根結點的key，那么我們就直接返回根結點的val。

二叉樹查找流程圖

上面的操作我們利用遞歸可以非常容易的實現，代碼如下：

/**


    

  • Returns the value associated with the given key.
*
    • 

  • @param  key the key
    • 

  • @return the value associated with the given key if the key is in the symbol table
    • 

  • and null if the key is not in the symbol table
    • 

  • @throws IllegalArgumentException if key is null
*/
public Value get(Key key) {
 if(key == null) {

     throw new IllegalArgumentException("first argument to put() is null");

    
 } else {

     return get(root, key);

    
 }
}
private Value get(Node x, Key key) {
 if(x == null) {

     return null;

    
 } else {

     int cmp = key.compareTo(x.key);
 if(cmp < 0) {
     return get(x.left, key);
 } else if(cmp > 0) {
     return get(x.right, key);
 } else {
     return x.val;
 }

    
 }
}</code></pre> 

    插入操作
     

    如果理解了上面的查找操作，插入操作其實也很好理解，我們首先要找到我們新插入結點的位置，其思想和查找操作一樣。找到插入的位置后我們就將新結點插入二叉樹。只是這里還要加一個步驟：更新結點的size，因為我們剛剛新插入了結點，該結點的父節點，父節點的父節點的size都要加一。
     

     

    二叉樹插入流程圖
     

    插入操作的實現同樣有多種實現方法，但是遞歸的實現應該是最為清晰的。下面的代碼的思想和 get 基本類似，只是多了 x.N = size(x.left) + size(x.right) + 1; 這一步驟用來更新結點的size大小。
     

    /**
    • 

  • Inserts the specified key-value pair into the symbol table, overwriting the old
    • 

  • value with the new value if the symbol table already contains the specified key.
    • 

  • Deletes the specified key (and its associated value) from this symbol table
    • 

  • if the specified value is null.
*
    • 

  • @param  key the key
    • 

  • @param  val the value
    • 

  • @throws IllegalArgumentException if key is null
*/
public void put(Key key, Value val) {
 if(key == null) {

     throw new IllegalArgumentException("first argument to put() is null");

    
 }
 if(val == null) {

     delete(key);
 return;

    
 }
 root = put(root, key, val);
 // assert check(); // Check integrity of BST data structure.
}
private Node put(Node x, Key key, Value val) {
 if(x == null) {

     return new Node(key, val, 1);

    
 } else {

     int cmp = key.compareTo(x.key);
 if(cmp < 0) {
     x.left = put(x.left, key, val)
 } else if(cmp > 0) {
     x.right = put(x.right, key, val);
 } else {
     x.val = val;
 }
 // reset links and increment counts on the way up
 x.size = size(x.left) + size(x.right) + 1;
 return x;

    
 }
}</code></pre> 

    select與rank的實現
     

    select的實現
     

    上面我們的 get() 操作是通過指定的 key 去在二叉查找樹中查詢其關聯的結點，二叉查找樹的另外一個優點就是它可以一定程度上保證數據的有序性，所以我們可以較高效的去查詢第 n 小的數據。
     

    首先我們來思考一個問題：怎么知道一個二叉查找樹中小于指定結點的子結點的個數？這一點根據二叉查找樹的性質- 左子樹中的結點都要小于根結點 很容易實現，我們只需要統計左子樹的大小就行了。結合下面這幅圖，以查找二叉樹第4小的結點我們來看一下select操作的具體流程。
     

    依次遍歷二叉樹，我們來到了下圖中的 E 結點，E結點的左子樹有2個結點，它是二叉樹中第3小的結點，所以我們可以判斷出要查找的結點肯定在 E 結點的右子樹中。由于我們要查找第4小的結點，而E又是二叉樹中第3小的結點，所以我們要查找的這個結點接下來肯定要滿足一個特征：E的右子樹中只有0個比它更小的結點，即右子樹中最小的結點 H 。
     

     

    二叉樹select流程圖
     

    select的實現如下，實際就是根據左子樹的結點數目來判斷當前結點在二叉樹中的大小。
     

    /**
    • 

  • Return the kth smallest key in the symbol table.
*
    • 

  • @param  k the order statistic
    • 

  • @return the kth smallest key in the symbol table
    • 

  • @throws IllegalArgumentException unless k is between 0 and n-1
*/
public Key select(int k) {
 if (k < 0 || k >= size()) {

     throw new IllegalArgumentException("called select() with invalid argument: " + k);

    
 } else {

     Node x = select(root, k);
 return x.key;

    
 }
}
// Return the key of rank k.
public Node select(Node x, int k) {
 if(x == null) {

     return null;

    
 } else {

     int t = size(x.left);
 if(t > k) {
     return select(x.left, k);
 } else if(t < k) {
     return select(x.right, k);
 } else {
     return x;
 }

    
 }
}</code></pre> 

    rank就是查找指定的鍵key在二叉樹中的排名，實現代碼如下，思想和上面一致我就不重復解釋了。
     

    /**
    • 

  • Return the number of keys in the symbol table strictly less than key.
*
    • 

  • @param  key the key
    • 

  • @return the number of keys in the symbol table strictly less than key
    • 

  • @throws IllegalArgumentException if key is null
*/
public int rank(Key key) {
 if (key == null) {

     throw new IllegalArgumentException("argument to rank() is null");

    
 } else {

     return rank(key, root);

    
 }
}
public int rank(Key key, Node x) {
 if(x == null) {

     return 0;

    
 } else {

     int cmp = key.compareTo(x.key);
 if(cmp < 0) {
     return rank(key, x.left);
 } else if(cmp > 0) {
     return 1 + size(x.left) + rank(key, x.right);
 } else {
     return size(x.left);
 }

    
 }
}</code></pre> 

    刪除操作
     

    刪除操作是二叉查找樹中最難實現的方法，在實現它之前，我們先來看一下如何刪除二叉查找樹中最小的結點。
     

    為了實現 deleteMin() ，我們首先要找到這個最小的節點，很明顯這個結點就是樹中最左邊的結點 A ，我們重點關注的是怎么刪除這個結點 A 。在我們下面這幅圖中結點 E 的左子樹中的兩個結點 A 和 C 都是小于結點E的，我們只需要將結點E的左鏈接由A變為C即可，然后A就會自動被GC回收。最后一步就是更新節點的size了。
     

     

    二叉樹deletetMin流程圖
     

    具體的實現代碼如下：
     

    /**
    • 

  • Removes the smallest key and associated value from the symbol table.
*
    • 

  • @throws NoSuchElementException if the symbol table is empty
*/
public void deleteMin() {
 if (isEmpty()) {

     throw new NoSuchElementException("Symbol table underflow");

    
 } else {

     root = deleteMin(root);
 // assert check(); // Check integrity of BST data structure.

    
 }
}
private Node deleteMin(Node x) {
 if(x.left == null) {

     return x.right;

    
 } else {

     x.left = deleteMin(x.left);
 x.size = size(x.left) + size(x.right) + 1;
 return x;

    
 }
}</code></pre> 

    刪除最大的結點也是一個道理，我就不重復解釋了：
     

    /**
    • 

  • Removes the largest key and associated value from the symbol table.
*
    • 

  • @throws NoSuchElementException if the symbol table is empty
*/
public void deleteMax() {
 if (isEmpty()) {

     throw new NoSuchElementException("Symbol table underflow");

    
 } else {

     root = deleteMax(root);
 // assert check(); // Check integrity of BST data structure.

    
 }
}
private Node deleteMax(Node x) {
 if (x.right == null) {

     return x.left;

    
 } else {

     x.right = deleteMax(x.right);
 x.size = size(x.left) + size(x.right) + 1;
 return x;

    
 }
}</code></pre> 

    接下來我們結合下圖來一步步完整地看一下整個刪除操作的過程，首先還是和上面一樣我們要找到需要刪除的結點 E ，然后我們要在E的右子樹中找到最小結點，這里是 H ，接下來我們就用 H 替代 E 就行了。為什么可以直接用 H 替代 E 呢？因為 H 結點大于 E 的左子樹的所有結點，小于 E 的右子樹中的其它所有結點，所以這一次替換并不會破壞二叉樹的特性。
     

     

    二叉樹delete流程圖
     

    實現代碼如下，這里解釋一下執行到了 // find key 后的代碼，這個時候會出現三種情況：
     

       

    1. 結點的右鏈接為空，這個時候我們直接返回左鏈接來替代刪除結點。
      2.  

    2. 結點的左鏈接為空，這個時候返回右鏈接來替代刪除結點。
      3.  

    3. 左右鏈接都不為空的話，就是我們上圖中的那種情形了。
      4.  

     

    /**
    • 

  • Removes the specified key and its associated value from this symbol table
    • 

  • (if the key is in this symbol table).
*
    • 

  • @param  key the key
    • 

  • @throws IllegalArgumentException if key is null
*/
public void delete(Key key) {
 if (key == null) {

     throw new IllegalArgumentException("argument to delete() is null");

    
 } else {

     root = delete(root, key);
 // assert check(); // Check integrity of BST data structure.

    
 }
}
private Node delete(Key key) {
 if(x == null) {

     return null;

    
 } else {

     int cmp = key.compareTo(x.key);
 if(cmp < 0) {
     x.left = delete(x.left, key);
 } else if(cmp > 0) {
     x.right = delete(x.right, key);
 } else {
     // find key
     if(x.right == null) {
         return x.left;
     } else if(x.left == null) {
         return x.right;
     } else {
         Node t = x;
         x = min(t.right);
         x.right = deleteMin(t.right);
         x.left = t.left;
     }
 }
 // update links and node count after recursive calls
 x.size = size(x.left) + size(x.right) + 1;
 return x;

    
 }
}</code></pre> 

    floor和ceiling的實現
     

    floor的實現
     

    floor() 要實現的就是向下取整，我們來分析一下它的執行流程：
     

       

    1. 如果指定的鍵key小于根節點的鍵，那么小于等于key的最大結點肯定就在左子樹中了。
      2.  

    2. 如果指定的鍵key大于根結點的鍵，情況就要復雜一些，這個時候要分兩種情況：1>當右子樹中存在小于等于key的結點時，小于等于key的最大結點則在右子樹中；2>反之根節點自身就是小于等于key的最大結點了。
      3.  

     

     

    二叉樹floor流程圖
     

    具體實現代碼如下：
     

    /**
    • 

  • Returns the largest key in the symbol table less than or equal to key.
*
    • 

  • @param  key the key
    • 

  • @return the largest key in the symbol table less than or equal to key
    • 

  • @throws NoSuchElementException if there is no such key
    • 

  • @throws IllegalArgumentException if  key is null
*/
public Key floor(Key key) {
 if (key == null) {

     throw new IllegalArgumentException("argument to floor() is null");

    
 }
 if (isEmpty()) {

     throw new NoSuchElementException("called floor() with empty symbol table");

    
 }
 Node x = floor(root, key);
 if (x == null) {

     return null;

    
 } else {

     return x.key;

    
 }
}
private Node floor(Node x, Key key) {
 if (x == null) {

     return null;

    
 } else {

     int cmp = key.compareTo(x.key);
 if(cmp == 0) {
     return x;
 } else if(cmp < 0) {
     return floor(x.left, key);
 } else {
     Node t = floor(x.right, key);
     if(t != null) {
         return t;
     } else {
         return x;
     }
 }

    
 }
}</code></pre> 

    ceiling的實現
     

    ceiling() 則與 floor() 相反，它做的是向下取整，即找到大于等于key的最小結點。但是兩者的實現思路是一致的，只要將上面的左變為右，小于變為大于就行了：
     

    /**
    • 

  • Returns the smallest key in the symbol table greater than or equal to {@code key}.
*
    • 

  • @param  key the key
    • 

  • @return the smallest key in the symbol table greater than or equal to {@code key}
    • 

  • @throws NoSuchElementException if there is no such key
    • 

  • @throws IllegalArgumentException if {@code key} is {@code null}
*/
public Key ceiling(Key key) {
 if(key == null) {

     throw new IllegalArgumentException("argument to ceiling() is null");

    
 }
 if(isEmpty()) {

     throw new NoSuchElementException("called ceiling() with empty symbol table");

    
 }
 Node x = ceiling(root, key);
 if(x == null) {

     return null;

    
 } else {

     return x.key;

    
 }
}
private Node ceiling(Node x, Key key) {
 if(x == null) {

     return null;

    
 } else {

     int cmp = key.compareTo(x.key);
 if(cmp == 0) {
     return x;
 } else if(cmp < 0) {
     Node t = ceiling(x.left, key);
     if (t != null) {
         return t;
     } else {
         return x;
     }
 } else {
     return ceiling(x.right, key);
 }

    
 }
}</code></pre> 

     
     
     
     

    來自：http://www.importnew.com/24059.html
     

     
    •
 本文由用戶 Vir1632 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！