摘要：所以，如果中序遍歷二叉搜索樹(shù)，會(huì)得到一個(gè)有序的數(shù)據(jù)，時(shí)間復(fù)雜度是，所以二叉搜索樹(shù)又叫做二叉排序樹(shù)。所以，我們需要一種方式來(lái)維持二叉樹(shù)的平衡，最好是將其維持為滿二叉樹(shù)或者完全二叉樹(shù)，這就是后面會(huì)說(shuō)到的平衡二叉查找樹(shù)，常見(jiàn)的有樹(shù)，紅黑樹(shù)。

1. 概述

前面的文章說(shuō)到了二叉樹(shù)，其實(shí)今天講的二叉搜索(查找)樹(shù)就是二叉樹(shù)最常用的一種形式，它支持高效的查找、插入、刪除操作，它的定義是這樣的：對(duì)于樹(shù)中的任意一個(gè)節(jié)點(diǎn)，其左子節(jié)點(diǎn)值必須小于該節(jié)點(diǎn)，其右子節(jié)點(diǎn)必須大于該節(jié)點(diǎn)。例如下圖中的幾種樹(shù)都是二叉查找樹(shù)：

2. 二叉搜索樹(shù)的查找

我們直接拿查找的數(shù)據(jù)和根節(jié)點(diǎn)數(shù)據(jù)作比較，如果大于根節(jié)點(diǎn)，則在右子樹(shù)中遞歸查找，如果小于根節(jié)點(diǎn)，則在左子樹(shù)中查找，如果等于，則直接返回。就像下圖的查找過(guò)程：

結(jié)合代碼能夠更直觀的理解：

public class BinaryTree {
    private Node head = null;//樹(shù)的根節(jié)點(diǎn)
    //1.查找節(jié)點(diǎn)
    public Node find(int value){
        Node p = head;
        while (p != null){
            if (p.getData() > value) p = p.left;
            else if (p.getData() < value) p = p.right;
            else return p;
        }
        return null;
    }
    //定義樹(shù)的節(jié)點(diǎn)
    public static class Node{
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }

        public int getData() {
            return data;
        }
    }
}

3. 二叉搜索樹(shù)的插入

插入操作和查找其實(shí)比較的類(lèi)似，都是需要拿插入的數(shù)據(jù)和樹(shù)中的數(shù)據(jù)進(jìn)行比較，如果插入的數(shù)據(jù)大于樹(shù)節(jié)點(diǎn)數(shù)據(jù)，并且節(jié)點(diǎn)的右子樹(shù)為空，則直接插入到右子樹(shù)，否則繼續(xù)在右子樹(shù)中遞歸查找位置；如果插入的數(shù)據(jù)小于樹(shù)節(jié)點(diǎn)數(shù)據(jù)，并且節(jié)點(diǎn)的左子樹(shù)為空，則直接插入到左子樹(shù)，否則繼續(xù)在左子樹(shù)中遞歸查找位置。

結(jié)合代碼理解一下：

 public void insert(int value){
        Node node = new Node(value);
        if (head == null){
            head = node;
            return;
        }
        Node p = head;
        while (p != null){
            if (p.getData() > value){
                if (p.left == null) {
                    p.left = node;
                    return;
                }
                p = p.left;
            }
            else {
                if (p.right == null) {
                    p.right = node;
                    return;
                }
                p = p.right;
            }
        }
    }

4. 二叉搜索樹(shù)的刪除

前面的查找和插入操作都比較的簡(jiǎn)單易懂，但是二叉搜索樹(shù)的刪除操作就比較的復(fù)雜了，分為了幾種情況。

第一種情況：要?jiǎng)h除的節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，這樣的話，可以直接將指向該節(jié)點(diǎn)的父節(jié)點(diǎn)指針設(shè)為 null。

第二種情況：要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，直接將該節(jié)點(diǎn)的父節(jié)點(diǎn)的指針，指向該節(jié)點(diǎn)的子節(jié)點(diǎn)即可。

第三種情況：要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，我們需要在刪除節(jié)點(diǎn)的右子樹(shù)中，尋找到最小的那個(gè)節(jié)點(diǎn)，然后將其放在刪除的節(jié)點(diǎn)的位置上。

三種情況對(duì)應(yīng)下圖：

結(jié)合代碼來(lái)理解一下：

    //3.刪除數(shù)據(jù)
    public void delete(int value){
        Node p = head;
        Node pParent = null;//p節(jié)點(diǎn)的父節(jié)點(diǎn)

        //先找到這個(gè)節(jié)點(diǎn)
        while (p != null && p.getData() != value){
            pParent = p;
            if (p.getData() > value)p = p.left;
            else p = p.right;
        }
        if (p == null) return;//表示沒(méi)有找到值為value的節(jié)點(diǎn)

        //1.假如要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
        if (p.left != null && p.right != null){
            //查找p節(jié)點(diǎn)的右子節(jié)點(diǎn)中的最小值
            Node minP = p.right;
            Node minPP = p;//minPP表示minP的父節(jié)點(diǎn)
            while (minP.left != null){
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.getData();
            if (minPP == p) p.right = null;
            else minPP.left = null;
            return;
        }

        //2.假如刪除的節(jié)點(diǎn)p是葉子節(jié)點(diǎn)或只有一個(gè)子節(jié)點(diǎn)
        Node child = null;
        if (p.left != null) child = p.left;
        else if (p.right != null) child = p.right;

        if (pParent == null) head = child;
        else if (pParent.left == p) pParent.left = child;
        else pParent.right = child;
    }

5. 二叉搜索樹(shù)分析

最后，還有兩個(gè)需要說(shuō)明一下，前面說(shuō)到了二叉樹(shù)的三種遍歷方式，其中，中序遍歷的方式是先遍歷節(jié)點(diǎn)的左子節(jié)點(diǎn)，再遍歷這個(gè)節(jié)點(diǎn)本身，然后遍歷節(jié)點(diǎn)的右子節(jié)點(diǎn)。所以，如果中序遍歷二叉搜索樹(shù)，會(huì)得到一個(gè)有序的數(shù)據(jù)，時(shí)間復(fù)雜度是 O(n)，所以二叉搜索樹(shù)又叫做二叉排序樹(shù)。

在理想的情況下，我們的二叉樹(shù)是一棵滿二叉樹(shù)或者完全二叉樹(shù)，那么查找、插入、刪除操作十分的高效，時(shí)間復(fù)雜度是 O(logn)，但是，如果二叉樹(shù)的左右子樹(shù)非常的不平衡，極端的情況下，可能會(huì)退化為鏈表，那么性能就下降了。

所以，我們需要一種方式來(lái)維持二叉樹(shù)的平衡，最好是將其維持為滿二叉樹(shù)或者完全二叉樹(shù)，這就是后面會(huì)說(shuō)到的平衡二叉查找樹(shù)，常見(jiàn)的有 AVL 樹(shù)，紅黑樹(shù)。