查找-树
2020-04-09 本文已影响0人
格林哈
1. 树的基本概念
- 度： 结点拥有的子树数称为结点的度
-
节点分类：
- 叶结点（终端结点） 度为0的结点
- 非终端结点（分支结点） 度不为0
- 根节点
- 内部节点
2. 二叉树
- 定义： 每个结点最多有两棵子树，左子树和右子树是有顺序的。
2.1 特殊二叉树
- 斜树
- 所有的结点都只有左子树的二叉树叫左斜树
- 所有结点都是只有右子树的二叉树叫右斜树
-
斜树
- 满二叉树
- 定义： 在二叉树中，所有节点非空，并且所有叶子都在同一层上
- 完全二叉树
- 定义： 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置相同，则这棵二叉树称为完全二叉树
2.2 二叉树性质
- 在二叉树的第n层上至多有 2^(i-1)个结点（n≥1）
- 深度为k的二叉树至多有2^k-1个结点
- 对任何一棵二叉树T，如果其叶子结点数为n0 ，度为2的结点数为n2 ，则n0 =n2 + 1
- 具有n个结点的完全二叉树的深度为 |log2(n+1)|（|x|表示不大于x的最大整数）
- 如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：
- 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
- 如果2*i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
- 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
2.3 二叉树遍历原理
- 前序遍历
- 树为空返回空， 非空，根结点,左子树，右子树
- 中序遍历
- 树为空返回空， 非空，左子树,根结点，右子树
- 后序遍历
- 树为空返回空， 非空，左子树,右子树，根结点
- 层序遍历
- 树为空返回空， 非空，从树的第一层，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
3. 二叉排序树/二叉查找树
-
定义：
- 左子树不空，则左子树上所有结点的值都小于跟节点值
- 右子树不空，则右子树上所有节点的值都大于跟节点值
- 左、右子树也分别为二叉排序树
-
插入
- 根据二叉树定义，找到对应节点，插入到适合位置
-
删除
- 叶子节点
- 直接删除，树结构不受影响
- 仅有左或右子树的结点
- 父节点之间继承删除节点左子树或者右子树
- 左右子树都有的结点
- 找待删除结点的前驱或者后继节点替换位置，然后删除前驱或者后继节点。
- 前驱节点 删除节点左孩子最右一个（肯定没有右孩子 满足第二次情况）。
- 后继节点 删除节点右孩子最左一个（肯定没有左孩子 满足第二次情况）。
- 找待删除结点的前驱或者后继节点替换位置，然后删除前驱或者后继节点。
- 叶子节点
-
代码
package com.datastructure.tree;
/**
* BinaryTree class
*
* @author 格林
* @date 2020/3/25
*/
public class BinarySearchTree<E extends Comparable<E>> {
private Node root;
private int size;
public E remove(E e) {
return remove(root, null, e,true);
}
/**
* 三种情况
* node 是叶子节点
* node 左子树为空 或者 node 右子树为空
* node 左右子树都不为空
* @param node
* @param parent
* @param e
* @param isleft
* @return
*/
private E remove(Node node, Node parent, E e,boolean isleft) {
if(node == null) {
return null;
}
if(e.compareTo(node.e) > 0) {
return remove(node.right,node,e,false);
} else if(e.compareTo(node.e) < 0) {
return remove(node.left,node,e,true);
} else {
E returnE = node.e;
// 假如 左右子树都不为空
if(node.left != null && node.right != null) {
//转左，然后向右到尽头(找待删结点的前驱)
Node s = node.left;
Node q = node;
while (s.right != null) {
q = s;
s = s.right;
}
// s 指向被删除节点
node.e = s.e;
if(q != node) {
q.right = s.left;
// 转左 节点没有右了
} else {
q.left = s.left;
}
// 删除的是跟节点，并且只有一个子树。 我是通过父节点删除，先解决这种可能导致后面出现null的问题情况。
}else if(parent == null ) {
root = root.left != null ? root.left : root.right;
// 删除节点左节点为空
} else if(node.left == null) {
if(isleft) {
parent.left = node.right;
} else {
parent.right = node.right;
}
// 删除节点右节点为空
} else if(node.right == null) {
if(isleft) {
parent.left = node.left;
} else {
parent.right = node.left;
}
}
return returnE;
}
}
public void add( E e) {
add(root,null, e);
}
private void add(Node node,Node parent, E e) {
if(parent == null && root == null) {
root = new Node(e);
size ++;
}else if(node == null) {
if(e.compareTo(parent.e) > 0) {
parent.right = new Node(e);
} else {
parent.left = new Node(e);
}
size ++;
} else if(e.compareTo(node.e) > 0) {
add(node.right, node,e);
} else if(e.compareTo(node.e) < 0) {
add(node.left, node,e);
}
return ;
}
public boolean contains(E e) {
return contains(root,e);
}
private boolean contains(Node node,E e){
if(node == null){
return false;
}
if(e.compareTo(node.e) == 0){
return true;
}else if(e.compareTo(node.e) < 0){
return contains(node.left,e);
}else {
return contains(node.right,e);
}
}
private class Node {
E e;
Node left,right;
public void add(){
}
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
return inTraverse(root,stringBuilder);
}
/**
* 中序遍历
* @param node
* @param stringBuilder
* @return
*/
public String inTraverse(Node node, StringBuilder stringBuilder ){
if(node == null ) {
return null;
}
inTraverse(node.left,stringBuilder);
stringBuilder.append(" " + node.e);
inTraverse(node.right,stringBuilder);
return stringBuilder.toString();
}
}
package com.datastructure.tree;
/**
* Main class
*
* @author 格林
* @date 2020/3/28
*/
public class Main {
public static void main(String[] args) {
int[] nums = new int[]{5,4,2,3,6,12,2131,12321,21};
BinarySearchTree binarySearchTree = new BinarySearchTree();
for(int i : nums) {
binarySearchTree.add(i);
}
System.out.println(binarySearchTree);
binarySearchTree.remove(2);
System.out.println(binarySearchTree);
binarySearchTree.remove(100);
System.out.println(binarySearchTree);
binarySearchTree.remove(12321);
System.out.println(binarySearchTree);
}
}
//控制台输出
2 3 4 5 6 12 21 2131 12321
3 4 5 6 12 21 2131 12321
3 4 5 6 12 21 2131 12321
3 4 5 6 12 21 2131
- 总结
- 二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。
- 对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数
- 最好情况 深度与完全二叉树相同，那么查找的时间复杂也就为O(logn)
- 最坏情况 斜树，查找时间复杂度为O(n)，这等同于顺序查找
4. 平衡二叉树/AVL树
- 定义 是一种二叉排序树，其中每一个节点的左子树和右子树的高度差绝对值不超过1
- 优点 二叉树结构更好，从而提供了查找的速度
- 缺点 插入和删除操作复杂化，降低了插入和删除操作的速度。
- 适合场景 建立就很少进行插入和删除操作，主要用于查询。
5. B树/B-树
-
一个m阶的B树具有如下属性
- 如果根结点不是叶结点，则其至少有两棵子树。
- 每个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]<=k<=m，每个叶子节点都有k-1个元素。
- 所有叶子结点都位于同一层次。
- 所有分支结点，包含n 和n个关键字 n+1个孩子。每个关键字左边孩子小于关键字，关键字右边孩子大于关键字
-
image.png
-
-
场景
- 内外存的数据交互
- 内存与外存交换数据次数频繁，会造成了时间效率上的瓶颈，那么B树结构怎么就可以做到减少次数呢
- 当要处理的外存 如硬盘(是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是211到214个字节。)数据量很大，因此无法一次全部装入内存。我们会对B树进行调整，使得使得B树的阶数（或结点的元素）与硬盘存储的页面大小相匹配
- 比如说一棵B树的阶为1001（即1个结点包含1000个关键字），高度为2，它可以储存超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可
- 当要处理的外存 如硬盘(是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是211到214个字节。)数据量很大，因此无法一次全部装入内存。我们会对B树进行调整，使得使得B树的阶数（或结点的元素）与硬盘存储的页面大小相匹配
- 内存与外存交换数据次数频繁，会造成了时间效率上的瓶颈，那么B树结构怎么就可以做到减少次数呢
- 内外存的数据交互
-
n个关键字的m阶B树，最坏情况是要查找几次
-
image.png
-
-
B树不足
- B树结构，通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行，可是在B树结构中，往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问
-
如
image.png
-
中序遍历所有的元素，页面2→页面1→页面3→页面1→页面4→页面1→页面5
-
如
- B树结构，通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行，可是在B树结构中，往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问
5.1 2-3树（3阶B树）
- 定义
- 其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）
- 一个2结点包含一个元素和两个孩子（或没有孩子），左子树包含的元素小于该元素，右子树包含的元素大于该元素。
- 一个3结点包含一小一大两个元素和三个孩子（或没有孩子），左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
6. B+树
-
一棵m阶的B+树和m阶的B树的差异在于
- 有n棵子树的结点中包含有n个关键字
- 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
- 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字
-
场景
- 文件系统所需而出的一种B树的变形树
- 带有范围的查找
-
效率稳定
- 非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
7. 红黑树
- 定义
- 每个节点或黑色或红色
- 根节点是黑色的
- 每个叶子节点是黑色的
- 如果也一个节点是红色的，则它的两个子节点都是黑色的
- 对于每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数目的黑节点。
- 与平衡二叉树比较
- 查找 查询性能略微逊色于AVL树
- 插入和删除 avl树每次插入删除会进行大量的平衡度计算，平衡二叉树任何不平衡都会在三次旋转之内解决，较于avl树为了维持平衡的开销要小得多。
7.1 左偏红黑树
- 定义
- 对红黑树进行了进一步的限制，一个黑色节点左右儿子
- 要么全是黑色
- 要么左儿子是红色，右儿子是黑色。
- 等价定义
- 红连接均为左链接
- 没有任何一个节点同时和两条红链接相连
- 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数相等
-左偏红黑树 与 2-3树 关系
- 如果一颗红黑树的红链接画平，红链接相连的节点合并，得到的就是一颗2-3 树。
-
将红链接画平，一颗红黑树就是一颗2-3树
- 对红黑树进行了进一步的限制，一个黑色节点左右儿子
- 情况分析与代码
-
颜色修正操
- 左旋
-
左旋H
-
- 右旋
-
右旋H
-
-
颜色转换
- H节点变红，H左右子节点变黑
- 左旋
-
插入 X
- 情况分析
- 插入位置是 2节点
- 小于 新增红色节点
- 大于 产生红色右连接，X父节点 左旋
- 插入位置是 3节点
- 大于原树两个键 新增红色节点 产生两个子节点都是红色，颜色转换
- 小于原树两个键 产生两条连续的红链接 X父节点 右旋，变成第一种情况
- 两个键之间 产生红色右链接，并且父节点也是红色 X父节点 左旋，变成第二种情况
- 总结
- 如果右子节点是红色，左子节点是黑色， 左旋
- 如果左子节点是红色，左子节点的左子节点也是红色， 右旋
- 如果左子节点，右子节点都是红色，颜色转换
- 插入位置是 2节点
- 情况分析
-
删除 X
- 删除最小键
- 情况分析
- 删除位置3节点 直接删除
- 删除2节点 沿左链接向下进行变换，确保当前节点不是2节点（可能是3，临时4节点）
- 跟节点两种情况
- 跟是2节点，且它的两个子节点都是2节点，这个三个节点变成一个4节点
- 保证跟节点左子节点不是2节点 必要的话，可以从右侧兄弟节点借。
- 总结
- 如果当前结点的左子节点不是2节点，完成
- 左子节点是2节点，兄弟不是2节点，将左子节点的兄弟节点中一个键移动到左子节点中
- 左子节点，兄弟都是2节点，将左子节点，父节点中的最小键，左子节点兄弟节点合并为一个4节点，使父节点由3节点变成2节点或者4节点变成3节点
- 情况分析
- 删除最小键
-
代码
-
package com.datastructure.tree.rbtree;
import java.util.LinkedList;
import java.util.Queue;
/**
* RedBlackTree class
*
* @author 格林
* @date 2020/3/31
*/
public class RedBlackTree<Key extends Comparable<Key>, Value> {
public static final boolean RED = true;
public static final boolean BLACK =false;
private Node root;
private class Node{
boolean color;
Key key;
Value value;
/**
* 这颗树的结点总数
*/
int N;
Node left, right;
public Node(boolean color, Key key, Value value, int n) {
this.color = color;
this.key = key;
this.value = value;
N = n;
}
@Override
public String toString() {
return key +" " + (color ? "Red" : "BLACK");
}
}
public boolean isRed(Node node) {
if(node == null) return false;
return node.color == RED;
}
public void moveflipColors(Node node) {
node.color = BLACK;
node.left.color = RED;
node.right.color = RED;
}
private Node balance(Node h){
if (isRed(h.right)) h = rotateLeft(h);
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);
h.N = size(h.left)+size(h.right)+1;
return h;
}
public void deleteMin(){
if(!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMin(root);
if(!isEmpty())
root.color = BLACK;
}
private Node deleteMin(Node node) {
if(node.left == null) {
return null;
}
if(!isRed(node.left) && !isRed(node.right))
node = moveRedLeft(node);
node.left = deleteMin(node.left);
return balance(node);
}
public void deleteMax() {
if(!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMax(root);
if(!isEmpty())
root.color = BLACK;
}
private Node deleteMax(Node h) {
if(isRed(h.left))
h = rotateRight(h);
if(h.right == null)
return null;
if(!isRed(h.right) && !isRed(h.left))
h = moveRedRight(h);
h.right = deleteMax(h.right);
return balance(h);
}
public void levelOrder() {
Queue<Node> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
while (!nodeQueue.isEmpty()) {
Node node = nodeQueue.poll();
System.out.println(node);
if(node.left != null ) {
nodeQueue.add(node.left);
}
if(node.right != null) {
nodeQueue.add(node.right);
}
}
}
/**
*
* \\
* 4.5
* / \
* 3 6
* / \ // \
* 1 4 5 7
*
* |
* 4.5
* // \\
* 3 6
* / \ // \
* 1 4 5 7
*
* |
* 4.5
* // \\
* 3 5
* / \ \\
* 1 4 6
* \
* 7
*
* |
* 5
* // \\
* 4.5 6
* // \
* 3 7
* / \
* 1 4
* @param h
* @return
*/
private Node moveRedLeft(Node h){
/**
* 假设节点h为红色，左右子节点都是黑色
* 将节点h.left 或者 h.left 的子节点之一变红
* 如果该节点的右节点的左节点是红色节点，说明兄弟节点不是2-节点，可以从兄弟节点中借一个
*/
moveflipColors(h); // 从父节点中借一个
if(isRed(h.right.left)){ // 判断兄弟节点，如果是非红节点，也从兄弟节点中借一个
h.right = rotateRight(h.right);
h = rotateLeft(h);
}
return h;
}
private Node moveRedRight(Node h){
/**
* 假设节点h为红色，左右子节点都是黑色
* 将节点h.left 或者 h.left 的子节点之一变红
*/
moveflipColors(h);
if(isRed(h.left.left)){ // 在这里对于兄弟节点的判断都是.left，因为红色节点只会出现在左边
h=rotateRight(h);
// moveflipColors(h);
}
return h;
}
public void delete(Key key){
if(!isRed(root.left)&& !isRed(root.right)){
root.color = RED;
}
root = delete(root,key);
if(root != null)
root.color = BLACK;
}
private Node delete(Node h, Key key){
if(key.compareTo(h.key) < 0){ // 当目标键小于当前键的时候，我们做类似于寻找最小是的操作，向树左边移动，合并父子结点来消除2-结点
if(h.left == null){
return null;
}
if(isRed(h.left) && !isRed(h.left.left)){
h = moveRedLeft(h);
}
h.left = delete(h.left,key);
}else{ // 当目标键大于当前键的时候，我们向右移动，并做与deleteMax相同的操作，如果相同的话，我们使用和二叉树的删除一样的操作，获取当前键的右子树的最小健，然后交换，并将目标键删除
if(isRed(h.left)){
h = rotateRight(h);
}
if(key.compareTo(h.key) == 0 && (h.right == null) ){ // 我们没有找到目标键，我们将其删除
return null;
}
if(!isRed(h.right) && isRed(h.right.left)){
h = moveRedRight(h);
}
if(key.compareTo(h.key) == 0 ){
h.value = get(h.right,min(h.right).key);
h.key = min(h.right).key;
h.right = deleteMin(h.right);
}
else h.right = delete(h.right,key);
}
return balance(h);
}
public Value get(Key key){
return get(root, key);
}
private Value get(Node node, Key key){
if(node == null)
return null;
int cmp = key.compareTo(node.key);
if(cmp < 0)
return get(node.left, key);
else if(cmp > 0)
return get(node.right, key);
else
return node.value;
}
/**
* 查找以node为根节点红黑树的最小节点
* 深度优先遍历，递归实现
*
* @param node
* @return BinarySearchTree<E>.Node
* @author ronglexie
* @version 2018/8/18
*/
private Node min(Node node) {
if(isEmpty()){
throw new IllegalArgumentException("BinarySearchTree is empty !");
}
if(node.left == null){
return node;
}
return min(node.left);
}
private boolean isEmpty() {
return root == null;
}
public void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
/**
* 什么时候左旋 就是node节点是红的。
* 通过左旋node变成左节点，符合红黑树定义
* @param node
* @return
*/
Node rotateLeft(Node node) {
Node t = node.right;
node.right = t.left;
t.left = node;
t.color = node.color;
node.color = RED;
t.N = node.N;
node.N = 1 + size(node.left) +size( node.right);
return t;
}
/**
*
* @param node
*/
// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
/**
* 右旋 就是因为左边有两个连续的红节点
* 通过右旋使得左边红节点x 红色传到右边
* @param node
*/
public Node rotateRight(Node node) {
Node t = node.left;
node.left = t.right;
t.right = node;
t.color = node.color;
node.color = RED;
t.N = node.N;
node.N = 1 + size(node.left) +size( node.right);
return t;
}
public int size() {
return size(root);
}
public int size(Node node) {
if(node == null) return 0;
else return node.N;
}
public void put(Key key, Value value) {
root = put(root, key, value);
root.color = BLACK;
}
public Node put(Node node, Key key, Value value) {
if(node == null)
return new Node(RED,key,value,1);
int cmp = key.compareTo(node.key);
if(cmp < 0)
node.left = put(node.left,key,value);
else if(cmp > 0)
node.right = put(node.right,key,value);
else
node.value = value;
if(isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);
if(isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
if(isRed(node.left) && isRed(node.right)) flipColors(node);
node.N = size(node.left) + 1 + size(node.right);
return node;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
return inTraverse(root,stringBuilder);
}
/**
* 中序遍历
* @param node
* @param stringBuilder
* @return
*/
public String inTraverse(Node node, StringBuilder stringBuilder ){
if(node == null ) {
return null;
}
inTraverse(node.left,stringBuilder);
stringBuilder.append(" " + node.key + " color " + (node.color == true ? "red" : "black") +"|" );
inTraverse(node.right,stringBuilder);
return stringBuilder.toString();
}
}
- 测试
public class Main {
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree<>();
tree.put(2,"qmd");
tree.put(1,"xxp");
tree.put(4,"ddd");
tree.put(3,"ycy");
tree.put(3,"ycyycy");
tree.levelOrder();
System.out.println(tree.toString());
tree.deleteMin();
System.out.println(tree.toString());
tree.deleteMax();
System.out.println(tree.toString());
tree.delete(3);
System.out.println(tree.toString());
}
}
// 输出
2 BLACK
1 BLACK
4 BLACK
3 Red
1 color black| 2 color black| 3 color red| 4 color black|
2 color black| 3 color black| 4 color black|
2 color red| 3 color black|
2 color black|
