天天看點
傳回

查找與二叉樹

查找與二叉樹

我家園子有幾棵樹系列

  • 查找與二叉樹
    • 我家園子有幾棵樹系列
    • Preface
    • 查找
    • 二叉查找樹的實作
      • 定義資料結構
      • 中序周遊
      • 查找操作
      • 插入
      • 删除
        • 删除最小值
        • 複制(拷貝)删除
          • 步驟
      • Rank
    • 2-3查找樹
    • 總結

Preface

前面我們學習了基于線性表的資料結構，如數組，連結清單，隊列，棧等。現在我們要開始學習一種非線性的資料結構--樹(tree)，是不是很興奮呢！讓我們開始新的系列吧！

查找

先讓我們回憶一下線性表的查找，首先最暴力的方法就是做一個線性掃描，一一對比是不是要找的值。這麼做的時間複雜度顯而易見的是 O(N)，如表格第一行;更機智一點，我們采用二分法，首先将線性表排好順序，然後每次對比中間的值就好了，這樣做的時間複雜度就是 O(logN)，如表格第二行。但上面的做法都是利用的線性資料結構，而它有緻命的缺點;那就是進行動态的操作時，比如插入，删除;無法同時實作迅速的查找，隻能等重新排序以後再查，效率就低了很多，無法滿足日常需求(如下表)。這個時候我們的主角就閃亮登場了——二叉查找樹(BST) 。

圖源

查找與二叉樹

表格

二叉查找樹的實作

首先我放幾張圖說明一下什麼是二叉樹，樹的高度，深度等等，詳細的介紹我已經放在這裡，有興趣的話也可以看看别人的部落格。

圖源 轉載學習，如侵權則聯系我删除！

查找與二叉樹
查找與二叉樹

深度

廢話不多說我們開始實作一顆二叉查找樹(BST)吧！

[注] 為了友善了解大部分代碼都提供了遞歸實作！

定義資料結構 

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;
        }
    }

    /**
     * Initializes an empty symbol table.
     */
    public BST() {}
    /**
     * Returns the number of key-value pairs in this symbol table.
     * @return the number of key-value pairs in this symbol table
     */
    public int size() {
        return size(root);
    }

    // return number of key-value pairs in BST rooted at x
    private int size(Node x) {
        if (x == null) return 0;
        else return x.size;
    }

}

中序周遊

我們知道二叉查找樹的任一個節點，他的左子結點比他小，右子節點比他大，哈，那麼我們隻要進行一波中序周遊就可以完成資料的排序啦！

/***************************************************************************
     * 中序周遊，非遞歸版本
     ***************************************************************************/
    public Iterable<Key> keys() {
        Stack<Node> stack = new Stack<Node>();
        Queue<Key> queue = new Queue<Key>();
        Node x = root;
        while (x != null || !stack.isEmpty()) {
            if (x != null) {
                stack.push(x);
                x = x.left;
            } else {
                x = stack.pop();
                queue.enqueue(x.key);
                x = x.right;
            }
        }
        return queue;
    }
    /************************************************************************
    * 中序周遊，遞歸列印
    ************************************************************************/
    public	void inOrder(Node* root) {
 		if (root == null) return;
  		inOrder(root.left);
  		print root // 此處為僞代碼，表示列印 root 節點
  		inOrder(root.right);
}

查找操作 

/************************************************************************
    * 非遞歸
    ************************************************************************/
    Value get(Key key){
        Node x = root;
        while(x != null){
            int cmp =  key.compareTo(x.key);
            if(cmp<0)
                x = x.left;
            else if(cmp>0) 
                x = x.right;
            else return 
                x.value;
        }
        return null;
    }
    /************************************************************************
    * 遞歸
    ************************************************************************/
    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if (x == null) return null;
        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;
    }

插入 

/************************************************************************
* 非遞歸
************************************************************************/
public void put(Key key, Value val) {
        Node z = new Node(key, val);
        if (root == null) {
            root = z;
            return;
        }

        Node parent = null, x = root;
        while (x != null) {
            parent = x;
            int cmp = key.compareTo(x.key);
            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else {
                x.val = val;
                return;
            }
        }
        int cmp = key.compareTo(parent.key);
        if (cmp < 0)
            parent.left = z;
        else
            parent.right = z;
    }
/************************************************************************
* 遞歸版本
************************************************************************/
public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    private Node put(Node x, Key key, Value value) {
        if (x == null)
            return new Node(key, value, 1);
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = put(x.left, key, value);
        else if (cmp > 0)
            x.right = put(x.right, key, value);
        else
            x.value = value;
        x.size = 1 + size(x.left) + size(x.right);
        return x;
    }

删除

删除有兩種方式，一種是

合并删除

，另一種是

複制删除

，這裡我主要講第二種，想了解第一種可以點這裡

删除最小值

在正式的删除之前讓我們先熱身一下，看看怎麼删除一棵樹的最小值(如圖)。

步驟

  • 我們先找到最小值，即不斷查找節點的左子節點，若無左節點，那他就是最小值。
  • 找到最小的節點後，傳回他的右子節點給上一層，最小節點會被GC機制回收
  • 因為用的是遞歸方法，是以依次更新節點數量
查找與二叉樹
public void deleteMin(){
    root = deleteMin(root);
}

private Node deleteMin(Node x){
    if (x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

複制(拷貝)删除

在說複制删除之前，我們需要先熟悉二叉查找樹的前驅和後繼（根據中序周遊衍生出來的概念）。

  • 前驅：A節點的前驅是其左子樹中最右側節點。
  • 後繼：A節點的後繼是其右子樹中最左側節點。
查找與二叉樹

BSTcopyDelete

上圖是複制删除的原理，我們既可以用前驅節點 14 代替，又可以用後繼節點 18 代替。

步驟
查找與二叉樹

BSTcDelete

如圖所示，我們分為四個步驟

  1. 将指向即将被删除的節點的連結儲存為t;
  2. 将 x 指向它的後繼節點

    min(t.right)

     ;
  3. 将 x 的右連結(原本指向一顆所有節點都大于 x.key 的二叉查找樹) 指向

    deleteMin(t.right)

     ，也就是在删除後所有節點仍然都大于 x.key 的子二叉查找樹。
  4. 将 x 的左連結(本為空) 設為 t.left 
public void delete(Key key){
    root = delete(root,key);
}
private Node min(Node x){
    if(x.left == null) return x;
    else return min(x.left);
}
private Node delete(Node x, Key key){
    if(x==null) return null;
    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{
        if(x.right == null) return x.left;
        if(x.left == null) return x.right;
        Node t = x;
        x = min(t.right);
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

在前面的代碼中，我們總是删除node中的後繼結點，這樣必然會降低右子樹的高度，在前面中我們知道，我們也可以使用前驅結點來代替被删除的結點。是以我們可以交替的使用前驅和後繼來代替被删除的結點。

J.Culberson從理論證明了使用非對稱删除, IPL(内部路徑長度)的期望值是 O(n√n), 平均查找時間為 O(√n),而使用對稱删除, IPL的期望值為 O(nlgn),平均查找時間為 O(lgn)。

Rank

查找節點 x 的排名

public int rank(Key key){
    return rank(key, root);
}

private int rank(Key key, Node x){
    // 傳回以 x 為根節點的子樹中小于x.key的數量
    if(x == null) return 0;
    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);
}

2-3查找樹

通過前面的分析我們知道，一般情況下二叉查找樹的查找，插入，删除都是 O(lgn)的時間複雜度，但是二叉查找樹的時間複雜度是和樹的高度是密切相關的，如果我們以升序的元素進行二叉樹的插入，我們會發現，此時的二叉樹已經退化成連結清單了，查找的時間複雜度變成了 O(n)，這在性能上是不可容忍的退化！那麼我們該怎麼解決這個問題呢？

答案相信大家都知道了，那就是建構一顆始終平衡的二叉查找樹。那麼有哪些平衡二叉查找樹呢？如何實作？

這些我們留到下節再講。

總結

這一節我們學會了使用非線性的資料結構--二叉查找樹來高效的實作查找，插入，删除操作。分析了它的性能，在随機插入的情況下，二叉查找樹的高度趨近于

2.99lgN

,平均查找時間複雜度為

1.39lgN(2lnN)

，而且在升序插入的情況下，樹會退化成連結清單。這些知識為我們後面學習2-3查找樹和紅黑樹打下了基礎。

DataStructurealgorithm
上一篇: 睿象雲高科 | 淺談告警管理能力成熟度模型
下一篇: 利用cookie實作浏覽器中多個标簽頁之間的通信