1: 手写二分查找树
// 二叉查找树；
public class HelloWorld {
public static void main(String[] args) {
int[] x = new int[]{1,2,3,4,5,6,7,8,9,10,14,17,19};
System.out.println(binarySearch(x,19));
}
public static int binarySearch(int[] arr,int num){
int low = 0;
int hight = arr.length - 1;
while (low <= hight){
int mid = low + (hight - low)/2;
if (arr[mid] > num){
hight = mid-1;
} else if (arr[mid] < num) {
low = mid +1 ;
}else{
return mid;
}
}
return -1;
}
}
//时间复杂度 o lg(n)
//空间复杂度 o(n)
注意二叉查找树的问题，存在最坏的情况，依赖数组的情况
AVL数，就是平衡树，各左右节点的高度差不超过1；能做到不偏向一方的情况
2: 红黑树的基本定义
五大特性
- 每个节点要么是红色的，要么是黑色的
- 根节点是黑色的
- 每个叶子结点是NIL节点，且颜色为黑色
- 每个红色节点的子节点一定是黑色的，且不能两个红色的节点直接相连；
- 任一节点到叶子结点，都包含相同个数的黑色节点
常见操作
- 变色 节点由黑变成红，或者由红变成黑
- 左旋 以某个节点为支点（旋转点），其右子节点变成旋转节点的父节点；右子节点的变成旋转节点的右子节点，左子节点保持不变
- 右旋 以某个节点为支点（旋转点），其左子节点变成旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变
左旋
src=http___store.codemouse.online_pic_488618b8f9442efe97b25969b29262ac.gif&refer=http___store.codemouse.gif
图片来源于网络
右旋
src=http___images.cnitblog.com_blog_94031_201403_270025038901226.gif&refer=http___images.cnitblog.gif
图片来源于网络
红黑树的查找
类似于二分查找树
红黑树的插入
插入节点必须是红色，插入的情况可能会影响到树的结构；插入的情况一般分为一下的集中情况
-
情景1： 红黑树为空树
直接插入，将红色节点更新为黑色 -
情景2 ： 插入的值为存在的值
更新当前节点的值，为插入节点的值 -
情景3 ： 插入节点的父节点为黑色的
因为插入节点是红色，当插入节点的父节点是黑色的，未破坏树的平衡性 -
情景4 ：插入节点的父节点是红色的，一定会破坏树的平衡性，需要对树进行调整，分为多种情况（说明PP 为爷爷节点，P为父节点，U为叔叔节点）
-
情景4.1 ：叔叔节点存在，并且为红节点
该种情况，爷爷节点一定是黑色的，此时的节点关系变成了黑红红，则需要进行相应的变化；将P和U节点改成黑色
将PP节点改成红色
将PP节点设置为当前节点，进行下一步操作 -
情景4.2 ：叔叔节点不存在（或黑节点），并且插入节点的父亲节点，是祖父节点的左子树；
- 情景4.2.1 ：新插入的节点是父节点的左子树（LL双红的情况）
变颜色，将P节点变成黑色节点，PP变红
将PP节点进行右旋 -
情景4.2.2 ：新插入的节点是父节点的右子树（RL红色的情况）
对P进行左旋
将P设置为当前节点
按照LL双红的情况，对节点节点进行修正（先将P节点变成黑色，然后进行右旋）
-
情景4.1 ：叔叔节点存在，并且为红节点
-
情景4.3 ：叔叔节点不存在（或黑节点），并且插入节点的父亲节点，是祖父节点的右子树；
- 情景4.3.1 ：新插入的节点是父节点的右子树（R双红的情况）
变颜色，将P节点变成黑色节点，PP变红
将PP节点进行左旋 -
情景4.3.2 ：新插入的节点是父节点的右子树（LR红色的情况）
将P进行右旋
将P设置为当前节点，变成了RR双红的情况
将P变成黑色节点，PP变成红色，将PP节点进行左旋；
案例分析（todo List）
备注： 学习资料来源于B站
网友评论