查找----基于二叉查找树
参照数据结构--符号表API实现。
首先，定义二叉树结点类：
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;
}
}其中N为以该节点为根的子树的节点总数，计算方法如下：
size(x) = size(x.left) + size(x.right) + 1;
查找方法：递归查找，如果小于当前结点，递归去左子树查找；如果大于当前结点，递归去右子树查找。
public Value get(Key key) {
return get(root,key);
}
public 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);
if(cmp>0) return get(x.right,key);
else return x.val;
}插入方法：先查找，如果树中已经存在相应的键，只需更新值；如果查询无果，指针也已经指向了应该插入的位置，用要插入的键值对新创结点并插入到相关位置。
public void put(Key key,Value 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);//插入左子树
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;
}floor()方法和ceiling()方法：
floor()方法要求找出小于等于给定键的最大键；ceiling()方法要求找出大一等于给定键的最小键。
floor()方法实现：如果给定的键小于根节点，则目标节点在左子树中；如果给定的键大于根节点，当右子树存在小于等于给定节点的值时则在右子树中，否则根节点就是目标节点。
seiling()方法和floor()方法实现方法一样，将“左”变成“右”（同时将小于变成大于）即可实现。
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;
if(cmp < 0) return floor(x.left,key);
Node t = floor(x.right, key);
if(t != null) return t;
else return x;
}select()方法：
目标是排名第k的键，如果根节点左子树结点数小于k,则递归在左子树中查找；如果等于k,则就是根节点；如果大于k,则在右子树中查找排名为（k-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<0) return select(x.left,k);
else if(t>0) return select(x.right,k);
else return x;
}rank()方法：
rank()方法返回给定键的排名，它是select()的逆方法。如果给定的键等于根节点的键，返回左子树节点数；如果小于，递归返回该键在左子树中的排名；如果大于，返回（t+1+它在右子树中的排名）。
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);
}删除操作：
- 即将被删除的节点记为t;
- x指向它的后继节点min(t.right);
- 将x的右链接链接到x的父节点的左链接上（即替换掉原x的位置）；
- 用x节点替换t节点（将t.left和t.right设为x.left和x.right）；
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);
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;
}遍历操作：
对二叉树的遍历可以分为前序遍历，中序遍历和后续遍历。中序遍历如下，前序和后序遍历只需调整一下语句顺序即可。
private void print(Node x){
if(x == null) return ;
print(x.left);
System.out.print(x.key);
print(x.right);
}性能分析：
在一棵二叉查找树中，所有操作在最坏情况下所需时间都和输的高度成正比。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读