## 二叉查找树 转

AllenOR灵感

``````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。

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);
}

}
``````

### AllenOR灵感

#### 暂无文章

rime设置为默认简体

zhenruyan

5
0

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快，要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率，发送方的发送窗口大小不能超过接收方给出窗口大小。...

10
0
OSChina 周日乱弹 —— 别问，问就是没空

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @tom_tdhzz ：#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌，请使劲儿戳（这里） @wqp0010 :周...

1K
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

5
0
Spring Context 你真的懂了吗

Java知其所以然

9
0