普林斯顿算法中级笔记8(平衡查找树)

平衡查找树定义（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与N²。
当不存在重复节点时，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;
 }