Java數(shù)據(jù)結(jié)構(gòu)超詳細(xì)分析二叉搜索樹(shù)

更新時(shí)間：2022年03月21日 09:17:27 作者：未見(jiàn)花聞

二叉搜索樹(shù)是以一棵二叉樹(shù)來(lái)組織的。每個(gè)節(jié)點(diǎn)是一個(gè)對(duì)象，包含的屬性有l(wèi)eft，right，p和key，其中，left指向該節(jié)點(diǎn)的左孩子，right指向該節(jié)點(diǎn)的右孩子，p指向該節(jié)點(diǎn)的父節(jié)點(diǎn)，key是它的值

1.搜索樹(shù)的概念

二叉搜索樹(shù)是一種特殊的二叉樹(shù)，又稱二叉查找樹(shù)，二叉排序樹(shù)，它有幾個(gè)特點(diǎn)：

如果左子樹(shù)存在，則左子樹(shù)每個(gè)結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。
如果右子樹(shù)存在，則右子樹(shù)每個(gè)結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。
中序遍歷二叉搜索樹(shù)，得到的序列是依次遞增的。
二叉搜索樹(shù)的左右子樹(shù)均為二叉搜索樹(shù)。
二叉搜索樹(shù)的結(jié)點(diǎn)的值不能發(fā)生重復(fù)。

1-1

2.二叉搜索樹(shù)的簡(jiǎn)單實(shí)現(xiàn)

我們來(lái)簡(jiǎn)單實(shí)現(xiàn)以下搜索樹(shù)，就不使用泛型了，二叉搜索樹(shù)基本結(jié)構(gòu)：

public class BinarySearchTree {

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node(int val) {
            this.val = val;
        }
    }

    public Node root;
    //其他方法
}

2.1查找

二叉搜索樹(shù)最擅長(zhǎng)的就是查找，根據(jù)二叉搜索樹(shù)的定義，左子樹(shù)的元素比根小，右子樹(shù)的元素比根大，所以我們只需要根據(jù)根結(jié)點(diǎn)的值與目標(biāo)元素的值比較，就能實(shí)現(xiàn)查找功能。

根與目標(biāo)元素相等，表示找到了。
根比目標(biāo)元素大，去左子樹(shù)找。
根比目標(biāo)元素小，去右子樹(shù)找。
左右子樹(shù)找不到，那就找不到了。

參考實(shí)現(xiàn)代碼：

    public Node search(int key) {
        Node cur = this.root;
        while (cur != null) {
            //根與目標(biāo)元素相等，表示找到了。
            if (cur.val == key) return cur;
            //根比目標(biāo)元素大，去左子樹(shù)找。
            else if (cur.val > key) cur = cur.left;
            //根比目標(biāo)元素小，去右子樹(shù)找。
            else cur = cur.right;
        }
        //此時(shí)cur = null, 左右子樹(shù)找不到，那就找不到了。
        return cur;
    }

2.2插入

需要在二叉搜索樹(shù)中插入一個(gè)元素，首先得找到一個(gè)合適的插入位置，如何找呢？其實(shí)就是利用搜索樹(shù)查找的方式，找到一個(gè)空位，如何將目標(biāo)結(jié)點(diǎn)插入到這個(gè)位置。

根與插入元素相等，插入元素不能與搜索樹(shù)中的元素相等，插入失敗。
根比插入元素大，去左子樹(shù)找。
根比插入元素小，去右子樹(shù)找。
找到的結(jié)點(diǎn)為空，那這個(gè)位置就是我們要找的空位。

2-1

由于你找到空位時(shí)，無(wú)法獲取該空位的前一個(gè)位置，所以每次查找的時(shí)候都需要保存上一次查找的位置。

找到位置后，將目標(biāo)結(jié)點(diǎn)插入到該位置。

2-2

參考實(shí)現(xiàn)代碼：

    public boolean insert(int val) {
        //結(jié)點(diǎn)為空，直接插
        if(root == null) {
            root = new Node(val);
            return true;
        }
        Node cur = this.root;   //當(dāng)前查找位置
        Node parent = null;     //查找的上一個(gè)位置
        while (cur != null) {
            parent = cur;
            if (val > cur.val) cur = cur.right;
            else if (val < cur.val) cur = cur.left;
            else return false;
        }
        //開(kāi)始插入，找到空位前一個(gè)位置，比插入元素小，空位在右邊，插入右邊
        if (val > parent.val) {
            parent.right = new Node(val);
        } else {
            //比插入元素大，空位在左邊，插入左邊
            parent.left = new Node(val);
        }
        return true;
    }

2.3刪除

刪除是搜索樹(shù)基本操作中最麻煩的一個(gè)操作，需要考慮多種情況。

不妨設(shè)需要?jiǎng)h除的結(jié)點(diǎn)為cur，cur的父結(jié)點(diǎn)為parent，搜索樹(shù)的根結(jié)點(diǎn)為root。首先需要?jiǎng)h除結(jié)點(diǎn)，那就得找到結(jié)點(diǎn)，所以第一步是找結(jié)點(diǎn)，思路與查找的思路一模一樣。

第二步那就是刪除了，刪除結(jié)點(diǎn)大概有下面幾種情況：

情況1：cur.left == null

cur == root，讓root = cur.right;
cur != root且parent.left == cur，讓parent.left = cur.right;
cur != root且parent.right == cur，讓parent.right = cur.right。

情況2：cur.right == null

cur == null，讓root = cur.left;
cur != root且parent.left == cur，讓parent.left = cur.left;
cur != root且parent.right == cur，讓parent.right = cur.left。

情況3：cur.left != null && cur.right != null

方案1：找到cur右子樹(shù)中最小的元素target，然后將該元素的值覆蓋到cur處（可以理解為交換），此時(shí)等價(jià)于刪除target處的結(jié)點(diǎn)，即該結(jié)點(diǎn)的父結(jié)點(diǎn)為preTarget。

3-1

3-2

因?yàn)?code>target為cur右子樹(shù)最小的一個(gè)結(jié)點(diǎn)，所以target.left == null，此時(shí)preTarget.left == target，所以刪除時(shí)按照上面的情況1去進(jìn)行刪除。

3-2-1

但是還有一種特殊情況，那就是cur.right就是最小結(jié)點(diǎn)，此時(shí)preTarget==cur，即preTarget.right == target，這時(shí)刪除時(shí)要將 preTarget.right = target.right。

3-3

3-4

3-4--0

方案2：找到cur左子樹(shù)中最大的元素target，然后將該元素的值覆蓋到cur處（可以理解為交換），此時(shí)等價(jià)于刪除target處的結(jié)點(diǎn)，即該結(jié)點(diǎn)的父結(jié)點(diǎn)為preTarget。

4-1

因?yàn)?code>target為cur左子樹(shù)最大的一個(gè)結(jié)點(diǎn)，所以target.right == null，此時(shí)preTarget.right == target，所以刪除時(shí)按照上面的情況2去進(jìn)行刪除。

4-2

但是還有一種特殊情況，那就是cur.left就是左子樹(shù)最大結(jié)點(diǎn)，此時(shí)preTarget==cur，即preTarget.left == target，這時(shí)刪除時(shí)要將 preTarget.left = target.left。

4-3

4-4

參考實(shí)現(xiàn)代碼：

    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                //這里開(kāi)始刪除
                removeNode(cur,parent);
                break;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

removeNode方法（方案1）：

    public void removeNode(Node cur,Node parent) {
        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 {
            Node preTarget  = cur ;
            Node target  = cur.right;
            while (target.left != null) {
                preTarget = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == preTarget.left) {
                preTarget.left = target.right;
            } else {
                preTarget.right = target.right;
            }
        }
    }

removeNode方法（方案2）：

    public void removeNode(Node cur,Node parent) {
        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 {
            Node preTarget  = cur ;
            Node target  = cur.left;
            while (target.right != null) {
                preTarget = target;
                target = target.right;
            }
            cur.val = target.val;
            if (target == preTarget.left) {
                preTarget.left = target.left;
            } else {
                preTarget.right = target.left;
            }
        }
    }

2.4修改

搜索樹(shù)的修改可以基于刪除和插入，先刪除目標(biāo)元素，然后再插入修改元素。

參考實(shí)現(xiàn)代碼：

    public void set(int key, int val) {
        remove(key);
        insert(val);
    }

3.二叉搜索樹(shù)的性能

在平衡二叉樹(shù)的情況下（左右子樹(shù)高度差不超過(guò)1），假設(shè)有n個(gè)結(jié)點(diǎn)，此時(shí)時(shí)間復(fù)雜度為二叉樹(shù)的高度，即 O ( l o g 2 n ) O(log_2n) O(log2?n)，但是這只是例行情況，最不理想的情況就是二叉樹(shù)化為單分支樹(shù)，時(shí)間復(fù)雜為 O ( n ) O(n) O(n)。

為了解決這個(gè)問(wèn)題，后面引申出AVL樹(shù)，紅黑樹(shù)，其中TreeMap與TreeSet的底層就是紅黑樹(shù)。具體紅黑樹(shù)是什么，這里就不多說(shuō)了。

本文到底了，你學(xué)會(huì)了嗎？

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)超詳細(xì)分析二叉搜索樹(shù)的文章就介紹到這了,更多相關(guān)Java 二叉搜索樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: