再學(xué) HashMap的紅黑樹

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;
    }
}

//時(shí)間復(fù)雜度 o lg(n)
//空間復(fù)雜度 o(n)
注意二叉查找樹的問題喉悴，存在最壞的情況允乐，依賴數(shù)組的情況
AVL數(shù)畴椰，就是平衡樹瓣喊，各左右節(jié)點(diǎn)的高度差不超過1；能做到不偏向一方的情況

2: 紅黑樹的基本定義

五大特性

每個節(jié)點(diǎn)要么是紅色的芽世，要么是黑色的
根節(jié)點(diǎn)是黑色的
每個葉子結(jié)點(diǎn)是NIL節(jié)點(diǎn)挚赊，且顏色為黑色
每個紅色節(jié)點(diǎn)的子節(jié)點(diǎn)一定是黑色的，且不能兩個紅色的節(jié)點(diǎn)直接相連济瓢；
任一節(jié)點(diǎn)到葉子結(jié)點(diǎn)荠割，都包含相同個數(shù)的黑色節(jié)點(diǎn)

常見操作

變色節(jié)點(diǎn)由黑變成紅，或者由紅變成黑
左旋以某個節(jié)點(diǎn)為支點(diǎn)（旋轉(zhuǎn)點(diǎn)）旺矾，其右子節(jié)點(diǎn)變成旋轉(zhuǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)蔑鹦；右子節(jié)點(diǎn)的變成旋轉(zhuǎn)節(jié)點(diǎn)的右子節(jié)點(diǎn)，左子節(jié)點(diǎn)保持不變
右旋以某個節(jié)點(diǎn)為支點(diǎn)（旋轉(zhuǎn)點(diǎn)）箕宙，其左子節(jié)點(diǎn)變成旋轉(zhuǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)嚎朽，左子節(jié)點(diǎn)的右子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的左子節(jié)點(diǎn)，右子節(jié)點(diǎn)保持不變

左旋

src=http___store.codemouse.online_pic_488618b8f9442efe97b25969b29262ac.gif&refer=http___store.codemouse.gif

圖片來源于網(wǎng)絡(luò)

右旋

src=http___images.cnitblog.com_blog_94031_201403_270025038901226.gif&refer=http___images.cnitblog.gif

圖片來源于網(wǎng)絡(luò)

紅黑樹的查找

類似于二分查找樹

紅黑樹的插入

插入節(jié)點(diǎn)必須是紅色柬帕，插入的情況可能會影響到樹的結(jié)構(gòu)哟忍；插入的情況一般分為一下的集中情況

情景1：紅黑樹為空樹
直接插入狡门，將紅色節(jié)點(diǎn)更新為黑色
情景2 ：插入的值為存在的值
更新當(dāng)前節(jié)點(diǎn)的值，為插入節(jié)點(diǎn)的值
情景3 ：插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色的
因?yàn)椴迦牍?jié)點(diǎn)是紅色锅很，當(dāng)插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的其馏，未破壞樹的平衡性
情景4 ：插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，一定會破壞樹的平衡性爆安，需要對樹進(jìn)行調(diào)整叛复，分為多種情況（說明PP 為爺爺節(jié)點(diǎn)，P為父節(jié)點(diǎn)扔仓，U為叔叔節(jié)點(diǎn)）
- 情景4.1 ：叔叔節(jié)點(diǎn)存在褐奥，并且為紅節(jié)點(diǎn)
  該種情況，爺爺節(jié)點(diǎn)一定是黑色的当辐，此時(shí)的節(jié)點(diǎn)關(guān)系變成了黑紅紅抖僵，則需要進(jìn)行相應(yīng)的變化鲤看；
  
  將P和U節(jié)點(diǎn)改成黑色
  將PP節(jié)點(diǎn)改成紅色
  將PP節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)缘揪，進(jìn)行下一步操作
- 情景4.2 ：叔叔節(jié)點(diǎn)不存在（或黑節(jié)點(diǎn)），并且插入節(jié)點(diǎn)的父親節(jié)點(diǎn)义桂，是祖父節(jié)點(diǎn)的左子樹找筝；
  - 情景4.2.1 ：新插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹（LL雙紅的情況）
  變顏色，將P節(jié)點(diǎn)變成黑色節(jié)點(diǎn)慷吊，PP變紅
  將PP節(jié)點(diǎn)進(jìn)行右旋
- 情景4.2.2 ：新插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的右子樹（RL紅色的情況）
  
  對P進(jìn)行左旋
  將P設(shè)置為當(dāng)前節(jié)點(diǎn)
  按照LL雙紅的情況袖裕，對節(jié)點(diǎn)節(jié)點(diǎn)進(jìn)行修正（先將P節(jié)點(diǎn)變成黑色，然后進(jìn)行右旋）
情景4.3 ：叔叔節(jié)點(diǎn)不存在（或黑節(jié)點(diǎn)）溉瓶，并且插入節(jié)點(diǎn)的父親節(jié)點(diǎn)急鳄，是祖父節(jié)點(diǎn)的右子樹；
- 情景4.3.1 ：新插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的右子樹（R雙紅的情況）
變顏色堰酿，將P節(jié)點(diǎn)變成黑色節(jié)點(diǎn)疾宏，PP變紅
將PP節(jié)點(diǎn)進(jìn)行左旋
情景4.3.2 ：新插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的右子樹（LR紅色的情況）

將P進(jìn)行右旋
將P設(shè)置為當(dāng)前節(jié)點(diǎn)，變成了RR雙紅的情況
將P變成黑色節(jié)點(diǎn)触创，PP變成紅色坎藐，將PP節(jié)點(diǎn)進(jìn)行左旋；

案例分析（todo List）

備注：學(xué)習(xí)資料來源于B站