《算法》第三章部分程序 part 2
2024-08-29 09:19:50
▶ 书中第三章部分程序，加上自己补充的代码，平衡二叉搜索树
● 平衡二叉搜索树
package package01; import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01<Key extends Comparable<Key>, Value>
{
private class Node // 二叉树节点
{
private Key key;
private Value val;
private Node left, right;
private int size; // 节点总数（包括根节点和子树） public Node(Key key, Value val, int size)
{
this.key = key;
this.val = val;
this.size = size;
}
} private Node root; // 二叉树根节点 public class01() {} public int size()
{
return size(root);
} private int size(Node x)
{
if (x == null)
return 0;
return x.size;
} public boolean isEmpty()
{
return size() == 0;
} public Value get(Key key) // 查找
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
return getKernel(root, key);
} private Value getKernel(Node x, Key key) // 查找内核，递归地向下找
{
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return getKernel(x.left, key);
if (cmp > 0)
return getKernel(x.right, key);
return x.val;
} public boolean contains(Key key) // 判断 key 是否在树中
{
if (key == null)
throw new IllegalArgumentException("\n<contains> key == null.\n");
return get(key) != null;
} public void put(Key key, Value val) // 插入
{
if (key == null)
throw new IllegalArgumentException("\n<put> key == null.\n");
if (val == null) // 空值插入作删除处理
delete(key);
else
root = putKernel(root, key, val);
//assert check(); // 对树作修改时需要检查
} private Node putKernel(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 = putKernel(x.left, key, val);
else if (cmp > 0)
x.right = putKernel(x.right, key, val);
else
x.val = val;
x.size = 1 + size(x.left) + size(x.right);
return x;
} public void deleteMin() // 删除最小节点（先根序首节点）
{
if (isEmpty())
throw new NoSuchElementException("\n<deleteMin> underflow.\n");
root = deleteMinKernel(root);
//assert check();
} private Node deleteMinKernel(Node x) // 删除最小节点内核
{
if (x.left == null) // 左子树为空，返回右子树（相当于删除根节点）
return x.right;
x.left = deleteMinKernel(x.left); // 左子树不空，继续往下找
x.size = size(x.left) + size(x.right) + 1; // 重新计算输的大小
return x;
} public void deleteMax() // 删除最大节点（先根序末节点）
{
if (isEmpty())
throw new NoSuchElementException("\n<deleteMax> underflow.\n");
root = deleteMaxKernel(root);
//assert check();
} private Node deleteMaxKernel(Node x)
{
if (x.right == null) // 右子树为空，返回左子树（相当于删除根节点）
return x.left;
x.right = deleteMaxKernel(x.right); // 右子树不空，继续往下找
x.size = size(x.left) + size(x.right) + 1; // 重新计算输的大小 return x;
} public void delete(Key key) // 删除指定 key 的节点
{
if (key == null)
throw new IllegalArgumentException("\n<delete> key == null.\n");
root = deleteKernel(root, key);
//assert check();
} private Node deleteKernel(Node x, Key key) // 删除节点内核
{
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp < 0)
x.left = deleteKernel(x.left, key);
else if (cmp > 0)
x.right = deleteKernel(x.right, key);
else // 找到了目标键
{
if (x.right == null) // 右子树为空就返回左子树，左子树为空就返回右子树
return x.left;
if (x.left == null)
return x.right;
Node t = x; // 左右子树都不空，设这里中根序遍历为 x -> a -> b
x = min(t.right); // 找到 t 在中根序的下一个节点 a，赋给 x（结束后 x 的左子树一定为空）
x.right = deleteMinKernel(t.right); // 删除节点 a，删除函数返回 a 的下一个节点 b，赋给 x 的右子树
x.left = t.left; // 原来的的左子树接到 x 的左子树
}
x.size = 1 + size(x.left) + size(x.right);
return x;
} public Key min() // 返回最小键
{
if (isEmpty())
throw new NoSuchElementException("\n<delete> empty.\n");
return minKernel(root).key;
} private Node minKernel(Node x) // 最小节点内核，需要递归
{
if (x.left == null)
return x;
return minKernel(x.left);
} public Key max() // 返回最大键
{
if (isEmpty())
throw new NoSuchElementException("\n<max> empty.\n");
return maxKernel(root).key;
} private Node maxKernel(Node x) // 最大节点内核，需要递归
{
if (x.right == null)
return x;
return maxKernel(x.right);
} public Key floor(Key key) // 返回不大于 key 的最大元素的键，不存在
{
if (key == null)
throw new IllegalArgumentException("\n<floor> key == null.\n");
if (isEmpty())
throw new NoSuchElementException("\n<floor> empty.\n");
Node x = floorKernel(root, key);
return (x == null) ? null : x.key;
} private Node floorKernel(Node x, Key key) // floor 内核，需要递归
{
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp == 0)
return x;
if (cmp < 0)
return floorKernel(x.left, key);
Node t = floorKernel(x.right, key); // 目标键较大时需要递归搜索
return (t == null) ? x : t; // 在母栈中保存了当前最好的结果 x，没有实现尾递归
} public Key floor2(Key key) // floor 的尾递归实现
{
return floor2Kernel(root, key, null);
} private Key floor2Kernel(Node x, Key key, Key best) // 调用时带上当前已经找到的最佳值
{
if (x == null)
return best;
int cmp = key.compareTo(x.key);
if (cmp == 0)
return x.key;
if (cmp < 0)
return floor2Kernel(x.left, key, best);
return floor2Kernel(x.right, key, x.key);
} public Key ceiling(Key key) // 返回不小于 key 的最大元素的键
{
if (key == null)
throw new IllegalArgumentException("\n<ceiling> key == null.\n");
if (isEmpty())
throw new NoSuchElementException("\n<ceiling> empty.\n");
Node x = ceilingKernel(root, key);
return (x == null) ? null : x.key;
} private Node ceilingKernel(Node x, Key key) // ceiling 内核，需要递归
{
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp == 0)
return x;
if (cmp > 0)
return ceilingKernel(x.right, key);
Node t = ceilingKernel(x.left, key);
return (t == null) ? x : t;
} public Key ceiling2(Key key) // ceiling 的尾递归实现
{
return ceiling2Kernel(root, key, null);
} private Key ceiling2Kernel(Node x, Key key, Key best)
{
if (x == null)
return best;
int cmp = key.compareTo(x.key);
if (cmp == 0)
return x.key;
if (cmp < 0)
return ceiling2Kernel(x.left, key, best);
return ceiling2Kernel(x.right, key, x.key);
} public Key select(int k) // 取出排第 k 的元素
{
if (k < 0 || k >= size())
throw new IllegalArgumentException("\n<select> k < 0 || k >= size().\n");
return selectKernel(root, k).key;
} private Node selectKernel(Node x, int k) // 取元素内核，需要递归
{
if (x == null)
return null;
int t = size(x.left); // 树的元素数用于来计数
if (k < t)
return selectKernel(x.left, k);
if (k > t)
return selectKernel(x.right, k - t - 1);
return x;
} public int rank(Key key) // 计算键比 key 小的元素个数
{
if (key == null)
throw new IllegalArgumentException("\n<rank> key == null.\n");
return rankKernel(key, root);
} private int rankKernel(Key key, Node x) // 计算函数内核，需要递归
{
if (x == null)
return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return rankKernel(key, x.left);
if (cmp > 0)
return 1 + size(x.left) + rankKernel(key, x.right);
return size(x.left);
} public Iterable<Key> keys() // 创建队列用于迭代器，中根序
{
if (isEmpty())
return new Queue<Key>();
Key lo = min(), hi = max();
if (lo == null)
throw new IllegalArgumentException("\n<iterable> lo == null.\n");
if (hi == null)
throw new IllegalArgumentException("\n<iterable> hi == null.\n");
Queue<Key> queue = new Queue<Key>();
keysKernel(root, queue, lo, hi);
return queue;
} private void keysKernel(Node x, Queue<Key> queue, Key lo, Key hi) // 创建迭代器内核，需要递归
{
if (x == null)
return;
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0)
keysKernel(x.left, queue, lo, hi);
if (cmplo <= 0 && cmphi >= 0)
queue.enqueue(x.key);
if (cmphi > 0)
keysKernel(x.right, queue, lo, hi);
} public Iterable<Key> levelOrder() // 生成先根序队列
{
Queue<Key> keys = new Queue<Key>();
Queue<Node> queue = new Queue<Node>();
for (queue.enqueue(root); !queue.isEmpty();)
{
Node x = queue.dequeue();
if (x == null)
continue;
keys.enqueue(x.key);
queue.enqueue(x.left);
queue.enqueue(x.right);
}
return keys;
} public int size(Key lo, Key hi) // 计算键落在给定范围内的元素个数
{
if (lo == null)
throw new IllegalArgumentException("\n<size> lo == null.\n");
if (hi == null)
throw new IllegalArgumentException("\n<size> hi == null.\n");
if (lo.compareTo(hi) > 0)
return 0;
if (contains(hi))
return rank(hi) - rank(lo) + 1;
return rank(hi) - rank(lo);
} public int height() // 计算树的高度
{
return heightKernel(root);
} private int heightKernel(Node x) // 计算树高度内核，需要递归，空树高度为 -1，根节点高度为 0
{
if (x == null)
return -1;
return 1 + Math.max(heightKernel(x.left), heightKernel(x.right));
} private boolean check() // 检查函数，用于 debug
{
if (!isBinarySearchST())
StdOut.println("\n<check> Not in symmetric order.\n");
if (!isSizeConsistent())
StdOut.println("\n<check> Subtree counts not consistent.\n");
if (!isRankConsistent())
StdOut.println("\n<check> Ranks not consistent.\n");
return isclass01() && isSizeConsistent() && isRankConsistent();
} private boolean isBinarySearchST() // 检查输的保序性
{
return isBinarySearchSTKernel(root, null, null);
} private boolean isBinarySearchSTKernel(Node x, Key min, Key max)
{
if (x == null)
return true;
if (min != null && x.key.compareTo(min) <= 0)
return false;
if (max != null && x.key.compareTo(max) >= 0)
return false;
return isBinarySearchSTKernel(x.left, min, x.key) && isBinarySearchSTKernel(x.right, x.key, max);
} private boolean isSizeConsistent() // 检查树的 size 是否正确
{
return isSizeConsistentKernel(root);
} private boolean isSizeConsistentKernel(Node x)
{
if (x == null)
return true;
if (x.size != size(x.left) + size(x.right) + 1)
return false;
return isSizeConsistentKernel(x.left) && isSizeConsistentKernel(x.right);
} private boolean isRankConsistent() // 检查 rank 和 select
{
for (int i = 0; i < size(); i++) // 检查 rank 是否正确
{
if (i != rank(select(i)))
return false;
}
for (Key key : keys()) // 检查 select 是否正确
{
if (key.compareTo(select(rank(key))) != 0)
return false;
}
return true;
} public static void main(String[] args)
{
class01<String, Integer> st = new class01<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) // 放进树中
{
String key = StdIn.readString();
st.put(key, i);
} for (String s : st.levelOrder()) // 迭代器先根序遍历树
StdOut.println(s + " " + st.get(s)); StdOut.println();
for (String s : st.keys()) // 按键遍历树
StdOut.println(s + " " + st.get(s));
}
}
最新文章
- PopupWindowAction breaking MEF import?
- bootstrop框架
- 1、启动oracle的步骤
- 【动态规划】Codeforces 698A & 699C Vacations
- oracle group by rollup,decode,grouping,nvl,nvl2,nullif,grouping_id,group_id,grouping sets,RATIO_TO
- 3 x 8 = 23（火了）
- robot framework用python扩展编写自定义library
- python当中的 可迭代对象 迭代器
- rails中migration数据库后测试不通过的问题
- (86)Wangdao.com第十九天_JavaScript 接口之 ParentNode 和 ChildNode
- postgresql，封装数据库语句时，查询报错。
- SQL SERVER中LIKE使用变量类型不同输出结果不一致解惑
- 实验八 应用层协议Ⅱ-FTP协议分析
- BootStrap学习(6)_模态框
- 【HAOI2014】走出金字塔
- Swift - RotateView
- MT【158】只在此山中，云深不知处
- 20155215 2016-2017-2《Java程序设计》课程总结
- Windows Phone编程回顾
- 【BZOJ】3412: [Usaco2009 Dec]Music Notes乐谱（二分）