平衡查找树定义（BINARY SEARCH TRE 后面我们写作BSTs）
一个具有如下性质的二叉树
- 每一个节点都具有一个key，它左侧节点的key不大于它
- 它的右侧节点的key不小于它。
BST节点定义
private class Node
{
private Key key;
private Value val;
private Node left, right;
public Node(Key key, Value val)
{
this.key = key;
this.val = val;
}
}
BST定义
public class BST<Key extends Comparable<Key>, Value>
{
private Node root;
private class Node
//插入 如果已经存在则替换，否则插入新节点
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);
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 if (cmp == 0)
x.val = val;
return x;
}
//查找时，如果小于当前节点，那么查找右边，如果大于当前节点，那么查找左边
public Value get(Key key)
{
Node x = root;
while (x != null)
{
int cmp = key.compareTo(x.key);
if (cmp < 0) x = x.left;
else if (cmp > 0) x = x.right;
else if (cmp == 0) return x.val;
}
return null;
}
public void delete(Key key)
public Iterable<Key> iterator()
}
算法复杂度分析
跟树相关的算法，其复杂度往往决定于树的形状，两边对称的树和只偏向一边的树，其复杂度差别为lgN与N2。
当不存在重复节点时，BST在结构上与快速排序上是对应，从左向右有序。
屏幕快照 2018-09-10 下午3.23.00.png
一些应用
给定一个值k，获取该值在BST中的向上值与向下值，即ceil floor.通俗的说，如果BST中全是整数，那么就是向上与向下取整。
以向下为例
- 如果在BST中找到了k，那么return k。
- 如果root大于k,那么查找左侧子树，直到找到第一个小于k的节点
- 如果root小于k,那么查找右侧子树，直到找到第一个大于k的节点时，返回其父节点。
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;
}
顺序遍历
public Iterable<Key> keys()
{
Queue<Key> q = new Queue<Key>();
inorder(root, q);
return q;
}
//先遍历左子树，再遍历右子树。其实就是树的中序遍历
private void inorder(Node x, Queue<Key> q)
{
if (x == null) return;
inorder(x.left, q);
q.enqueue(x.key);
inorder(x.right, q);
}
节点的删除
懒方法
找到这个节点后，直接将这个节点的值置为null。然后当它不存在
标准方法
将节点分为三种情况：
- 这个节点是叶子节点
直接删除即可 - 这个节点没有左子树或者右子树
将子树的root替代被删除节点 -
这个节点既有左子树也有右子树
这中情况较为复杂：
屏幕快照 2018-09-10 下午4.46.02.png
代码实现
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.count = size(x.left) + size(x.right) + 1;
return x;
}
