再学 HashMap的红黑树

2021-06-12 本文已影响0人卫渐行

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.3 ：叔叔节点不存在（或黑节点），并且插入节点的父亲节点，是祖父节点的右子树；
- 情景4.3.1 ：新插入的节点是父节点的右子树（R双红的情况）
变颜色，将P节点变成黑色节点，PP变红
将PP节点进行左旋
情景4.3.2 ：新插入的节点是父节点的右子树（LR红色的情况）

将P进行右旋
将P设置为当前节点，变成了RR双红的情况
将P变成黑色节点，PP变成红色，将PP节点进行左旋；