天天看點
傳回

複旦大學961-資料結構-第三章-查找（3）-BST樹定義,性質,ADT及其實作,BST樹查找,插入,删除算法BST樹定義BST的性質BST的ADT及其實作

961全部内容連結

文章目錄

  • BST樹定義
  • BST的性質
    • BST的時間複雜度
  • BST的ADT及其實作
    • BST的ADT
    • BST的具體實作
      • BST的插入
      • BST的查找
      • BST的查找最大最小值
      • BST的删除操作
    • 完整代碼如下

BST樹定義

BST（Binary Search Tree），又稱二叉排序樹，二叉查找樹，二叉搜尋樹。其特點為：

  1. 根節點的左子樹的所有元素必須小于根節點。右子樹上的元素必須大于根節點。
  2. 從根節點下的所有子樹也都要滿足1。

例如，如圖所示：

複旦大學961-資料結構-第三章-查找（3）-BST樹定義,性質,ADT及其實作,BST樹查找,插入,删除算法BST樹定義BST的性質BST的ADT及其實作

該樹為一棵BST，将其中序周遊就是一個有序數列：1,3,4,5,6,8,10,13,14

BST的性質

性質基本上就是定義中的那些。

BST的時間複雜度

  1. 平均查找時間複雜度為O(log n)
  2. 最壞的時間複雜度為O(n)，例如這樣一棵樹。
    複旦大學961-資料結構-第三章-查找（3）-BST樹定義,性質,ADT及其實作,BST樹查找,插入,删除算法BST樹定義BST的性質BST的ADT及其實作

BST的ADT及其實作

ADT就是抽象資料類型

BST的ADT 

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {

    private static class BinaryNode<AnyType> {

        AnyType element;
        BinaryNode<AnyType> left;
        BinaryNode<AnyType> right;

        public BinaryNode(AnyType theElement) {
            this.element = theElement;
        }

        public BinaryNode(AnyType theElement, BinaryNode lt, BinaryNode rt) {
            this.element = theElement;
            this.left = lt;
            this.right = rt;
        }
    }

    private BinaryNode<AnyType> root;

    public BinarySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }
    
    public boolean contains(AnyType x) {}
    
    public AnyType findMin() {}
    
    public AnyType findMax() {}
    
    public void insert(AnyType x) {}
    
    public void remove(AnyType x) {}
    
    public void printTree() {}
}

BST的具體實作

BST的插入

基本思想如下：

  1. 從根節點開始遞歸，若目前節點為空，則生成新節點
  2. 若x小于根節點，則插入到左子樹
  3. 若x大于根節點，則插入到右子樹
  4. 若x等于根節點，則什麼都不做
  5. 2,3,4步驟一緻遞歸，直至遞歸到1

代碼如下：

private BinaryNode insert(BinaryNode<AnyType> node, AnyType x) {
    if (node == null) {
        return new BinaryNode<>(x);  // 如果為空節點，則生成新節點
    }

    int result = node.element.compareTo(x);
    if (result > 0) node.left = insert(node.left, x);  // x小于根節點，則插入到左子樹
    else if (result < 0) node.right = insert(node.right, x);  // x大于根節點，插入到右子樹
    return node;  // 傳回插入後的樹的根節點
}

public void insert(AnyType x) {
    root = insert(root, x);
}

BST的查找

基本思想（與插入類似）：

  1. 從根節點開始遞歸的查找，若為空，則查找失敗
  2. 若x小于根節點，則查找左子樹
  3. 若x大于根節點，則查找右子樹
  4. 若x等于根節點，則查找成功
  5. 遞歸2,3,4，直到查找成功或查找失敗

代碼如下：

private boolean contains(BinaryNode<AnyType> node, AnyType x) {
    if (node == null) return false; // 如果都空了還沒找到，那麼就是不存在

    int result = x.compareTo(node.element);
    if (result == 0) return true; // 查找成功
    else if (result > 0) return contains(node.right, x); // x在右子樹中
    else return contains(node.left, x); // x在左子樹中
}

public boolean contains(AnyType x) {
    return contains(root, x);
}

BST的查找最大最小值

基本思想：沿着根節點一緻往左查找，最後一個左孩子就是樹的最小值。最大值就是沿着根節點一緻往右。

代碼如下：

private BinaryNode<AnyType> findMin(BinaryNode node) {
    if (node.left == null) return node;
    return findMin(node.left); // 遞歸查找左孩子
}

public AnyType findMin() {
    if (root == null) return null;
    return findMin(root).element;
}

private BinaryNode<AnyType> findMax(BinaryNode node) {
    while (node.right != null)
        node = node.right; // node的右孩子不為空，則一直往右
    return node;
}

public AnyType findMax() {
    if (root == null) return null;
    return findMax(root).element;
}

BST的删除操作

複旦大學961-資料結構-第三章-查找（3）-BST樹定義,性質,ADT及其實作,BST樹查找,插入,删除算法BST樹定義BST的性質BST的ADT及其實作

BST的删除比較複雜，分很多情況：

  1. 要删除的節點是葉子節點，直接删除即可，如删除圖中4這個節點
  2. 要删除的節點既有左孩子也有右孩子，此時需要将該節點的值替換為該節點右子樹的最小值，然後删除其右子樹中的最小值。如删除圖中的3節點，則需要将3替換為4，然後删除647這棵樹子樹上的4節點
  3. 要删除的節點隻有左子樹或隻有右子樹，則直接讓其父節點連接配接到它的左子樹或右子樹 
private BinaryNode remove(AnyType x, BinaryNode<AnyType> node) {
    if (node == null) return null;

    int result = x.compareTo(node.element);
    if (result > 0) {
        // x在右子樹中
        node.right = remove(x, node.right);
    } else if (result < 0) {
        // x在左子樹中
        node.left = remove(x, node.left);
    } else {
        if (node.left == null && node.right == null) {
            // 要删除的節點是葉節點，則直接删除，即傳回空
            return null;
        } else if (node.left != null && node.right != null) {
            // 要删除的節點左子樹和右子樹都不為空
            BinaryNode<AnyType> minNode = findMin(node.right);  // 擷取右子樹中的最小值
            node.element = minNode.element;  // 替換要删除節點的值為右子樹中的最小值
            node.right = remove(minNode.element, node.right); // 删除右子樹中的最小值
        } else if (node.left != null && node.right == null) {
            // 要删除的節點的左孩子不為空，右節點為空，則傳回左孩子
            return node.left;
        } else if (node.right != null && node.left == null) {
            // 要删除的節點的右孩子不為空，左節點為空，則傳回右孩子
            return node.right;
        }
    }
    return node;
}

public void remove(AnyType x) {
    root = remove(x, root);
}

代碼中有很多地方的判斷是沒有必要的，可以簡化很多，但為了思路清晰，是以加上了。我覺得考試應該不會是以扣分。

完整代碼如下 

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {

    private static class BinaryNode<AnyType> {

        AnyType element;
        BinaryNode<AnyType> left;
        BinaryNode<AnyType> right;

        public BinaryNode(AnyType theElement) {
            this.element = theElement;
        }

        public BinaryNode(AnyType theElement, BinaryNode lt, BinaryNode rt) {
            this.element = theElement;
            this.left = lt;
            this.right = rt;
        }
    }

    private BinaryNode<AnyType> root;

    public BinarySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    private boolean contains(BinaryNode<AnyType> node, AnyType x) {
        if (node == null) return false; // 如果都空了還沒找到，那麼就是不存在

        int result = x.compareTo(node.element);
        if (result == 0) return true; // 查找成功
        else if (result > 0) return contains(node.right, x); // x在右子樹中
        else return contains(node.left, x); // x在左子樹中
    }

    public boolean contains(AnyType x) {
        return contains(root, x);
    }

    private BinaryNode<AnyType> findMin(BinaryNode node) {
        if (node.left == null) return node;
        return findMin(node.left); // 遞歸查找左孩子
    }

    public AnyType findMin() {
        if (root == null) return null;
        return findMin(root).element;
    }

    private BinaryNode<AnyType> findMax(BinaryNode node) {
        while (node.right != null)
            node = node.right; // node的右孩子不為空，則一直往右
        return node;
    }

    public AnyType findMax() {
        if (root == null) return null;
        return findMax(root).element;
    }

    private BinaryNode insert(BinaryNode<AnyType> node, AnyType x) {
        if (node == null) {
            return new BinaryNode<>(x);  // 如果為空節點，則生成新節點
        }

        int result = node.element.compareTo(x);
        if (result > 0) node.left = insert(node.left, x);  // x小于根節點，則插入到左子樹
        else if (result < 0) node.right = insert(node.right, x);  // x大于根節點，插入到右子樹
        return node;  // 傳回插入後的樹的根節點
    }

    public void insert(AnyType x) {
        root = insert(root, x);
    }

    private BinaryNode remove(AnyType x, BinaryNode<AnyType> node) {
        if (node == null) return null;

        int result = x.compareTo(node.element);
        if (result > 0) {
            // x在右子樹中
            node.right = remove(x, node.right);
        } else if (result < 0) {
            // x在左子樹中
            node.left = remove(x, node.left);
        } else {
            if (node.left == null && node.right == null) {
                // 要删除的節點是葉節點，則直接删除，即傳回空
                return null;
            } else if (node.left != null && node.right != null) {
                // 要删除的節點左子樹和右子樹都不為空
                BinaryNode<AnyType> minNode = findMin(node.right);  // 擷取右子樹中的最小值
                node.element = minNode.element;  // 替換要删除節點的值為右子樹中的最小值
                node.right = remove(minNode.element, node.right); // 删除右子樹中的最小值
            } else if (node.left != null && node.right == null) {
                // 要删除的節點的左孩子不為空，右節點為空，則傳回左孩子
                return node.left;
            } else if (node.right != null && node.left == null) {
                // 要删除的節點的右孩子不為空，左節點為空，則傳回右孩子
                return node.right;
            }
        }
        return node;
    }

    public void remove(AnyType x) {
        root = remove(x, root);
    }

    public void printTree() {
    	// todo 這個大綱裡沒有，後期補充
    }
}
961
上一篇: 複旦大學961-軟體工程-第二章-軟體需求軟體需求的概念需求工程的基本過程分層資料流模型用例和場景模組化及其UML表達資料模型模組化及其UML表達（類圖）
下一篇: 複旦大學961-計算機系統基礎-第二章-優化程式性能優化程式性能優化編譯器的能力編譯器優化的局限性表示程式性能特定體系結構或應用特性的性能優化限制因素确認和消除性能瓶頸

繼續閱讀