二叉樹--二叉搜尋樹

一直對AVL這個英文縮寫比較困惑，原來一直以為是平衡二叉樹的首字母縮寫，但是又想不明白，哈！前段時間才明白原來是種這課樹的三個人的名字的首字母的，哎，生活處處有驚喜，無知不可怕，現在我也知道了。廢話不多說，下面我們說說，樹形結構中的那些平衡二叉樹。

二叉排序樹

樹的周遊順序有3種，二叉排序樹，顧名思義，就是一顆有序的二叉樹，是一種按照中序周遊樹中節點，而輸出有序隊列的一種樹形結構，一種特殊的樹形結構。

定義

對于二叉樹，假設x為二叉樹中的任意一個結點，x節點包含關鍵字key，節點x的key值記為key[x]。如果y是x的左子樹中的一個結點，則key[y] <= key[x]；如果y是x的右子樹的一個結點，則key[y] >= key[x]。那麼，這棵樹就是二叉排序樹。

二叉樹--二叉搜尋樹

二叉查找樹是可以不平衡的！！！

雜談：大多數人都稱之為二叉查找樹或者* 二叉搜尋樹*，從這一點，可以看出，其實并沒有人用這種方式來進行資料的排序，而是在做查找或者是搜尋的時候，常常使用，這也是它最為常見的應用場景。

性質

(01) 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

(02) 任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

(03) 任意節點的左、右子樹也分别為二叉查找樹；

(04) 沒有鍵值相等的節點（no duplicate nodes）；

建立

建立二叉查找樹，就是要定義樹形的結構，本文中的樹形結構包括左右子樹，父指針，節點權值，詳細請見後面代碼。

查找

按照左小右大的規則進行查找。

/*
 * (遞歸實作)查找"二叉樹x"中鍵值為key的節點
 */
private BSTNode<T> search(BSTNode<T> x, T key) {
    if (x==null)
        return x;

    int cmp = key.compareTo(x.key);
    if (cmp < )
        return search(x.left, key);
    else if (cmp > )
        return search(x.right, key);
    else
        return x;
}

public BSTNode<T> search(T key) {
    return search(mRoot, key);
}

/*
 * (非遞歸實作)查找"二叉樹x"中鍵值為key的節點
 */
private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
    while (x!=null) {
        int cmp = key.compareTo(x.key);

        if (cmp < ) 
            x = x.left;
        else if (cmp > ) 
            x = x.right;
        else
            return x;
    }

    return x;
}

public BSTNode<T> iterativeSearch(T key) {
    return iterativeSearch(mRoot, key);
}

插入

二叉樹--二叉搜尋樹

整個插入的過程如上圖所示，簡單的一句話就是，先來的就是根節點，比根節點小的在左子樹，比根節點大的在右子樹，是以也就注定了，這種方式形成的樹不是一顆二叉平衡樹。

/* 
 * 将結點插入到二叉樹中
 *
 * 參數說明：
 *     tree 二叉樹的
 *     z 插入的結點
 */
private void insert(BSTree<T> bst, BSTNode<T> z) {
    int cmp;
    BSTNode<T> y = null;
    BSTNode<T> x = bst.mRoot;

    // 查找z的插入位置
    while (x != null) {
        y = x;
        cmp = z.key.compareTo(x.key);
        if (cmp < )
            x = x.left;
        else
            x = x.right;
    }

    z.parent = y;
    if (y==null)
        bst.mRoot = z;
    else {
        cmp = z.key.compareTo(y.key);
        if (cmp < )
            y.left = z;
        else
            y.right = z;
    }
}

/* 
 * 建立結點(key)，并将其插入到二叉樹中
 *
 * 參數說明：
 *     tree 二叉樹的根結點
 *     key 插入結點的鍵值
 */
public void insert(T key) {
    BSTNode<T> z=new BSTNode<T>(key,null,null,null);

    // 如果建立結點失敗，則傳回。
    if (z != null)
        insert(this, z);
}

删除

二叉樹--二叉搜尋樹

上圖中，是比較簡單的一種删除節點的情況，在二叉查找樹中，删除的情況總共分為三種：

1、删除節點的左子樹為null，直接用右子樹進行替換删除節點；

2、删除節點的右子樹為null，直接用左子樹進行替換；

3、删除節點 z 的左右子樹都不為null，則查找要删除節點右子樹的最小元素，調整取走最小元素 y 的局部結構，用 y 節點的右節點代替y（其實右節點就是空，都是最小了，哪還有右節點），局部結構調整完畢；然後用 y 來代替 z 節點，完畢。需要注意的一點是，在這個操作中，會涉及到父指針的操作，千萬不要忘記

/* 
 * 删除結點(z)，并傳回被删除的結點
 *
 * 參數說明：
 *     bst 二叉樹
 *     z 删除的結點
 */
private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
    BSTNode<T> x=null;
    BSTNode<T> y=null;

    if ((z.left == null) || (z.right == null) )
        y = z;
    else
        y = successor(z);

    if (y.left != null)
        x = y.left;
    else
        x = y.right;

    if (x != null)
        x.parent = y.parent;

    if (y.parent == null)
        bst.mRoot = x;
    else if (y == y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;

    if (y != z) 
        z.key = y.key;

    return y;
}

/* 
 * 删除結點(z)，并傳回被删除的結點
 *
 * 參數說明：
 *     tree 二叉樹的根結點
 *     z 删除的結點
 */
public void remove(T key) {
    BSTNode<T> z, node; 

    if ((z = search(mRoot, key)) != null)
        if ( (node = remove(this, z)) != null)
            node = null;
}

完整的二叉搜尋樹代碼如下：

/**
 * Java 語言: 二叉查找樹
 *
 * @author skywang
 * @date 2013/11/07
 */

public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot;    // 根結點

    public class BSTNode<T extends Comparable<T>> {
        T key;                // 關鍵字(鍵值)
        BSTNode<T> left;    // 左孩子
        BSTNode<T> right;    // 右孩子
        BSTNode<T> parent;    // 父結點

        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        public T getKey() {
            return key;
        }

        public String toString() {
            return "key:"+key;
        }
    }

    public BSTree() {
        mRoot=null;
    }

    /*
     * 前序周遊"二叉樹"
     */
    private void preOrder(BSTNode<T> tree) {
        if(tree != null) {
            System.out.print(tree.key+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    /*
     * 中序周遊"二叉樹"
     */
    private void inOrder(BSTNode<T> tree) {
        if(tree != null) {
            inOrder(tree.left);
            System.out.print(tree.key+" ");
            inOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }


    /*
     * 後序周遊"二叉樹"
     */
    private void postOrder(BSTNode<T> tree) {
        if(tree != null)
        {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.key+" ");
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }


    /*
     * (遞歸實作)查找"二叉樹x"中鍵值為key的節點
     */
    private BSTNode<T> search(BSTNode<T> x, T key) {
        if (x==null)
            return x;

        int cmp = key.compareTo(x.key);
        if (cmp < )
            return search(x.left, key);
        else if (cmp > )
            return search(x.right, key);
        else
            return x;
    }

    public BSTNode<T> search(T key) {
        return search(mRoot, key);
    }

    /*
     * (非遞歸實作)查找"二叉樹x"中鍵值為key的節點
     */
    private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
        while (x!=null) {
            int cmp = key.compareTo(x.key);

            if (cmp < ) 
                x = x.left;
            else if (cmp > ) 
                x = x.right;
            else
                return x;
        }

        return x;
    }

    public BSTNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

    /* 
     * 查找最小結點：傳回tree為根結點的二叉樹的最小結點。
     */
    private BSTNode<T> minimum(BSTNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.left != null)
            tree = tree.left;
        return tree;
    }

    public T minimum() {
        BSTNode<T> p = minimum(mRoot);
        if (p != null)
            return p.key;

        return null;
    }

    /* 
     * 查找最大結點：傳回tree為根結點的二叉樹的最大結點。
     */
    private BSTNode<T> maximum(BSTNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.right != null)
            tree = tree.right;
        return tree;
    }

    public T maximum() {
        BSTNode<T> p = maximum(mRoot);
        if (p != null)
            return p.key;

        return null;
    }

    /* 
     * 找結點(x)的後繼結點。即，查找"二叉樹中資料值大于該結點"的"最小結點"。
     */
    public BSTNode<T> successor(BSTNode<T> x) {
        // 如果x存在右孩子，則"x的後繼結點"為 "以其右孩子為根的子樹的最小結點"。
        if (x.right != null)
            return minimum(x.right);

        // 如果x沒有右孩子。則x有以下兩種可能：
        // (01) x是"一個左孩子"，則"x的後繼結點"為 "它的父結點"。
        // (02) x是"一個右孩子"，則查找"x的最低的父結點，并且該父結點要具有左孩子"，找到的這個"最低的父結點"就是"x的後繼結點"。
        BSTNode<T> y = x.parent;
        while ((y!=null) && (x==y.right)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    /* 
     * 找結點(x)的前驅結點。即，查找"二叉樹中資料值小于該結點"的"最大結點"。
     */
    public BSTNode<T> predecessor(BSTNode<T> x) {
        // 如果x存在左孩子，則"x的前驅結點"為 "以其左孩子為根的子樹的最大結點"。
        if (x.left != null)
            return maximum(x.left);

        // 如果x沒有左孩子。則x有以下兩種可能：
        // (01) x是"一個右孩子"，則"x的前驅結點"為 "它的父結點"。
        // (01) x是"一個左孩子"，則查找"x的最低的父結點，并且該父結點要具有右孩子"，找到的這個"最低的父結點"就是"x的前驅結點"。
        BSTNode<T> y = x.parent;
        while ((y!=null) && (x==y.left)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    /* 
     * 将結點插入到二叉樹中
     *
     * 參數說明：
     *     tree 二叉樹的
     *     z 插入的結點
     */
    private void insert(BSTree<T> bst, BSTNode<T> z) {
        int cmp;
        BSTNode<T> y = null;
        BSTNode<T> x = bst.mRoot;

        // 查找z的插入位置
        while (x != null) {
            y = x;
            cmp = z.key.compareTo(x.key);
            if (cmp < )
                x = x.left;
            else
                x = x.right;
        }

        z.parent = y;
        if (y==null)
            bst.mRoot = z;
        else {
            cmp = z.key.compareTo(y.key);
            if (cmp < )
                y.left = z;
            else
                y.right = z;
        }
    }

    /* 
     * 建立結點(key)，并将其插入到二叉樹中
     *
     * 參數說明：
     *     tree 二叉樹的根結點
     *     key 插入結點的鍵值
     */
    public void insert(T key) {
        BSTNode<T> z=new BSTNode<T>(key,null,null,null);

        // 如果建立結點失敗，則傳回。
        if (z != null)
            insert(this, z);
    }

    /* 
     * 删除結點(z)，并傳回被删除的結點
     *
     * 參數說明：
     *     bst 二叉樹
     *     z 删除的結點
     */
    private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
        BSTNode<T> x=null;
        BSTNode<T> y=null;

        if ((z.left == null) || (z.right == null) )
            y = z;
        else
            y = successor(z);

        if (y.left != null)
            x = y.left;
        else
            x = y.right;

        if (x != null)
            x.parent = y.parent;

        if (y.parent == null)
            bst.mRoot = x;
        else if (y == y.parent.left)
            y.parent.left = x;
        else
            y.parent.right = x;

        if (y != z) 
            z.key = y.key;

        return y;
    }

    /* 
     * 删除結點(z)，并傳回被删除的結點
     *
     * 參數說明：
     *     tree 二叉樹的根結點
     *     z 删除的結點
     */
    public void remove(T key) {
        BSTNode<T> z, node; 

        if ((z = search(mRoot, key)) != null)
            if ( (node = remove(this, z)) != null)
                node = null;
    }

    /*
     * 銷毀二叉樹
     */
    private void destroy(BSTNode<T> tree) {
        if (tree==null)
            return ;

        if (tree.left != null)
            destroy(tree.left);
        if (tree.right != null)
            destroy(tree.right);

        tree=null;
    }

    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

    /*
     * 列印"二叉查找樹"
     *
     * key        -- 節點的鍵值 
     * direction  --  0，表示該節點是根節點;
     *               -1，表示該節點是它的父結點的左孩子;
     *                1，表示該節點是它的父結點的右孩子。
     */
    private void print(BSTNode<T> tree, T key, int direction) {

        if(tree != null) {

            if(direction==)    // tree是根節點
                System.out.printf("%2d is root\n", tree.key);
            else                // tree是分支節點
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==?"right" : "left");

            print(tree.left, tree.key, -);
            print(tree.right,tree.key,  );
        }
    }

    public void print() {
        if (mRoot != null)
            print(mRoot, mRoot.key, );
    }
}

文中代碼和圖參考自如果天空不死

二叉樹--二叉搜尋樹

定義

性質

建立

查找

插入

删除

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器