映射表map(平衡二叉樹實作)_手動實作Java集合容器之TreeMap(上)

上一篇我們手寫了HashMap，還有一個很重要的Map的實作類TreeMap。打開源碼第一句話：* A Red-Black tree based {

@link

NavigableMap} implementation.TreeMap是一個基于紅黑樹的實作。對紅黑樹沒有了解怎麼辦，那就先搞清楚紅黑樹的原理。隻要了解紅黑樹的玩法，TreeMap實作起來就沒有那麼大的難度了。

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹。是以我們先搞明白什麼是二叉查找樹和完美平衡二叉樹。

二叉排序樹（Binary Sort Tree）是具有下列性質的二叉樹：

1. 元素以關鍵字為依據，每個結點可比較大小，各元素關鍵字互不相同。
2. 對于每個結點，其左子樹上所有結點均小于該結點，右子樹上是以結點均大于該結點。
3. 每個結點的左右子樹也分别為二叉排序樹。

• 查找：從根結點開始查找，根據每一次比較結果，在目前結點的左子樹與右子樹選擇其一，進而縮小一半的查找範圍。如果到達葉子結點仍然不相等，則查找不成功。
• 插入：首先使用查找算法确定元素的插入位置。如果查找成功，說明相同元素已經存在，則不插入；否則在查找不成功的一條路徑之尾插入結點，作為葉子結點。
• 删除：a. 葉結點直接删除 b. 如果被删除的結點有一個子結點，将子結點移到被删除的元素的位置。c. 采用中序周遊（左-根-右），找到待删除的結點的後繼結點，将其與待删除的結點互換，然後删除待删除的結點。假如我們要删除29，中序周遊結果為10-11-13-20-27-29-31-32-39-41-53-50-65-72-91，是以29的後繼結點是31,然後互換位置,删除29。
• 二叉查找樹的查詢複雜度，和二分查找一樣，插入和查找的時間複雜度均為 O(logn) ，但是在最壞的情況下仍然會有 O(n) 的時間複雜度。原因在于插入和删除元素的時候，樹沒有保持平衡。

為了降低二叉排序樹的高度，提高查找效率。平衡二叉樹（又稱為AVL樹）。平衡二叉樹（Balanced Binary Tree）是具有下列性質的二叉排序樹：

1. 左子樹和右子樹都是平衡二叉樹
2. 左子樹與右子樹高度差絕對值不超過一。結點的平衡因子定義為其左子樹與右子樹的高度之差。
3. 在平衡二叉樹中，插入或删除一個結點可能破壞二叉樹的平衡性，是以在插入或删除時都要調整二叉樹。

插入：如果插入一個結點後破壞了二叉樹的平衡性，需要調整一棵最小不平衡子樹。最小不平衡子樹是離插入結點最近，且以平衡因子絕對值大于1的結點為根的子樹。若出現不平衡，則要根據新插入的結點與最低不平衡結點的位置關系進行相應的調整。分為LL,RR,LR,RL四種類型。以下隻介紹了最簡單的情況。

LL型

：在最低不平衡結點的左孩子的左子樹上插入結點。插入C後，A的平衡因子由1增加到2 。結點B變成新的根結點。A變成右孩子結點，C變成左孩子結點。

RR型

：在最低不平衡結點的右孩子的右子樹上插入結點。結點B變成新的根結點。C變成右孩子結點，A變成左孩子結點。

LR型

：在最低不平衡結點的左孩子的右子樹上插入結點。結點C變成新的根結點。A變成右孩子結點，B變成左孩子結點。

RL型

：在最低不平衡結點的右孩子的左子樹上插入結點。結點C變成新的根結點。B變成右孩子結點，A變成左孩子結點。

平衡二叉樹似乎完美解決了二叉排序樹的問題，通過旋轉使樹的高度最小化，對于有 n 個節點的平衡樹，最壞的查找時間複雜度也為 O(logn)。

那麼我們為什麼還需要紅黑樹？

因為我們不僅僅需要關心查找的效率，還要考慮插入的效率。因為平衡二叉樹要求每個節點的左子樹和右子樹的高度差至多等于1，這個要求非常嚴格，每次進行插入/删除資料的時候，幾乎都會破壞這個規則。在插入/删除資料很頻繁的場景中，平衡二叉樹的性能就會受到很嚴重的影響。是以我們需要紅黑樹。

紅黑樹的定義

1. 每個節點或者是黑色，或者是紅色。
2. 根節點是黑色。
3. 每個葉子節點是黑色。
4. 如果一個節點是紅色的，則它的子節點必須是黑色的
5. 從任意一個節點到葉子節點，經過的黑色節點是一樣的。

• 查找：紅黑樹的查找和二叉排序樹一樣，不再贅述
• 添加：

這是一個把資料結構可視化的網站，我們用網站進行一些插入資料的試驗

Red/Black Tree Visualization​www.cs.usfca.edu

添加根結點時，結點為黑色

添加一個子結點，插入結點為紅色，滿足紅黑樹的定義，無需變化

在添加一個孩子，如果添加的數比根結點小，很簡單

如果添加的數比根結點的右結點還要大，左旋，15變成根結點，并且改變顔色

如果繼續插入一個數，因為不滿足性質4，是以10和20的顔色變黑，30變紅

繼續在右子樹上添加35，左旋

繼續插入25，此時不需要旋轉，隻需要改變結點顔色，滿足性質四

是以我們發現每一次插入資料之後，如果不滿足紅黑樹的定義，就需要對紅黑樹的結構進行調整。兩種方式：旋轉和重新上色。是以我們在Java源碼中找到了添加資料的方法，并分析這個方法。

/**
           

假如我們要往這個紅黑數裡面添加6

沒有調整過的樹是這樣的

第一步，8和6兩個同為紅色結點，是以改變顔色，8和14變黑，10變紅。對應源碼中的情況1，當插入結點的叔叔結點為紅，把父結點變黑，叔叔結點也變黑，再把爺爺結點變紅

如果插入結點的爺爺結點是右孩子結點，我們找到爺爺結點的父結點，然後在這個結點上左旋，對應源碼中的情況2

下一步，右旋，10變黑，20變紅，對應源碼中的情況3

從源碼中看出，情況2是情況3的一種擴充。情況4、5、6是1、2、3的鏡像，就不展開了。

删除也需要調整樹的結構，但是更複雜一些，我們看一下源碼中的方法。

/**
           

删除一共8種情況，1-4和5-8也是鏡像的，就不舉具體的例子了。TreeMap果然要比HashMap還要複雜的多，就算讀懂了 rebalance的方法，真正實作起來還是有很大的難度。以此為基礎，下一篇我們嘗試一下手寫HashMap。