6.树（入门与进阶）

//使用层序遍历得到树中所有的键
public Queue<Key> layerErgodic(){
Queue<Key> keys = new Queue<>();
Queue<Node> nodes = new Queue<>();
nodes.enqueue(root);
while(!nodes.isEmpty()){
Node x = nodes.dequeue();
keys.enqueue(x.key);
if (x.left!=null){
nodes.enqueue(x.left);
}
if (x.right!=null){
nodes.enqueue(x.right);
}
}
return keys;
}
//测试代码
public class Test {
public static void main(String[] args) throws Exception {
BinaryTree<String, String> bt = new BinaryTree<>();
bt.put("E", "5");
bt.put("B", "2");
bt.put("G", "7");
bt.put("A", "1");
bt.put("D", "4");
bt.put("F", "6");
bt.put("H", "8");
bt.put("C", "3");
Queue<String> queue = bt.layerErgodic();
for (String key : queue) {
System.out.println(key+"="+bt.get(key));
}
}
}

1.7 二叉树的最大深度问题

public class PaperFolding {
public static void main(String[] args) {
//构建折痕树
Node tree = createTree(3);
//遍历折痕树，并打印
printTree(tree);
}
//3.使用中序遍历，打印出树中所有结点的内容；
private static void printTree(Node tree) {
if (tree==null){
return;
}
printTree(tree.left);
System.out.print(tree.item+",");
printTree(tree.right);
}
//2.构建深度为N的折痕树；
private static Node createTree(int N) {
Node root = null;
for (int i = 0; i <N ; i++) {
if (i==0){
//1.第一次对折，只有一条折痕，创建根结点；
root = new Node("down",null,null);
}else{
//2.如果不是第一次对折，则使用队列保存根结点；
Queue<Node> queue = new Queue<>();
queue.enqueue(root);
//3.循环遍历队列：
while(!queue.isEmpty()){
//3.1从队列中拿出一个结点；
Node tmp = queue.dequeue();
//3.2如果这个结点的左子结点不为空，则把这个左子结点添加到队列中；
if (tmp.left!=null){
queue.enqueue(tmp.left);
}
//3.3如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；
if (tmp.right!=null){
queue.enqueue(tmp.right);
}
//3.4判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个
值为down的左子结点，一个值为up的右子结点。
if (tmp.left==null && tmp.right==null){
tmp.left = new Node("down",null,null);
tmp.right = new Node("up",null,null);
}
}
}
}
return root;
}
//1.定义结点类
private static class Node{
//存储结点元素
String item;
//左子结点
Node left;
//右子结点
Node right;
public Node(String item, Node left, Node right) {
this.item = item;
this.left = left;
this.right = right;
}
}
}

进阶

一、平衡树

我们会发现，如果我们要查找1这个元素，查找的效率依旧会很低。效率低的原因在于这个树并不平衡，全部是向左边分支，如果我们有一种方法，能够不受插入数据的影响，让生成的树都像完全二叉树那样那么即使在最坏情况下查找的效率依旧会很好。

1.1 2-3查找树

1.1.1 2-3查找树的定义

一棵2-3查找树要么为空，要么满足满足下面两个要求：

2-结点：

3-结点：

1.1.2 查找

1.1.3 插入

1.1.3.1 向2-结点中插入新键

 1.1.3.2 向一棵只含有一个3-结点的树中插入新键

 1.1.3.3 向一个父结点为2-结点的3-结点中插入新键

1.3.1.4 向一个父结点为3-结点的3-结点中插入新键 

 1.3.1.5 分解根结点

 1.3.4 2-3树的性质

1.3.5 2-3树的实现

1.2 红黑树

1.2.1 红黑树的定义

 1.2.2 红黑树结点API

 代码：

private class Node<Key,Value>{
//存储键
public Key key;
//存储值
private Value value;
//记录左子结点
public Node left;
//记录右子结点
public Node right;
//由其父结点指向它的链接的颜色
public boolean color;
public Node(Key key, Value value, Node left,Node right,boolean color) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}
}

1.2.3 平衡化

1.2.3.2 右旋

当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋

1.2.4 向单个2-结点中插入新键

• 如果新键小于当前结点的键，我们只需要新增一个红色结点即可，新的红黑树和单个3-结点完全等价。

•  如果新键大于当前结点的键，那么新增的红色结点将会产生一条红色的右链接，此时我们需要通过左旋，把 红色右链接变成左链接，插入操作才算完成。形成的新的红黑树依然和3-结点等价，其中含有两个键，一条红色链接。

1.2.5 向底部的2-结点插入新键

1.2.6 颜色反转

 1.2.7 向一棵双键树(即一个3-结点)中插入新键

 1.2.8 根结点的颜色总是黑色

1.2.9 向树底部的3-结点插入新键

1.2.10 红黑树的API设计

 1.2.11 红黑树的实现

//红黑树代码
public class RedBlackTree<Key extends Comparable<Key>, Value> {
//根节点
private Node root;
//记录树中元素的个数
private int N;
//红色链接
private static final boolean RED = true;
//黑色链接
private static final boolean BLACK = false;
/**
* 判断当前节点的父指向链接是否为红色
*
* @param x
* @return
*/
private boolean isRed(Node x) {
//空结点默认是黑色链接
if (x == null) {
return false;
}
//非空结点需要判断结点color属性的值
return x.color == RED;
}
/**
* 左旋转
*
* @param h
* @return
*/
private Node rotateLeft(Node h) {
//找出当前结点h的右子结点
Node hRight = h.right;
//找出右子结点的左子结点
Node lhRight = hRight.left;
//让当前结点h的右子结点的左子结点成为当前结点的右子结点
h.right = lhRight;
//让当前结点h称为右子结点的左子结点
hRight.left = h;
//让当前结点h的color编程右子结点的color
hRight.color = h.color;
//让当前结点h的color变为RED
h.color = RED;
//返回当前结点的右子结点
return hRight;
}
/**
* 右旋
*
* @param h
* @return
*/
private Node rotateRight(Node h) {
//找出当前结点h的左子结点
Node hLeft = h.left;
//找出当前结点h的左子结点的右子结点
Node rHleft = hLeft.right;
//让当前结点h的左子结点的右子结点称为当前结点的左子结点
h.left = rHleft;
//让当前结点称为左子结点的右子结点
hLeft.right = h;
//让当前结点h的color值称为左子结点的color值
hLeft.color = h.color;
//让当前结点h的color变为RED
h.color = RED;
//返回当前结点的左子结点
return hLeft;
}
/**
* 颜色反转,相当于完成拆分4-节点
*
* @param h
*/
private void flipColors(Node h) {
//当前结点的color属性值变为RED；
h.color = RED;
//当前结点的左右子结点的color属性值都变为黑色
h.left.color = BLACK;
h.right.color = BLACK;
}
/**
* 在整个树上完成插入操作
*
* @param key
* @param val
*/
public void put(Key key, Value val) {
//在root整个树上插入key-val
root = put(root, key, val);
//让根结点的颜色变为BLACK
root.color = BLACK;
}
/**
* 在指定树中，完成插入操作,并返回添加元素后新的树
*
* @param h
* @param key
* @param val
*/
private Node put(Node h, Key key, Value val) {
if (h == null) {
//标准的插入操作，和父结点用红链接相连
N++;
return new Node(key, val, null, null, RED);
}
//比较要插入的键和当前结点的键
int cmp = key.compareTo(h.key);
if (cmp < 0) {
//继续寻找左子树插入
h.left = put(h.left, key, val);
} else if (cmp > 0) {
//继续寻找右子树插入
h.right = put(h.right, key, val);
} else {
//已经有相同的结点存在，修改节点的值；
h.value = val;
}
//如果当前结点的右链接是红色，左链接是黑色，需要左旋
if (isRed(h.right) && !isRed(h.left)) {
h=rotateLeft(h);
}
//如果当前结点的左子结点和左子结点的左子结点都是红色链接，则需要右旋
if (isRed(h.left) && isRed(h.left.left)) {
h=rotateRight(h);
}
//如果当前结点的左链接和右链接都是红色，需要颜色变换
if (isRed(h.left) && isRed(h.right)) {
flipColors(h);
}
//返回当前结点
return h;
}
//根据key，从树中找出对应的值
public Value get(Key key) {
return get(root, key);
}
//从指定的树x中，查找key对应的值
public Value get(Node x, Key key) {
//如果当前结点为空，则没有找到,返回null
if (x == null) {
return null;
}
//比较当前结点的键和key
int cmp = key.compareTo(x.key);
if (cmp < 0) {
//如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
return get(x.left, key);
} else if (cmp > 0) {
//如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
return get(x.right, key);
} else {
//如果要查询的key等于当前结点的key，则树中返回当前结点的value。
return x.value;
}
}
//获取树中元素的个数
public int size() {
return N;
}
//结点类
private class Node {
//存储键
public Key key;
//存储值
private Value value;
//记录左子结点
public Node left;
//记录右子结点
public Node right;
//由其父结点指向它的链接的颜色
public boolean color;
public Node(Key key, Value value, Node left, Node right, boolean color) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}
}
}
//测试代码
public class Test {
public static void main(String[] args) throws Exception {
RedBlackTree<Integer, String> bt = new RedBlackTree<>();
bt.put(4, "二哈");
bt.put(1, "张三");
bt.put(3, "李四");
bt.put(5, "王五");
System.out.println(bt.size());
bt.put(1,"老三");
System.out.println(bt.get(1));
System.out.println(bt.size());
}
}

二、B-树

1.1 B树的特性

• 每个结点最多有M-1个key，并且以升序排列；
• 每个结点最多能有M个子结点；
• 根结点至少有两个子结点；

2.2 B树存储数据

2.3 B树在磁盘文件中的应用

2.3.1 磁盘

2.3.2 磁盘IO

 执行 select * from user where id=18 ,需要从第一条数据开始，一直查询到第6条，发现id=18，此时才能查询出目标结果，共需要比较6次；

3.3.3 区间查询