▶ 书中第三章部分程序,加上自己补充的代码,平衡二叉搜索树
● 平衡二叉搜索树
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));
}
}
《算法》第三章部分程序 part 2的更多相关文章
-
《算法》第三章部分程序 part 6
▶ 书中第三章部分程序,加上自己补充的代码,包含双向索引表.文建索引.稀疏向量类型 ● 双向索引表 package package01; import edu.princeton.cs.algs4.S ...
-
《算法》第三章部分程序 part 5
▶ 书中第三章部分程序,加上自己补充的代码,包含公共符号表.集合类型 ● 公共符号表,用于普通查找表的基本类 package package01; import java.util.NoSuchEle ...
-
《算法》第三章部分程序 part 4
▶ 书中第三章部分程序,加上自己补充的代码,包括散列表.线性探查表 ● 散列表 package package01; import edu.princeton.cs.algs4.Queue; impo ...
-
《算法》第三章部分程序 part 3
▶ 书中第三章部分程序,加上自己补充的代码,红黑树 ● 红黑树,大部分方法与注释与二叉树相同 package package01; import java.util.NoSuchElementExce ...
-
《算法》第三章部分程序 part 1
▶ 书中第三章部分程序,加上自己补充的代码,包括单词频率统计,(单链表)顺序查找表,二分查找表 ● 单词频率统计 package package01; import edu.princeton.cs. ...
-
《算法》第二章部分程序 part 3
▶ 书中第二章部分程序,加上自己补充的代码,包括各种优化的快排 package package01; import edu.princeton.cs.algs4.In; import edu.prin ...
-
《算法》第一章部分程序 part 1
▶ 书中第一章部分程序,加上自己补充的代码,包括若干种二分搜索,寻找图上连通分量数的两种算法 ● 代码,二分搜索 package package01; import java.util.Arrays; ...
-
《算法》第二章部分程序 part 5
▶ 书中第二章部分程序,加上自己补充的代码,包括利用优先队列进行多路归并和堆排序 ● 利用优先队列进行多路归并 package package01; import edu.princeton.cs.a ...
-
《算法》第二章部分程序 part 4
▶ 书中第二章部分程序,加上自己补充的代码,包括优先队列和索引优先队列 ● 优先队列 package package01; import java.util.Comparator; import ja ...
随机推荐
-
(转)The Neural Network Zoo
转自:http://www.asimovinstitute.org/neural-network-zoo/ THE NEURAL NETWORK ZOO POSTED ON SEPTEMBER 14, ...
-
AspectJ对AOP的实现
一:你应该明白的知识 1.对于AOP这种编程思想,很多框架都进行了实现.Spring就是其中之一,可以完成面向切面编程.然而,AspectJ也实现了AOP的功能,且实现方式更为简捷,使用更加方便,而且 ...
-
深入了解android平台的jni---图像灰度化处理
一.涉及到的jni编程知识 Java基本类型的数组,在JNI中都是jArray的类型格式.具体类型如下: typedef jarray jbooleanArray; typedef jarray jb ...
-
SpringMVC框架三:参数绑定
这篇文章整合了SpringMVC和MyBatis: https://www.cnblogs.com/xuyiqing/p/9419144.html 接下来看看参数绑定: 默认Conrtroller可以 ...
-
JsonPath 使用
Map<String, String> map ----> $.store.bicycleString str = $.store.otherList<Map<Str ...
-
Java 复习
基础: JAVA基础扎实,理解io.多线程.集合等基础框架,对JVM原理有一定的了解: 熟读Java SDK源码: 框架: 对Spring,ibatis,struts等开源框架熟悉:
-
Tensorflow 之finetune微调模型方法&;&;不同层上设置不同的学习率
在不同层上设置不同的学习率,fine-tuning https://github.com/dgurkaynak/tensorflow-cnn-finetune ConvNets: AlexNet VG ...
-
linux常用命令:free 命令
free命令可以显示Linux系统中空闲的.已用的物理内存及swap内存,及被内核使用的buffer.在Linux系统监控的工具中,free命令是最经常使用的命令之一. 1.命令格式: free [参 ...
-
servlet基础(组成与生命周期)
servlet基础作用:servlet是运行在Web服务器或应用服务器上的程序:担当web浏览器或其他HTTP客户程序发出的请求与HTTP服务器上的数据库或应用程序之间的中间层.1.读取客户程序发送的 ...
-
ios 读取各种类型文件
1.如何读取UTF-8编码的文本文件? 2.如何读取GB2312(中文)的文本文件? 3.如何读取其它编码文件? 首先解决第一个问题, 1.如何读取UTF-8编码的文本文件? NSString *fi ...