1. B树和B+树 性质及区别
1.1 B树（B-树）
m 阶的B树性质：
- 每个结点至多拥有m棵子树；
- 根结点至少拥有两颗子树（存在子树的情况下）；
- 除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；
- 所有的叶结点都在同一层上；
- 有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；
- 关键字个数（查书吧）
1.2 B+树
1.3 红黑树
1.3.1 概念+性质
- 平衡二叉查找树
- 性质：
a. 每个节点要么是黑色，要么是红色。
b. 根节点是黑色。
c. 每个叶节点（NIL）是黑色。
d. 每个红色结点的两个子结点一定都是黑色。
e.任意一结点到每个叶结点的路径都包含数量相同的黑结点。
根据e推论
如果一个结点存在黑子结点，那么该结点肯定有两个子结点
1.3.2 红黑树自平衡
（三种操作：左旋、右旋和变色）
-
左旋
左旋 -
右旋
右旋
- 左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
- 右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
-
变色
结点的颜色由红变黑或由黑变红
1.3.3 红黑树查找
- 类似于平衡二叉树查找
-
查找效率 O(log2n）
二叉树查找流程
1.3.3 红黑树插入
- 查找插入位置
- 插入后自平衡
- 从根结点开始查找；
- 若根结点为空，那么插入结点作为根结点，结束。
- 若根结点不为空，那么把根结点作为当前结点；
- 若当前结点为null，返回当前结点的父结点，结束。
- 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。
- 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；
红黑树插入位置查找- 插入位置结点是红色
红黑树插入情景- 除了情景2，所有插入操作都是在叶子结点进行的
1.3.3 红黑树删除
- 查找删除位置
复用查找插入位置
-
删除后自平衡
三种情况：
- 若删除结点无子结点，直接删除
- 若删除结点只有一个子结点，用子结点替换删除结点
若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点
删除所有情景
2. 排序算法
2.1 冒泡排序 ---O(n^2)
- 算法思想： 两层for循环 一旦发现j比i小 要和i交换数据
public static void Bubble(int[] data){
int len = data.length;
if(len <2)
return ;
for(int i=0; i<len; i++){
for(int j = i+1;j<len; j++){
if(data[j]<data[i]){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
}
2.2 快速排序----O(nlogn)
public static void quickSort(int[] arr, int left, int right){
int len = arr.length;
if(len <2 || left >= right || arr == null)
return ;
int mid = partition(arr, left, right);
quickSort(arr, left, mid-1);
quickSort(arr, mid +1, right);
}
public static int partition(int[] arr, int left, int right){
int tmp = arr[left];
while(left < right){
while(left< right && tmp>= arr[right])
right --;
while(left< right && tmp< arr[left])
left ++;
int data = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
return left;
}
