1 定义

• 一棵二叉查找树（BST）是一棵二叉树，其中每个结点都含有一个Comparable的键（以及相关的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

2 基本实现

• 一棵二叉查找树代表的是一组键（及其相应的值）的集合，而同一个集合可以用多棵不同的二叉查找树表示。但注意，将一棵二叉查找树的所以键投影到一条直线上，保证一个节点的左子树的键出现在其左边，右子树的键出现在其右边。
  不同二叉查找树表示同一个集合
• 下面给出二叉查找树的实现代码,接下来将对这些方法进行解释：

package BinaryTree.BinarySearchTree;

public class BTS<Key extends Comparable<Key>, Value> {
    //二叉树根节点
    private Node root;

    private class Node {
        private Key key; //键
        private Value value;//值
        private Node left, right;//左节点和右节点
        private int N;//以该节点为根的子树中的节点总数

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

        //以该节点为根的子树中的节点总数
        public int size() {
            return size(root);
        }

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

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

        public Value get(Node x, Key key) {
            //如果树为空，则返回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);
            }
        }

        //插入某个值
        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 查找

• 查找只会获得两种结果，一是含有该节点，二是不含该节点返回Null.
• 递归算法：①如果树是空的，则返回null②如果被查找的键和根节点键相同，则查找命中，返回该节点③否则递归地在适当的子树中进行查找，如果被查找的键小于该节点就选择左子树，否则选择右子树。上面代码中get()函数完全按照这种思想进行的

• 代码运行流程实例如下：

  
  查找流程

2.2 插入

• 插入同样会产生两种后果，一是该节点已经存在，则更新该结点的值（Value），二是该节点不存在，则生成一个节点插入。
• 递归算法：①如果该树是空的，则返回一个含有该键值对的新结点②如果要插入的键已经存在且是当前结点，则修改其value值③如果被插入的键小于根节点，则在左子树中插入该键，否则在右子树中插入。
• 注意：结点还有一个属性N（代码以该结点为根节点的子树的结点数量），在进行插入后需要修改该值。*将递归调用前的代码想象成沿着树向下走（比较键大小），那递归后调用的代码想象成沿着树向上爬（对于get()方法，这仅代表一系列的返回指令return,但对于put()方法，这意味着重置N值）
• 上面代码中put()函数完全按照这种思想进行的

• 运行流程示例如下：

  
  插入流程

2.3 最大键和最小键

• 二叉查找树的根节点小于其右子树中的所有结点，大于其左子树中的所有结点。因策，最小键即最左下角的结点，最大键即最右下角的结点。
• 代码实现如下：

        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的最小键
• 算法思想：如果给定的键等于该根节点，则返回根节点;如果给定的键小于根节点的键，则小于等于key的最大键floor(key)在其左子树中；如果给定的键大于根节点的键，则仅当其右子树存在小于等于key的键时返回该键，否则就返回当前根节点的键。下面的代码完全按照该思想进行编码：

        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{
                //当找到小于key的键，要判断其右子树是否存在小于等于key的键，若有则返回那个节点，没有则返回当前节点
                Node t = floor(x.right, key);
                if (t != null) return t;
                else return x;
            }
        }

• 代码运行流程如下：

  
  floor

2.5 select选择操作

• 假设我们想找到排名为k的键（树中正好有k个小于它的键）。如果左子树中的结点t大于k，我们就继续在左子树中查找排名为k的键；如果t等于k，我们就返回根节点中的键；如果t小于k，就查找右子树中排名(k-t-1)的键。下面的代码完全按照该思想进行编码：

        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;
            }
        }

• 运行流程如下：

  
  select

2.6 删除最大键和最小键

• 删除最小键算法思想：只要不断深入左子树直至遇见一个空连接。

        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 删除任意键

• 将即将被删除的结点保存为t
• 将x 指向它的后继结点min(t.right)
• 将x的右链接指向deleteMin(t.right)
• 将x的左连接设为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;
        }

• 运行流程如下：

  
  运行流程

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 练习

3.1 插入练习

• 题目：将 E A S Y Q U E S T I O N 作为键按顺序插入一棵初始为空的二叉查找树。

    @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 插入顺序导致的最优与最劣二叉查找树结构

• A X C S E R H 顺序插入将会导致一棵最坏情况的二叉查找树，其最后一个结点两个链接全空，其余结点都含有一个空结点。树变为了链表。

• H C A E S R X便会产生最优的二叉查找树。

  
  插入顺序导致的不同

3.3 为二叉查找树添加查询树高度的方法

        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 方法测试

package BinaryTree.BinarySearchTree;


import sun.misc.Queue;

public class BTS<Key extends Comparable<Key>, Value> {
    //二叉树根节点
    public Node root;

    public class Node {
        private Key key; //键
        private Value value;//值
        private Node left, right;//左节点和右节点
        private int N;//以该节点为根的子树中的节点总数
        public Node(){

        }
        //构造方法
        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);
        }
        //以该节点为根的子树中的节点总数
        public int size() {
            return size(root);
        }

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

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

        private Value get(Node x, Key key) {
            //如果树为空，则返回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);
            }
        }

        //插入某个值
        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 {
                //当找到小于key的键，要判断其右子树是否存在小于等于key的键，若有则返回那个节点，没有则返回当前节点
                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();
        //求树高度
        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个键大的那个键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());
        }
    }
}

代码中生成的树

3.5 完美平衡

• 实现一个和二分查找等价的二叉查找树。也就是说在这棵树中查找任意键所产生的比较序列和二分查找所产生的完全相同。

    @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);
    }