算法红皮书 3.2.1
2022年6月12日 22:09 周日二叉查找树 #
使用每个结点含有两个链接（链表中每个结点只含有一个链接）的二叉查找树来高效地实现符号表
该数据结构由结点组成，结点包含的链接可以为空(null)或者指向其他结点
一棵二叉查找树（BST）是一棵二叉树，其中每个结点都含有一个Comparable 的键（以 及相关联的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。
基本实现 #
数据表示
- 每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器 左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该节点的所有键组成的二叉查找树，变量N给出了以该结点为根的子树的结点总数
- 对于任意节点总是成立 size(x)=size(x.left)+size(x.right)+1
多棵二叉查找树表示同一组有序的键来实现构建和使用二叉查找树的高校算法
查找
- 在符号表中查找一个键可能得到两种结果：如果含有该键的结点存在表中，我们的查找就命中了，然后返回值；否则查找未命中（返回null)
- 递归：如果树是空的，则查找未命中；如果被查找的键和根节点的键相等，查找命中，否则在适当的子树中查找：如果被查找的键较小就选择左子树，否则选择右子树
- 下面的get()方法，第一个参数是一个结点（子树根节点），第二个参数是被查找的键，代码会保证只有该结点所表示的子树才会含有和被查找的键相等的结点
- 从根结点开始，在每个结点中查找的进程都会递归地在它的一个子结点上展开，因此一次查找也就定义了树的一条路径。对于命中的查找，路径在含有被查找的键的结点处结束。对于未命中的查找，路径的终点是一个空链接
基于二叉查找树的符号表
public class BST<Key extends Comparable<Key>, Value> { private Node root; // 二叉查找树的根结点 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; } } 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) // 请见算法3.3（续1） public void put(Key key, Value val) // 请见算法3.3（续1） // max()、min()、floor()、ceiling()方法请见算法3.3（续2） // select()、rank()方法请见算法3.3（续3） // delete()、deleteMin()、deleteMax()方法请见算法3.3（续4） // keys()方法请见算法3.3（续5） }- 每个Node 对象都是一棵含有N 个结点的子树的根结点，它的左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找 树。root 变量指向二叉查找树的根结点Node 对象（这棵树包含了符号表中的所有键值对）
二叉查找树的查找和排序方法的实现
...
