1 定義

• 一棵二叉查找樹(shù)（BST）是一棵二叉樹(shù)桨仿，其中每個(gè)結(jié)點(diǎn)都含有一個(gè)Comparable的鍵（以及相關(guān)的值）且每個(gè)結(jié)點(diǎn)的鍵都大于其左子樹(shù)中的任意結(jié)點(diǎn)的鍵而小于右子樹(shù)的任意結(jié)點(diǎn)的鍵。

2 基本實(shí)現(xiàn)

• 一棵二叉查找樹(shù)代表的是一組鍵（及其相應(yīng)的值）的集合筑辨，而同一個(gè)集合可以用多棵不同的二叉查找樹(shù)表示。但注意纲堵，將一棵二叉查找樹(shù)的所以鍵投影到一條直線上巡雨，保證一個(gè)節(jié)點(diǎn)的左子樹(shù)的鍵出現(xiàn)在其左邊，右子樹(shù)的鍵出現(xiàn)在其右邊席函。
  
  不同二叉查找樹(shù)表示同一個(gè)集合
• 下面給出二叉查找樹(shù)的實(shí)現(xiàn)代碼,接下來(lái)將對(duì)這些方法進(jìn)行解釋：

package BinaryTree.BinarySearchTree;

public class BTS<Key extends Comparable<Key>, Value> {
    //二叉樹(shù)根節(jié)點(diǎn)
    private Node root;

    private class Node {
        private Key key; //鍵
        private Value value;//值
        private Node left, right;//左節(jié)點(diǎn)和右節(jié)點(diǎn)
        private int N;//以該節(jié)點(diǎn)為根的子樹(shù)中的節(jié)點(diǎn)總數(shù)

        //構(gòu)造方法
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }

        //以該節(jié)點(diǎn)為根的子樹(shù)中的節(jié)點(diǎn)總數(shù)
        public int size() {
            return size(root);
        }

        private int size(Node x) {
            if (x == null) {
                return 0;
            } else {
                return x.N;
            }
        }

        //查找某個(gè)值
        public Value get(Key key) {
            return get(root, key);
        }

        public Value get(Node x, Key key) {
            //如果樹(shù)為空铐望，則返回null
            if (x == null) {
                return null;
            }
            int cmp = key.compareTo(x.key);
            //如果相等，則返回該結(jié)點(diǎn)茂附，小于就去左子樹(shù)正蛙，大于就去右子樹(shù)
            if(cmp == 0){
                return x.value;
            }else if(cmp<0){
                return get(x.left, key);
            }else{
                return get(x.right, key);
            }
        }

        //插入某個(gè)值
        public void put(Key key, Value value) {
            //查找key，找到更新它的值营曼，找不到則插入
            root = put(root, key, value);
        }

        public Node put(Node x, Key key, Value value) {
            if (x == null) {
                return new Node(key, value, 1);
            }
            int cmp = key.compareTo(x.key);
            if (cmp < 0) {
                x.left = put(x.left, key, value);
            } else if (cmp > 0) {
                x.right = put(x.right, key, value);
            } else {
                x.value = value;
            }
            x.N = size(x.left) + size(x.right) + 1;
            return x;
        }

        public Key min() {
            return min(root).key;
        }

        public Node min(Node x) {
            if (x.left == null) return x;
            return min(x.left);
        }

        public Key floor(Key key) {
            Node x = floor(root,key);
            if(x == null) return null;
            return x.key;
        }

        public Node floor(Node x, Key key) {
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x;
            if (cmp < 0) return floor(x.left, key);
            Node t = floor(x.right, key);
            if (t != null) return t;
            else return x;
        }
    }
}

2.1 查找

• 查找只會(huì)獲得兩種結(jié)果乒验，一是含有該節(jié)點(diǎn)，二是不含該節(jié)點(diǎn)返回Null.
• 遞歸算法：①如果樹(shù)是空的蒂阱，則返回null②如果被查找的鍵和根節(jié)點(diǎn)鍵相同锻全，則查找命中，返回該節(jié)點(diǎn)③否則遞歸地在適當(dāng)?shù)淖訕?shù)中進(jìn)行查找录煤，如果被查找的鍵小于該節(jié)點(diǎn)就選擇左子樹(shù)鳄厌，否則選擇右子樹(shù)。上面代碼中g(shù)et()函數(shù)完全按照這種思想進(jìn)行的

• 代碼運(yùn)行流程實(shí)例如下：

  
  
  查找流程

2.2 插入

• 插入同樣會(huì)產(chǎn)生兩種后果妈踊，一是該節(jié)點(diǎn)已經(jīng)存在部翘，則更新該結(jié)點(diǎn)的值（Value），二是該節(jié)點(diǎn)不存在响委，則生成一個(gè)節(jié)點(diǎn)插入新思。
• 遞歸算法：①如果該樹(shù)是空的，則返回一個(gè)含有該鍵值對(duì)的新結(jié)點(diǎn)②如果要插入的鍵已經(jīng)存在且是當(dāng)前結(jié)點(diǎn)赘风，則修改其value值③如果被插入的鍵小于根節(jié)點(diǎn)夹囚，則在左子樹(shù)中插入該鍵，否則在右子樹(shù)中插入邀窃。
• 注意：結(jié)點(diǎn)還有一個(gè)屬性N（代碼以該結(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)的結(jié)點(diǎn)數(shù)量）荸哟，在進(jìn)行插入后需要修改該值。*將遞歸調(diào)用前的代碼想象成沿著樹(shù)向下走（比較鍵大兴膊丁）鞍历，那遞歸后調(diào)用的代碼想象成沿著樹(shù)向上爬（對(duì)于get()方法，這僅代表一系列的返回指令return,但對(duì)于put()方法肪虎，這意味著重置N值）
• 上面代碼中put()函數(shù)完全按照這種思想進(jìn)行的

• 運(yùn)行流程示例如下：

  
  
  插入流程

2.3 最大鍵和最小鍵

• 二叉查找樹(shù)的根節(jié)點(diǎn)小于其右子樹(shù)中的所有結(jié)點(diǎn)劣砍，大于其左子樹(shù)中的所有結(jié)點(diǎn)。因策扇救，最小鍵即最左下角的結(jié)點(diǎn)刑枝，最大鍵即最右下角的結(jié)點(diǎn)香嗓。
• 代碼實(shí)現(xiàn)如下：

        public Node min(Node x) {
            if (x.left == null) return x;
            return min(x.left);
        }
        public Node max(Node x) {
            if (x.right == null) return x;
            return min(x.right);
        }

2.4 向上取整和向下取整

• 向下取整：即取得小于等于key的最大鍵
• 向上取整：即取得大于等于key的最小鍵
• 算法思想：如果給定的鍵等于該根節(jié)點(diǎn)，則返回根節(jié)點(diǎn);如果給定的鍵小于根節(jié)點(diǎn)的鍵装畅，則小于等于key的最大鍵floor(key)在其左子樹(shù)中靠娱；如果給定的鍵大于根節(jié)點(diǎn)的鍵，則僅當(dāng)其右子樹(shù)存在小于等于key的鍵時(shí)返回該鍵掠兄，否則就返回當(dāng)前根節(jié)點(diǎn)的鍵像云。下面的代碼完全按照該思想進(jìn)行編碼：

        public Node floor(Node x, Key key) {
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0){
                return x;
            }else if (cmp < 0){
                return floor(x.left, key);
            }else{
                //當(dāng)找到小于key的鍵，要判斷其右子樹(shù)是否存在小于等于key的鍵蚂夕，若有則返回那個(gè)節(jié)點(diǎn)苫费，沒(méi)有則返回當(dāng)前節(jié)點(diǎn)
                Node t = floor(x.right, key);
                if (t != null) return t;
                else return x;
            }
        }

• 代碼運(yùn)行流程如下：

  
  
  floor

2.5 select選擇操作

• 假設(shè)我們想找到排名為k的鍵（樹(shù)中正好有k個(gè)小于它的鍵）。如果左子樹(shù)中的結(jié)點(diǎn)t大于k双抽，我們就繼續(xù)在左子樹(shù)中查找排名為k的鍵百框；如果t等于k，我們就返回根節(jié)點(diǎn)中的鍵牍汹；如果t小于k铐维，就查找右子樹(shù)中排名(k-t-1)的鍵。下面的代碼完全按照該思想進(jìn)行編碼：

        public Node select(Node x, int k) {
            if (x == null) {
                return null;
            }
            int t = size(x.left);
            if(t>k){
                return select(x.left,k);
            }else if(t<k){
                return select(x.right,k-t-1);
            }else{
                return x;
            }
        }

• 運(yùn)行流程如下：

  
  
  select

2.6 刪除最大鍵和最小鍵

• 刪除最小鍵算法思想：只要不斷深入左子樹(shù)直至遇見(jiàn)一個(gè)空連接慎菲。

        public Node deleteMin(Node x) {
            if (x.left == null) return x.right;
            x.left = deleteMin(x.left);
            x.N = size(x.left) + size(x.right) + 1;
            return x;
        }

2.7 刪除任意鍵

• 將即將被刪除的結(jié)點(diǎn)保存為t
• 將x 指向它的后繼結(jié)點(diǎn)min(t.right)
• 將x的右鏈接指向deleteMin(t.right)
• 將x的左連接設(shè)為t.left

        public Node delete(Node x, Key key) {
            if(x == null) return null;
            int cmp = key.compareTo(x.key);
            if(cmp<0){
                x.left = delete(x.left,key);
            }else if(cmp>0){
                x.right = delete(x.right,key);
            }else{
                if(x.right == null) return x.left;
                if(x.left == null) return x.right;
                Node t = x;
                x = min(t.right);
                x.right = deleteMin(t.right);
                x.left = t.left;
            }
            x.N = size(x.left) + size(x.right) +1;
            return x;
        }

• 運(yùn)行流程如下：

  
  
  運(yùn)行流程

2.8 范圍查找

• 代碼如下：

        public void key(Node x, Queue<Key> queue,Key lo,Key hi){
            if(x == null){
                return ;
            }
            int cmplo = lo.compareTo(x.key);
            int cmphi = hi.compareTo(x.key);
            if(cmplo<0){
                key(x.left,queue,lo,hi);
            }
            if(cmplo<=0&&cmphi>=0){
                queue.add(x.key);
            }
            if(cmphi>0){
                key(x.right,queue,lo,hi);
            }
        }

3 練習(xí)

3.1 插入練習(xí)

• 題目：將 E A S Y Q U E S T I O N 作為鍵按順序插入一棵初始為空的二叉查找樹(shù)嫁蛇。

    @Test
    public void testPut(){
        BTS<Character,String> bts = new BTS<Character,String>();
        Character ch[] = {'E','A','S','Y','Q','E','S','T','I','O','N'};
        BTS.Node node = bts.new Node();
        for(char c:ch){
            node.put(c,"");
        }
        //先序遍歷一下
        node.preOrder(bts.root);
    }

• 共需要21次比較

3.2 插入順序?qū)е碌淖顑?yōu)與最劣二叉查找樹(shù)結(jié)構(gòu)

• A X C S E R H 順序插入將會(huì)導(dǎo)致一棵最壞情況的二叉查找樹(shù)，其最后一個(gè)結(jié)點(diǎn)兩個(gè)鏈接全空露该，其余結(jié)點(diǎn)都含有一個(gè)空結(jié)點(diǎn)睬棚。樹(shù)變?yōu)榱随湵怼?/li>

• H C A E S R X便會(huì)產(chǎn)生最優(yōu)的二叉查找樹(shù)。

  
  
  插入順序?qū)е碌牟煌?/div>

3.3 為二叉查找樹(shù)添加查詢樹(shù)高度的方法

        public int height() {
            return height(root);
        }
        private int height(Node x) {
            if (x == null) return 0;
            return 1 + Math.max(height(x.left), height(x.right));
        }

3.4 方法測(cè)試

package BinaryTree.BinarySearchTree;


import sun.misc.Queue;

public class BTS<Key extends Comparable<Key>, Value> {
    //二叉樹(shù)根節(jié)點(diǎn)
    public Node root;

    public class Node {
        private Key key; //鍵
        private Value value;//值
        private Node left, right;//左節(jié)點(diǎn)和右節(jié)點(diǎn)
        private int N;//以該節(jié)點(diǎn)為根的子樹(shù)中的節(jié)點(diǎn)總數(shù)
        public Node(){

        }
        //構(gòu)造方法
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }


        public int height() {
            return height(root);
        }
        private int height(Node x) {
            if (x == null) return 0;
            return 1 + Math.max(height(x.left), height(x.right));
        }
        //線序遍歷
        public void preOrder(){
            preOrder(root);
        }
        //線序遍歷
        private void preOrder(Node x){
            if(x == null) return;
            System.out.print(x.key);
            preOrder(x.left);
            preOrder(x.right);
        }
        //以該節(jié)點(diǎn)為根的子樹(shù)中的節(jié)點(diǎn)總數(shù)
        public int size() {
            return size(root);
        }

        private int size(Node x) {
            if (x == null) {
                return 0;
            } else {
                return x.N;
            }
        }

        //查找某個(gè)值
        public Value get(Key key) {
            return get(root, key);
        }

        private Value get(Node x, Key key) {
            //如果樹(shù)為空解幼，則返回null
            if (x == null) {
                return null;
            }
            int cmp = key.compareTo(x.key);
            if (cmp == 0) {
                return x.value;
            } else if (cmp < 0) {
                return get(x.left, key);
            } else {
                return get(x.right, key);
            }
        }

        //插入某個(gè)值
        public void put(Key key, Value value) {
            //查找key抑党，找到更新它的值，找不到則插入
            root = put(root, key, value);
        }

        private Node put(Node x, Key key, Value value) {
            if (x == null) {
                return new Node(key, value, 1);
            }
            int cmp = key.compareTo(x.key);
            if (cmp == 0) {
                x.value = value;
            } else if (cmp < 0) {
                x.left = put(x.left, key, value);
            } else {
                x.right = put(x.right, key, value);
            }
            x.N = size(x.left) + size(x.right) + 1;
            return x;
        }

        public Key min() {
            return min(root).key;
        }

        public Node min(Node x) {
            if (x.left == null) return x;
            return min(x.left);
        }

        public Key floor(Key key) {
            Node x = floor(root, key);
            if (x == null) return null;
            return x.key;
        }

        private Node floor(Node x, Key key) {
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) {
                return x;
            } else if (cmp < 0) {
                return floor(x.left, key);
            } else {
                //當(dāng)找到小于key的鍵撵摆，要判斷其右子樹(shù)是否存在小于等于key的鍵底靠，若有則返回那個(gè)節(jié)點(diǎn)，沒(méi)有則返回當(dāng)前節(jié)點(diǎn)
                Node t = floor(x.right, key);
                if (t != null) return t;
                else return x;
            }
        }
        public Key select(int k){
            return select(root,k).key;
        }
        private Node select(Node x, int k) {
            if (x == null) {
                return null;
            }
            int t = size(x.left);
            if (t > k) {
                return select(x.left, k);
            } else if (t < k) {
                return select(x.right, k - t - 1);
            } else {
                return x;
            }
        }
        public void deleteMin(){
            root = deleteMin(root);
        }
        private Node deleteMin(Node x) {
            if (x.left == null) return x.right;
            x.left = deleteMin(x.left);
            x.N = size(x.left) + size(x.right) + 1;
            return x;
        }

        public void delete(Key key){
            root = delete(root,key);

        }
        private Node delete(Node x, Key key) {
            if(x == null) return null;
            int cmp = key.compareTo(x.key);
            if(cmp<0){
                x.left = delete(x.left,key);
            }else if(cmp>0){
                x.right = delete(x.right,key);
            }else{
                if(x.right == null) return x.left;
                if(x.left == null) return x.right;
                Node t = x;
                x = min(t.right);
                x.right = deleteMin(t.right);
                x.left = t.left;
            }
            x.N = size(x.left) + size(x.right) +1;
            return x;
        }
        public Queue<Key> keys(Key lo,Key hi){
            Queue<Key> queue = new Queue<Key>();
            keys(root,queue,lo,hi);
            return  queue;
        }

        private void keys(Node x, Queue<Key> queue,Key lo,Key hi){
            if(x == null){
                return ;
            }
            int cmplo = lo.compareTo(x.key);
            int cmphi = hi.compareTo(x.key);
            if(cmplo<0){
                keys(x.left,queue,lo,hi);
            }
            if(cmplo<=0&&cmphi>=0){
                queue.enqueue(x.key);
            }
            if(cmphi>0){
                keys(x.right,queue,lo,hi);
            }
        }
    }
}

package BinaryTree.BinarySearchTree;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import sun.misc.Queue;

import static org.junit.Assert.*;

public class BTSTest {
    BTS<Character, Integer> bts = new BTS<Character, Integer>();
    Character ch[] = {'E', 'A', 'S', 'Y', 'Q', 'E', 'S', 'T', 'I', 'O', 'N'};
    BTS.Node node = bts.new Node();

    @Before
    public void testBefore() {
        for (int i = 1; i <= ch.length; i++) {
            node.put(ch[i - 1], i);
        }
    }

    @Test
    public void testPut() {
        //先序遍歷一下
        node.preOrder();
        System.out.println();
        //求樹(shù)高度
        System.out.print(node.height());
    }

    @Test
    public void testGet() {
        //asn = 7
        System.out.println(node.get('S'));
    }
    @Test
    public void testFloor(){
        //找小于F的最大鍵,ans = E
        System.out.println(node.floor('F'));
    }
    @Test
    public void testSelect(){
        //選出比5個(gè)鍵大的那個(gè)鍵asn = Q
        System.out.println(node.select(5));
    }
    @Test
    public void testDeleteMin(){
        node.deleteMin();
        node.preOrder();
    }
    @Test
    public void testDelete(){
        node.delete('E');
        node.preOrder();
    }
    @Test
    public void testKeys() throws InterruptedException {
        Queue<Character> queue = node.keys('I','T');
        while (!queue.isEmpty()){
            System.out.print(queue.dequeue());
        }
    }
}

代碼中生成的樹(shù)

3.5 完美平衡

• 實(shí)現(xiàn)一個(gè)和二分查找等價(jià)的二叉查找樹(shù)特铝。也就是說(shuō)在這棵樹(shù)中查找任意鍵所產(chǎn)生的比較序列和二分查找所產(chǎn)生的完全相同暑中。

    @Test
    public void testPrefect(){
        Arrays.sort(ch);
        prefect(ch,0,ch.length-1);
        bts.preOrder();
    }
    private void prefect(Character []a,int lo, int hi){
        if(lo > hi) return ;
        int mid = lo + ((hi - lo)>>1);
        bts.put(a[mid],mid);
        prefect(a,lo,mid-1);
        prefect(a,mid +1 ,hi);
    }