算法3.3基于二叉查找树的符号表
《算法》笔记导航
《算法》中文第四版P252-P261
2020.8.4
@Stream_
public class BST <Key extends Comparable<Key>,Value>
将链表插入的灵活性和有序数组查找的高效性结合起来的符号表
一、变量，方法，类及其作用
1.变量
-
private Node root;
二叉查找树的根节点
2.类
-
private class Node
用于储存节点
2.1类的变量
-
private Key key;
键，用于储存和查找，具有唯一性 -
private Value val;
值，通过键来获取值，数据结构和算法直接影响获取值修改值的效率 -
private Node left,right;
左右子节点
左子比父节点小，右子比父节点大。代表左子的任意子节点都比当前的父节点小，右子的任意子节点都比当前的父节点大。 -
private int N;
节点计数器，记录以该节点为根的子树中的结点总数
2.2类的构造函数
-
public Node(Key key,Value val,int N)
逐一赋值
3.方法
3.1获取节点个数、获取指定键的值、修改或添加指定键的值
-
public int size()
返回总根节点的节点个数
private int size(Node x) -
public Value get(Key key)
获取指定值key相对应的value值
private Value get(Node x,Key key)
如果树是空的，则查找未命中。
如果被查找的键和根节点（递归路径上的每一个节点）的键相等，查找命中。
如果被查找的键较小就选择左子树，较大则选择右子树。 -
public void put(Key key,Value val)
如果找到指定的key值，则更新为val，如果没有找到，则在恰当的位置新建节点
private Node put(Node x,Key key,Value val)
和get类似，循环查找，如果结果是null返回一个新节点。
3.2获取最小值，向下取整
-
public Key min()
获取最小值
private Node min(Node x)
如果左链接为空，则最小值为根节点（这里的根节点依旧是递归的根节点，指的不仅是root节点），
如果左链接非空，树中的最小键就是左子树种的最小键。 -
public Key floor(Key key)
向下取整，获取小于等于key的最大值
private Node floor(Node x,Key key)
如果给定的键key小于二叉查找树的根节点（递归的根节点）的键，那么小于等于key的最大键floor(key)一定在根节点的左子树中
如果给定的键key大于二叉查找树的根结点（递归的根节点），只有当右子树存在小于等于key的节点时，小于等于key的最大键才会出现在右子树中，否则根节点就是小于等于key的最大键。
3.3获取指定排名的key值，查询key值的排名
-
public Key select(int k)
返回排名为k的节点的key值（树中正好有k个小于它的键）
private Node select(Node x,int k)
如果左子树（递归的左子树）中的结点数t大于k，就继续（递归的）在左子树中查找排名为k的键
如果t等于k，就返回根结点中的键
如果t小于k，就递归的在右子树中查找排名为（k-t-1）的键 -
public int rank(Key key)
rank()是select()的逆方法，查询key的位置（之前有多少个元素）
private int rank (Key key,Node x)
它的实现和select()类似，如果给定的键和根结点（递归的根节点）的键相等，返回左子树中的结点总数
如果给定的键小于根节点，返回该键在左子树中的排名（递归计算）
如果给定的键大于根节点，返回t+1加上它在右子树中的排名（递归计算）
3.4删除最小值和删除指定key值
-
public void deleteMin()
删除最小的键
private Node deleteMin(Node x)
要不断深入根节点的左子树中直到遇见一个空链接，然后将指向该节点的链接指向该节点的右子树（需要在递归调用中返回它的右链接） -
public void delete(Key key)
删除指定的键，对于有两个子节点的节点，用T.Hibbard的方法解决
在删除结点x后用它的后继节点填补它的位置，因为它有右子节点，它的后继节点就是其右子树中的最小节点
private Node delete(Node x,Key key)
将指向即将被删除的节点的链接保存为t
将x指向它的后继节点min(t.right)
将x的右链接（原本指向一棵所有节点都大于x.key的二叉查找树）指向deletMin(t.right)，也就是在删除后所有节点仍然都大于x.key的子二叉查找树
将x的左链接（本为空），设为t.left（其下所有的键都小于被删除的结点和它的后继结点）
二、算法的实现
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){ //获取指定值key相对应的value值
return get(root,key);
}
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 void put(Key key,Value val){ //如果找到指定的key值，则更新为val，如果没有找到，则新建节点
root=put(root,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 Key min(){ //获取最小值
return min(root).key;
}
private Node min(Node x){
if(x.left==null){
return x;
}
return min(x.left);
}
public Key floor(Key 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;
}
if(cmp<0){
return floor(x.left,key);
}
Node t=floor(x.right,key);
if(t!=null){
return t;
}
else {
return x;
}
}
public Key select(int k){ //返回排名为k的节点的key值（树中正好有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){ //查询key的位置（之前有多少个元素）
return rank(key,root);
}
private int rank (Key key,Node x){
if(x==null){
return 0;
}
int cmp=key.compareTo(x.key);
if(cmp<0){
return rank(key,x.left);
}
else if(cmp>0){
return 1+size(x.left)+rank(key,x.right);
}
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 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;
}
}
三、算法的优劣、注意和使用场景
- 1.优点：实现简单，能够进行有序性相关操作
- 2.缺点：没有性能上届的保证，链接需要额外的空间
- 3.树的高度决定了所有操作在最坏情况下的性能
- 4.一般使用非递归效率会更高，为了方便修改和说明教学，选择了递归进行展示
- 5.本例展示的delete()方法缺陷是在某些实际应用中产生性能问题，问题在于选用后继结点时随意的决定，没有考虑对称性。应当前驱节点和后继结点的选择时随机的。
《算法》笔记导航
渣渣菜鸡，难免错误，请友善讨论
非商用转载需注明作者及文章链接来源，私信告知后无需我回复即可直接转载
