定义：一个二叉查找树是一棵二叉树，其中每个节点都含有一个Comparable键（以及相关联的值），且每个节点中的键都大于其左子树中的任意节点的键，而小于右子树任意节点的键。
下面是完整的代码：
public class BinarySearchTree<Key extends Comparable<Key>, Value> {
private Node root;
public BinarySearchTree() {
}
private class Node {
private Key key;
private Value value;
private Node left;
private Node right;
private int size; //以该节点为根的字树中的节点总数（包括自身）
public Node(Key key, Value value, int size) {
this.key = key;
this.value = value;
this.size = size;
}
}
public void put(Key key, Value value) {
if (key == null) throw new IllegalArgumentException("called put() with a null key");
if (value == null) { //插入一个value为null的值代表要删除他
delete(key);
return;
}
root = put(root, key, value);
}
//递归在左右子树中查找直到找到合适位置插入，注意size值，从上往下递归再从下往上返回时重塑
size值
private Node put(Node node, Key key, Value value) {
if (node == null) return new Node(key, value, 1);
int cmp = key.compareTo(node.key);
if (cmp < 0) node.left = put(node.left, key, value);
else if (cmp > 0) node.right = put(node.right, key, value);
else node.value = value;
node.size = size(node.left) + size(node.right) + 1;
return node;
}
public Value get(Key key) {
return get(root, key);
}
private Value get(Node node, Key key) {
if (node == null) return null;
int cmp = key.compareTo(node.key);
if (cmp < 0) return get(node.left, key);
else if (cmp > 0) return get(node.right, key);
else return node.value;
}
//删除key键
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("called delete() with a null key");
root = delete(root, key);
}
private Node delete(Node node, Key key) {
if (node == null) return null; //key不存在
int cmp = key.compareTo(node.key);
if (cmp < 0) node.left = delete(node.left, key);
else if (cmp > 0) node.right = delete(node.right, key);
else {
if (node.left == null) return node.right; //左子树为空直接返回右子树
if (node.right == null) return node.left;
//左右子树都在的情况下，找到右子树中的最小节点，用它来代替被删除节点
Node temp = node;
node = min(node.right);
node.right = deleteMin(temp.right);
node.left = temp.left;
}
node.size = size(node.left) + size(node.right) + 1; //一个节点大小=左子树大小+右子树大小+1
return node;
}
//删除最大键
public void deleteMax() {
if (isEmpty()) throw new NoSuchElementException("called deleteMax() with empty symbol table");
root = deleteMax(root);
}
private Node deleteMax(Node node) {
if (node.right == null) return node.left;
node.right = deleteMax(node.right);
node.size = size(node.right) + size(node.left) + 1;
return node;
}
//删除最小键
public void deleteMin() {
if (isEmpty()) throw new NoSuchElementException("called deleteMin() with empty symbol table");
root = deleteMax(root);
}
private Node deleteMin(Node node) {
if (node.left == null) return node.right;
node.left = deleteMin(node.left);
node.size = size(node.left) + size(node.right) + 1;
return node;
}
public int size() {
return size(root);
}
private int size(Node node) {
if (node == null) return 0;
else return node.size;
}
private boolean isEmpty() {
return size() == 0;
}
public Key min() {
if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
return min(root).key;
}
private Node min(Node node) {
if (node.left == null) return node;
else return min(node.left);
}
public Key max() {
if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
return max(root).key;
}
private Node max(Node node) {
if (node.right == null) return node;
else return max(node.right);
}
/**
* 二叉树中小于等于key的最大key键
* @param key
* @return
*/
public Key floor(Key key) {
if (key == null) throw new IllegalArgumentException("called floor() with a null key");
if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
Node result = floor(root, key);
if (result == null) return null;
else return result.key;
}
//递归直到找到key返回，若没有相匹配的则返回最后一个比key小的node，即最后一个调用floor（node.right，key）的node。
原因如下：往左递归寻找是因为要找到一个小于key的node，往右找是因为找到了已经找到了一个小于key的node，
要往右找找有没有更接近key的node，所以最后一个调用floor（node.right，key）的node就是我们想要的值
private Node floor(Node node, Key key) {
if (node == null) return null; //表示树中没有与key相等的值
int cmp = key.compareTo(node.key);
if (cmp == 0) return node; //表示找到了与key相等的值
if (cmp < 0) return floor(node.left, key);
Node temp = floor(node.right, key);
if (temp != null) return temp;
else return node;
}
/**
* 大于等于key的最小key键
* @param key
* @return
*/
public Key ceiling(Key key) {
if (key == null) throw new IllegalArgumentException("called ceiling() with a null key");
if (isEmpty()) throw new NoSuchElementException("called ceiling() with empty symbol table");
Node result = ceiling(root, key);
if (result == null) return null;
else return result.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp > 0) return ceiling(x.right, key);
Node temp = ceiling(x.left, key);
if (temp != null) return temp;
else return x;
}
/**
* 返回的这个键在树中正好有k个小于它的键
* @param k
* @return
*/
public Key select(int k) {
if (k < 0 || k >= size())
throw new IllegalArgumentException("called select() with wrong number : " + k);
Node result = select(root, k);
return result.key;
}
private Node select(Node x, int k) {
int size = size(x.left);
if (k < size) return select(x.left, k);
else if (k > size) return select(x.right, k-size-1);
else return x;
}
//返回二叉树中小于key的node的个数
public int rank(Key key) {
if (key == null) throw new IllegalArgumentException("argument rank() is null");
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);
}
}
二叉查找树平均情况下查找和插入时间复杂需为1.39logn；最坏情况下为n。
网友评论