1、認(rèn)識(shí)二叉搜索樹(shù)

從字面上來(lái)看，它只比二叉樹(shù)多了搜索兩個(gè)字，我們回想一下，如果要是在二叉樹(shù)中查找一個(gè)元素的話，需要遍歷這棵樹(shù)，效率很慢，而二叉搜索樹(shù)，則會(huì)效率高很多，為什么呢？

二叉搜索樹(shù)，可以是一棵空樹(shù)，或者是具有以下的性質(zhì)：

• 若它的左子樹(shù)不為空，則左樹(shù)上所有的節(jié)點(diǎn)都小于根節(jié)點(diǎn)
• 若它的右子樹(shù)不為空，則右樹(shù)上所有節(jié)點(diǎn)的都大于根節(jié)點(diǎn)
• 它的左子樹(shù)和右子樹(shù)也分別為二叉搜索樹(shù)

通俗來(lái)講，左孩子都小于父節(jié)點(diǎn)，右孩子都大于父節(jié)點(diǎn)，以此類推，這里我們畫(huà)圖來(lái)認(rèn)識(shí)下二叉搜索樹(shù)：

當(dāng)然二叉搜索樹(shù)不要求是完全二叉樹(shù)或滿二叉樹(shù)，甚至?xí)霈F(xiàn)單分支的二叉搜索樹(shù)，所以針對(duì)這種特殊的情況進(jìn)行了優(yōu)化也就延申而來(lái)的 AVL樹(shù)，這個(gè)是后續(xù)的話題。

仔細(xì)觀察上圖，可以觀察出二叉搜索樹(shù)的一個(gè)新特性：

中序遍歷二叉搜索樹(shù)是有序的，所以二叉搜索樹(shù)也被稱為二叉排序樹(shù)。

2、實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)

2.1 成員變量

public class BinarySearchTree {
    private TreeNode root; //存放根節(jié)點(diǎn)
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode(int val) {
            this.val = val;
        }
    }
}

這里跟我們的二叉樹(shù)成員變量大同小異，主要是去實(shí)現(xiàn)插入，查找，刪除的邏輯。

2.2 insert 方法

往二叉搜索樹(shù)插入一個(gè)節(jié)點(diǎn)的時(shí)候，我們要注意兩點(diǎn)，首先如果二叉搜索樹(shù)為空，則直接令 root 為當(dāng)前插入的節(jié)點(diǎn)即可，那如果二叉搜索樹(shù)不為空，我們則需要利用二叉搜索樹(shù)的性質(zhì)，找到該節(jié)點(diǎn)要插入的位置即可，具體我們來(lái)看下圖：

通過(guò)動(dòng)圖我們可以看到，當(dāng)二叉搜索樹(shù)不為空的時(shí)候，新的元素會(huì)依次節(jié)點(diǎn)比較，如果比根節(jié)點(diǎn)大，則去根的右邊，比根節(jié)點(diǎn)小，則取根的左邊，以此類推。(搜索二叉樹(shù)不存在相同的元素)

但是我們用代碼如何實(shí)現(xiàn)呢？定義一個(gè) cur 引用，當(dāng) cur 等于 null 了，則表示是我要插入的位置，既然找到了要插入的位置，但是還得知道這個(gè)位置的父節(jié)點(diǎn)是誰(shuí)，通過(guò)父節(jié)點(diǎn)的指針域給連接起來(lái)，于是代碼可以這樣寫：

public boolean insert(int key) {
    // 二叉搜索樹(shù)沒(méi)有節(jié)點(diǎn)的情況
    if (root == null) {
        root = new TreeNode(key);
        return true;
    }
    // 二叉搜索樹(shù)不為空的情況 -> 找到該節(jié)點(diǎn)要插入的位置進(jìn)行插入
    // 如果已經(jīng)存在該節(jié)點(diǎn)了, 則不用插入 -> 二叉搜索樹(shù)中不能出現(xiàn)重復(fù)值
    TreeNode parent = null; // 記錄cur的父節(jié)點(diǎn)
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            return false; // 插入重復(fù)的節(jié)點(diǎn)
        }
    }
    // 走到這, cur為空了, key 需要插入到 parent 的左節(jié)點(diǎn)或右節(jié)點(diǎn)中
    TreeNode newNode = new TreeNode(key);
    if (parent.val < key) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    return true;
}

2.3 search 方法

搜索方法，也就是給一個(gè) key 你，讓你在這顆二叉樹(shù)找有沒(méi)有這個(gè)元素，有的話返回該節(jié)點(diǎn)，沒(méi)有的話返回 null，這個(gè)就很簡(jiǎn)單了，跟上面的步驟一樣無(wú)非就是碰到相同的元素返回 cur 嘛，當(dāng) cur 根據(jù) key 遍歷完這棵二叉搜索樹(shù)的時(shí)候，也就是 cur 為 null 了，則表示沒(méi)有該元素，直接返回 null即可。

代碼如下：

public TreeNode search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            cur = cur.right;
        } else if (cur.val > key) {
            cur = cur.left;
        } else {
            return cur;
        }
    }
    return null;
}

2.4 remove 方法(重點(diǎn))

在二叉搜索樹(shù)中，刪除一個(gè)節(jié)點(diǎn)是一個(gè)比較麻煩的事，但是只要把各種刪除的情況下列舉出來(lái)，一一解決它即可，對(duì)于二叉搜索樹(shù)來(lái)說(shuō)，你刪除了一個(gè)節(jié)點(diǎn)，它仍然滿足二叉搜索樹(shù)的性質(zhì)。

設(shè) cur 為要?jiǎng)h除的節(jié)點(diǎn)，所以首先我們得判斷這個(gè)二叉搜索樹(shù)中，是否存在要?jiǎng)h除的節(jié)點(diǎn)，這個(gè)邏輯上面已經(jīng)寫過(guò)了，找到要?jiǎng)h除的節(jié)點(diǎn)后，我們一共會(huì)面臨三種情況：

① 如果 cur 沒(méi)有左子樹(shù)的情況

• 如果 cur 是 root 的情況，只需要 root = cur.right
• 如果 cur 不是 root，cur 是 parent.left 的情況，只需要 parent.left = cur.right
• 如果 cur 不是 root，cur 是 parent.right 的情況，只需要 parent.right = cur.right

圖解：

② 如果 cur 沒(méi)有右子樹(shù)的情況

• 如果 cur 是 root 的情況，只需要 root = cur.left
• 如果 cur 不是 root，cur 是 parent.left 的情況，只需要 parent.left = cur.left
• 如果 cur 不是 root，cur 是 parent.right 的情況，只需要 parent.right = cur.left

圖解：

③ 如果 cur 既有左子樹(shù)，又有右子樹(shù)的情況

使用替換法進(jìn)行刪除，即在 cur 的右子樹(shù)中，一直往左尋找最小的元素，將這個(gè)最小值賦值給要?jiǎng)h除節(jié)點(diǎn)的 val 值中，接著把這個(gè)最小元素的節(jié)點(diǎn)刪除即可，刪除的邏輯見(jiàn)下圖和完整刪除代碼。

代碼如下：

public boolean remove(int key) {
    TreeNode parent = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            removeNode(parent, cur);
            return true;
        }
    }
    return false;
}
private void removeNode(TreeNode parent, TreeNode cur) {
    if (cur.left == null) {
        if (cur == root) {
            root = cur.right;
        } else if (cur == parent.left) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = cur.left;
        } else if (cur == parent.left) {
            parent.left = cur.left;
        } else {
            parent.right = cur.left;
        }
    } else {
        TreeNode target = cur.right;
        TreeNode targetParent = cur;
        while (target.left != null) {
            targetParent = target;
            target = target.left;
        }
        // 走到這, target就是要?jiǎng)h除節(jié)點(diǎn)的右子樹(shù)中最小的節(jié)點(diǎn), 接下來(lái)進(jìn)行覆蓋
        cur.val = target.val;
        // 覆蓋完成, 現(xiàn)在需要?jiǎng)h除 target 節(jié)點(diǎn)
        // 如果 cur.right 沒(méi)有左孩子的情況, 此時(shí)的target就是cur.right
        // 即直接將 cur.right 覆蓋到 cur 位置, 也就是滿足 target == targetParent.right 條件
        // 所以需要進(jìn)行特殊處理.
        if (target == targetParent.right) {
            targetParent.right = target.right;
        } else {
            targetParent.left = target.right;
        }
    }
}

3、二叉搜索樹(shù)總結(jié)

二叉搜索樹(shù)在最好的情況下為完全二叉樹(shù)，查找的平均比較次數(shù)為：logn

二叉搜索樹(shù)在最差的情況下退化成但分支，查找的平均比較次數(shù)為：n/2

所以二叉搜索樹(shù)在最差的情況下效率是不高的，為了解決單分支的情況，于是有了 AVL樹(shù)，當(dāng)發(fā)現(xiàn)二叉搜索樹(shù)左右子樹(shù)高度差太大，會(huì)自動(dòng)旋轉(zhuǎn)，以致平衡，避免旋轉(zhuǎn)的次數(shù)太多，又引入了紅黑樹(shù)，給節(jié)點(diǎn)增加了顏色，細(xì)節(jié)部分后期講解，這里有個(gè)概念即可，下期將會(huì)介紹由紅黑樹(shù)作為底層的集合：TreeSet 和 TreeMap

下期預(yù)告： 【Java 數(shù)據(jù)結(jié)構(gòu)】TreeSet 和 TreeMap

到此這篇關(guān)于Java簡(jiǎn)單幾步實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)的文章就介紹到這了,更多相關(guān)Java二叉搜索樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論