二分查找树

Author Avatar
Brian Lee 9月 01, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:二分查找树


原理

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

将链表插入的灵活性和有序数组查找的高效性结合起来。

二叉查找树


数据表示

方法

嵌套定义一个私有类来表示二叉树上的一个结点。

每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器。

左链接指向一棵由小于该结点的所有键组成的二叉查找树,右链接指向一棵由大于该结点的所有键组成的二叉查找树。

变量 $N$ 给出了以该结点为根的子树的结点总数。

代码

private class Node {
        private Key key;    //键
        private Value val;  //值
        private Node left, right;   //指向左右子树的链接
        private int N;  //以该结点为根的子树中的结点总数
        public Node (Key key, Value val, int N) {
            this.key = key;
            this.val = val;
            this.N = N;
        }
    }

图示

如果将一棵二叉查找树的所有键投影到一条直线上,可以得到一条有序的键列。

键列


API

public class BST <Key extends Comparable<Key>, Value>

函数 作用
boolean isEmpty() 判断是否为空
boolean contains(Key key) 判断是否包含某个键
int size() 获取二叉查找树大小
int size(Node x) 获取某个结点大小
int size(Key lo, Key hi) 获取键序[lo..hi]大小
Value get(Key key) 通过键获取值
void put(Node x, Key key, Value val) 插入结点
Key min() 找最小的键
key max() 找最大的键
Key floor() 向下取整
Key ceiling() 向上取整
Key select(int k) 按顺序k选择键
int rank(Key key) 返回键key的排名
void deleteMin() 删除最小键结点
void deleteMax() 删除最大键结点
void delete(Key key) 删除键为key的结点
void print() 打印所有键
Iterable <Key> keys() 返回所有键
Iterable <Key> keys(Key lo, Key hi) 返回[lo..hi]间的键
int height() 返回树的高度(一个结点的树高度为0)
Iterable <Key> levelOrderKeys 按照二叉树的层返回键
boolean isBST() 判断是否为二分查找树
boolean isSizeCorrect() 判断结点数是否正确
boolean isRankConsistent() 检查顺序是否连续

查找

原理

在二分查找树中进行查找可能结果有两种:查找命中,返回相应值;查找未命中,返回null。

如果树是空的,则查找未命中;如果被查找的键和根结点的键相等,查找命中,否则在适当的子树中继续查找(被查找键较小就选择左子树,否则选择右子树)。

图示

查找

代码

递归
public Value get(Key key) {
        return get(root, key);
    }
//在以x为根结点的子树中查找并返回key对应的值
//如果找不到则返回null
private Value get(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return get(x.left, key);
        else if (cmp > 0)
            return get(x.right, key);
        else
            return x.val;
    }
非递归
public Value get2(Key key) {
        Node x = root;
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0)    x = x.left;
            else if (cmp > 0)   x = x.right;
            else    return x.val;
        }
        return null;
    }

插入

原理

递归过程中,如果当前结点为空,则返回一个含有该键值对的新结点。

如果被查找的键小于当前结点的键,继续在左子树中插入该键,否则在右子树中插入该键。

且要增加路径上每个结点中的计数器的值。

图示

插入

代码

递归
public void put(Key key, Value val) {
        root = put(root, key, val);
    }
//如果key存在于以x为结点的子树中则更新它的值
//否则将以key和val为键值对的新结点插入到该子树中
private Node put(Node x, Key key, Value val) {
        if (x == null)
            return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = put(x.left, key, val);
        else if (cmp > 0)
            x.right = put(x.right, key, val);
        else
            x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
非递归

需保存一个指向底层结点的链接,以便使之成为新结点的父结点。

还需要额外遍历一遍查找路径来更新所有的结点计数器以保证结点插入的正确性。

public void put2(Key key, Value val) {
        Node x = root;
        Node t = root;
        int cmp = 0;
        while (x != null) {
            cmp = key.compareTo(x.key);
            if (cmp < 0) {
                t = x;
                x = x.left;
            }
            else if (cmp > 0) {
                t = x;
                x = x.right;
            }
            else  {
                x.val = val;
                return;
            }
        }
        if (cmp < 0)    t.left = new Node(key, val, 1);
        else if (cmp > 0)    t.right = new Node(key, val, 1);
        x = root;
        //更新结点计数器
        while (true) {
            int cmpa = key.compareTo(x.key);
            if (cmpa < 0) {
                x.N++;
                x = x.left;
            }
            else if (cmpa > 0) {
                x.N++;
                x = x.right;
            }
            else    break;
        }
    }

最大最小键

原理

找最小键即为递归遍历左结点,直到某结点左子结点为空,此结点便为最小键。最大键相反。

代码

//找最小的键
public Key min() {
        return min(root).key;
    }
private Node min(Node x) {
        if (x.left == null)     return x;
           return min(x.left);
}
//找最大的键
public Key max() {
        return max(root).key;
    }
private Node max(Node x) {
        if (x.right == null)    return x;
        return max(x.right);
    }

向下取整与向上取整

原理

如果给定键key小于二叉查找树的根结点的键,那么小于等于key的最大键(floor)一定在根结点的左子树中;如果给定的键key大于二叉查找树的根结点,那么只有当根结点右子树中存在小于等于key的结点时,小于等于key的最大键才会出现在右子树中,否则根结点就是小于等于key的最大键。

图示

取整

代码

//向下取整
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);
        Node t = floor(x.right, key);
        if (t != null)  return t;
        else    return x;
    }
//向上取整
public Key ceiling(Key key) {
        Node x = ceiling(root, key);
        if (x == null)  return null;
        return x.key;
    }
private Node ceiling(Node x, Key key) {
        if (x == null)  return null;
        int cmp = key.compareTo(x.key);
        if (cmp == 0)   return x;
        else if (cmp < 0) {
            Node t = ceiling(x.left, key);
            if (t != null)  return t;
            else    return x;
        }
        return ceiling(x.right, key);
    }

选择与排名

原理

要找到排名为k的键,如果左子树中的结点数t大于k,那么就(递归地)继续在左子树中查找排名为k的键;如果t等于k,就返回根结点中的键;如果t小于k,就在右子树中查找排名为(k-t-1)的键。

排名则为选择的逆方法。如果给定的键和根结点的键相等,则返回左子树中的结点总数t;若小于,则返回该键在左子树中的排名(递归);若大于,返回t+1(根结点)加上它在右子树中的排名。

图示

选择

代码

//按顺序选择
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 int rank(Key key) {
        return rank(root, key);
    }
private int rank(Node x, Key key) {
        if (x == null)  return 0;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)    return rank(x.left, key);
        else if (cmp > 0)   return 1 + size(x.left) + rank(x.right, key);
        else    return size(x.left);
    }

删除最大最小键

原理

以删除最小键为例:不断深入根结点的左子树直至遇见一个空链接,然后将指向该结点的链接指向该结点的右子树,并更新该结点到根结点路径上的计数器的值。

图示

删除

代码

//删除最小键结点
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 deleteMax() {
        root = deleteMax(root);
    }
private Node deleteMax(Node x) {
        if (x.right == null)    return x.left;
        x.right = deleteMin(x.right);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

删除

原理

  • 将指向即将被删除的结点的链接保存为t
  • 将x指向它的后继结点min(t.right)
  • 将x的右链接(原本指向一棵所有结点都大于x.key的二叉查找树)指向deleteMin(t.right),也就是在删除后所有结点仍都大于x.key的子二叉查找树
  • 将x的左链接(本为空)设为t.left(其下所有的键都小于被删除的结点和它的后继结点)
  • 修正计数器

图示

删除

代码

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 void print() {
        print(root);
    }
private void print(Node x) {
        if (x == null)  return;
        print(x.left);
        System.out.print(x.key);
        System.out.print(" ");
        print(x.right);
    }

范围查找

原理

将所有落在给定范围以内的键加入到一个队列Queue,并跳过不可能含有所查找键的子树。

图示

遍历

代码

public Iterable<Key> keys() {
        return keys(min(), max());
    }
public Iterable<Key> keys(Key lo, Key hi) {
        Queue<Key> queue = new LinkedList<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);    //lo<x.key
        if (cmplo <= 0 && cmphi >= 0)   queue.offer(x.key); //lo<=x.key<=hi
        if (cmphi > 0)  keys(x.right, queue, lo, hi);   //x.key<hi
    }

高度

说明

在此,一个结点的树高度为0

代码

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

按层遍历

原理

使用queue将每层的结点存入,按顺序进行遍历

代码

public Iterable<Key> levelOrderKeys() {
        Queue<Key> keys = new LinkedList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node x = queue.poll();
            if (x == null)  continue;
            keys.offer(x.key);
            queue.offer(x.left);
            queue.offer(x.right);
        }
        return keys;
    }

判断BST

原理

判断是否为BST,就是检查是否满足左子树所有结点的键小于根结点,右子树所有结点的键大于根结点。

代码

public boolean isBST() {
        return isBST(root, null, null);
    }
private boolean isBST(Node x, Key min, Key max) {
        if (x == null)  return true;
        if (min != null && x.key.compareTo(min) <= 0)
            return false;
        if (max != null && x.key.compareTo(max) >= 0)
            return false;
        return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
    }

检查结点数

原理

当每个结点的N等于左右子结点N之和加1时,结点数全部正确

代码

public boolean isSizeCorrect() {
        return isSizeCorrect(root);
    }
private boolean isSizeCorrect(Node x) {
        if (x == null)  return true;
        if (x.N != size(x.left) + size(x.right) + 1)
            return false;
        return isSizeCorrect(x.left) && isSizeCorrect(x.right);
    }

检查顺序

原理

通过检查rank()和select()是否匹配

代码

public boolean isRankConsistent() {
        for (int i = 0; i < size(); i++)
            if (i != rank(select(i)))   return false;
        for (Key key : keys())
            if (key.compareTo(select(rank(key))) != 0)
                return false;
        return true;
    }

符号表性能比较

数据结构 查找(最坏) 插入(最坏) 查找(平均) 插入(平均) 是否支持有序性相关操作
顺序查询(无序链表) $N$ $N$ $N/2$ $N$
二分查找(有序数组) $logN$ $N$ $lgN$ $N/2$
二分树查找(二分查找树) $N$ $N$ $1.39logN$ $1.39logN$

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S3_Searching/S3_2_Bianry_Search_Trees


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/09/01/BST/