自己動手實現java資料結構（六）二叉搜尋樹
摘要：
1.二叉搜尋樹介紹
前面我們已經介紹過了向量和連結串列。有序向量可以以二分查詢的方式高效的查詢特定元素，而缺點是插入刪除的效率較低(需要整體移動內部元素)；連結串列的優點在於插入，刪除元素時效率較高，但由於不支援隨機訪問，特定元素的查詢效率為線性複雜度O(1)，效率較低。
向量和連結...
1.二叉搜尋樹介紹
前面我們已經介紹過了向量和連結串列。有序向量可以以二分查詢的方式高效的查詢特定元素，而缺點是插入刪除的效率較低(需要整體移動內部元素)；連結串列的優點在於插入，刪除元素時效率較高，但由於不支援隨機訪問，特定元素的查詢效率為線性複雜度O(1)，效率較低。
向量和連結串列的優缺點是互補的，那麼有沒有辦法兼具兩者的優點呢？這便引出了接下來需要介紹的資料結構—— 二叉搜尋樹 ( B inary S earch T ree)。
二叉搜尋樹和連結串列類似，同樣是以節點為單位儲存資料的鏈式資料結構。二叉搜尋樹作為一種樹形資料結構，內部維護著一個根節點，在插入新資料時，會不斷的和當前子樹的根節點進行key值的大小比較，較小的key值落在左子樹，較大的key值落在右子樹，使得二叉搜尋樹從左到右維持一個有序的狀態。
形式化的定義：
二叉搜尋樹的左子樹上結點的值均小於根結點的值；右子樹上結點的值均大於根結點的值；二叉搜尋樹的左、右子樹也分別為二叉搜尋樹。
由於二叉搜尋樹中的資料是有序儲存的，可以使用高效的二分查詢查詢特定元素；同時由於內部儲存結構為鏈式節點，在插入、刪除元素時的效率和連結串列類似，也十分高效。
可以說， 二叉搜尋樹兼具了向量和連結串列的優點 。
2.二叉搜尋樹ADT介面
二叉搜尋樹同樣是一個儲存key/value型別資料結構，因此和雜湊表實現共用同一個介面（Map）。K/V資料結構需要暴露出內部節點的Key，value給使用者靈活的訪問，但雜湊表和二叉搜尋樹的內部節點實現有一定的差異，所以在Map介面中暴露了Map.EntryNode介面，由雜湊表和二叉搜尋樹的內部節點分別實現Map.EntryNode介面。
public interface Map <K,V>{
/**
* 存入鍵值對
* @param keykey值
* @param value value
* @return 被覆蓋的的value值
*/
V put(K key,V value);
/**
* 移除鍵值對
* @param keykey值
* @return 被刪除的value的值
*/
V remove(K key);
/**
* 獲取key對應的value值
* @param keykey值
* @return對應的value值
*/
V get(K key);
/**
* 是否包含當前key值
* @param keykey值
* @returntrue：包含 false：不包含
*/
boolean containsKey(K key);
/**
* 是否包含當前value值
* @param valuevalue值
* @returntrue：包含 false：不包含
*/
boolean containsValue(V value);
/**
* 獲得當前map儲存的鍵值對數量
* @return 鍵值對數量
* */
int size();
/**
* 當前map是否為空
* @returntrue：為空 false：不為空
*/
boolean isEmpty();
/**
* 清空當前map
*/
void clear();
/**
* 獲得迭代器
* @return 迭代器物件
*/
Iterator<EntryNode<K,V>> iterator();
/**
* entry 鍵值對節點介面
* */
interface EntryNode<K,V>{
/**
* 獲得key值
* */
K getKey();
/**
* 獲得value值
* */
V getValue();
/**
* 設定value值
* */
void setValue(V value);
}
}
3.二叉搜尋樹實現細節
3.1 二叉搜尋樹基本屬性
值得一提的是，二叉搜尋樹通過給儲存的元素進行排序來加快查詢的速度(遍歷查詢 ---> 二分查詢)。
java是面向物件的語言，二叉搜尋樹中的元素不僅僅是整數、小數。如果說對於整數、小數甚至字串的排序，我們確定了一個公認的排序邏輯。但是使用者自定義的物件，例如小貓、小狗物件的排序可就仁者見仁智者見智了。
由於java並不支援比較符號">"，"<"的運算子過載，因此我們提供了一個比較排序的介面，使用者可以在二叉搜尋樹初始化時指定排序時元素間比較的邏輯，使得二叉搜尋樹能以滿足使用者需求的方式執行排序的邏輯。
比較器介面(Comparator)定義：
@FunctionalInterface
public interface Comparator<T> {
/**
* 比較方法邏輯
* @param o1引數1
* @param o2引數2
* @return返回值大於0 ---> (o1 > o2)
*返回值等於0 ---> (o1 = o2)
*返回值小於0 ---> (o1 < o2)
*/
int compare(T o1, T o2);
}
基本屬性:
public class TreeMap<K,V> implements Map<K,V>{
/**
* 根節點
* */
private EntryNode<K,V> root;
/**
* 比較器(初始化之後，不能改)
* */
private final Comparator<? super K> comparator;
/**
* 當前二叉樹的大小
* */
private int size;
/**
* 預設建構函式
* */
public TreeMap() {
this.comparator = null;
}
/**
* 指定了比較器的建構函式
* */
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
｝
3.2 二叉搜尋樹內部節點
二叉搜尋樹的內部節點除了必須的key，value欄位，同時還維護了左、右孩子節點和雙親節點的引用。
通過實現暴露出去的Map.EntryNode介面，允許使用者訪問內部節點的key、value值，但二叉搜尋樹節點內部的孩子、雙親節點的引用是被封裝起來的，外部使用者是無法感知，也無需瞭解的。
/**
* 二叉搜尋樹 內部節點
* */
static class EntryNode<K,V> implements Map.EntryNode<K,V>{
/**
* key值
* */
K key;
/**
* value值
* */
V value;
/**
* 左孩子節點
* */
EntryNode<K,V> left;
/**
* 右孩子節點
* */
EntryNode<K,V> right;
/**
* 雙親節點
* */
EntryNode<K,V> parent;
EntryNode(K key, V value) {
this.key = key;
this.value = value;
}
EntryNode(K key, V value,EntryNode<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public void setValue(V value) {
this.value = value;
}
@Override
public String toString() {
return key + "=" + value;
}
}
3.3 二叉搜尋樹 內部輔助函式
為了簡化程式碼邏輯以及去除重複程式碼，在實現過程中提取出了諸如：獲取第一個節點( getFirst )、獲取節點直接後繼( getSuccessor )、獲得key值對應目標節點( getTargetEntryNode )等等輔助方法。
getTargetEntryNode用於獲取key值對應的目標節點，運用了哨兵的思想。從根節點開始，使用二分查詢的方式逐步逼近key值對應目標節點的位置。
如果目標節點確實存在，自然直接返回目標節點的引用(相對位置： RelativePosition.CURRENT )；
當目標節點不存在時，則 假設目標節點已經存在 (哨兵節點)，返回哨兵節點的雙親節點引用以及哨兵節點的相對位置(左、右節點： RelativePosition.LEFT 、 RelativePosition.Right )。
/**
* target 和目標節點的相對位置
* */
private enum RelativePosition {
/**
* 左節點
* */
LEFT,
/**
* 右節點
* */
RIGHT,
/**
* 當前節點
* */
CURRENT;
}
/**
* 查詢目標節點 返回值
* */
private static class TargetEntryNode<K,V>{
/**
* 目標節點
* */
private EntryNode<K,V> target;
/**
* 目標節點的雙親節點
* */
private EntryNode<K,V> parent;
/**
* 相對位置
* */
private RelativePosition relativePosition;
TargetEntryNode(EntryNode<K, V> target, EntryNode<K, V> parent, RelativePosition relativePosition) {
this.target = target;
this.parent = parent;
this.relativePosition = relativePosition;
}
}
/**
* 獲得key對應的目標節點
* @param key對應的key
* @return對應的目標節點
*返回null代表 目標節點不存在
* */
private TargetEntryNode<K,V> getTargetEntryNode(K key){
int compareResult = 0;
EntryNode<K,V> parent = null;
EntryNode<K,V> currentNode = this.root;
while(currentNode != null){
parent = currentNode;
//:::當前key 和 currentNode.key進行比較
compareResult = compare(key,currentNode.key);
if(compareResult > 0){
//:::當前key 大於currentNode 指向右邊節點
currentNode = currentNode.right;
}else if(compareResult < 0){
//:::當前key 小於currentNode 指向右邊節點
currentNode = currentNode.left;
}else{
return new TargetEntryNode<>(currentNode, parent, RelativePosition.CURRENT);
}
}
//:::沒有找到目標節點
if(compareResult > 0){
//:::返回 右孩子 哨兵節點
return new TargetEntryNode<>(null, parent, RelativePosition.RIGHT);
}else if(compareResult < 0){
//:::返回 左孩子 哨兵節點
return new TargetEntryNode<>(null, parent, RelativePosition.LEFT);
}else{
throw new RuntimeException("狀態異常");
}
}
/**
* key值進行比較
* */
@SuppressWarnings("unchecked")
private int compare(K k1,K k2){
//:::迭代器不存在
if(this.comparator == null){
//:::依賴物件本身的 Comparable，可能會轉型失敗
return ((Comparable) k1).compareTo(k2);
}else{
//:::通過迭代器邏輯進行比較
return this.comparator.compare(k1,k2);
}
}
/**
* 判斷雙親節點和目標節點 相對位置
* @param parent雙親節點
* @param target目標節點
* @return相對位置(左孩子/右孩子)
*/
private RelativePosition getRelativeByParent(EntryNode<K,V> parent,EntryNode<K,V> target){
if(parent.left == target){
return RelativePosition.LEFT;
}else if(parent.right == target){
return RelativePosition.RIGHT;
}else{
throw new RuntimeException("不是父子節點關係");
}
}
/**
* 獲得當前節點的直接後繼
* @param targetEntryNode當前節點
* @return當前節點的直接後繼
*/
private EntryNode<K,V> getSuccessor(EntryNode<K,V> targetEntryNode){
if(targetEntryNode == null){
//:::當前節點為null，則後繼也為null
return null;
}
//:::判斷當前節點是否存在右孩子
if(targetEntryNode.right != null){
//:::存在右孩子，右子樹的最左節點為直接後繼
EntryNode<K,V> rightChildSuccessor = targetEntryNode.right;
//:::迴圈往復，直至直接右孩子的最左節點
while(rightChildSuccessor.left != null){
rightChildSuccessor = rightChildSuccessor.left;
}
return rightChildSuccessor;
}else{
//:::不存在右孩子，尋找第一個靠右的雙親節點
EntryNode<K,V> parent = targetEntryNode.parent;
EntryNode<K,V> child = targetEntryNode;
//:::判斷當前孩子節點是否是雙親節點的左孩子
while(parent != null && parent.right == child){
//:::不是左孩子，而是右孩子，繼續向上尋找
child = parent;
parent = parent.parent;
}
return parent;
}
}
/**
* 獲得二叉搜尋樹的第一個節點
* */
private EntryNode<K,V> getFirstNode(){
if(this.root == null){
//:::空樹，返回null
return null;
}
EntryNode<K,V> entryNode = this.root;
//:::迴圈往復，尋找整棵樹的最左節點(最小節點、第一個節點)
while(entryNode.left != null){
entryNode = entryNode.left;
}
return entryNode;
}
3.4 二叉搜尋樹插入介面實現
二叉搜尋樹的插入介面複用了前面提到的 getTargetEntryNode 方法，以二分查詢的方式進行查詢。
當key值對應的目標節點存在時，替換掉之前的value。
當key值對應的目標節點不存在時，運用哨兵的思想，通過雙親節點和哨兵節點的相對位置，在目標位置插入一個新的節點。
@Override
public V put(K key, V value) {
if(this.root == null){
this.root = new EntryNode<>(key,value);
this.size++;
return null;
}
//:::獲得目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition == RelativePosition.CURRENT){
//:::目標節點存在於當前容器
//:::暫存之前的value
V oldValue = targetEntryNode.target.value;
//:::替換為新的value
targetEntryNode.target.value = value;
//:::返回之前的value
return oldValue;
}else{
//:::目標節點不存在於當前容器
EntryNode<K,V> parent = targetEntryNode.parent;
if(targetEntryNode.relativePosition == RelativePosition.LEFT){
//:::目標節點位於左邊
parent.left = new EntryNode<>(key,value,parent);
}else{
//:::目標節點位於右邊
parent.right = new EntryNode<>(key,value,parent);
}
this.size++;
return null;
}
}
3.5 二叉搜尋樹刪除介面實現
二叉搜尋樹節點在被刪除時，被刪除節點存在三種情況：
1. 不存在任何孩子節點 (既沒有左孩子，也沒有右孩子)
直接將雙親節點和當前節點的連線切斷(雙親對應孩子節點引用置為null)。
2. 只存在一個孩子節點 (只存在左孩子或者只存在右孩子)
被刪除節點唯一的孩子節點代替被刪除節點本身，唯一的孩子節點和雙親節點直接相連。
3.既有左孩子節點，又有右孩子節點
找到被刪除節點的直接後繼節點(直接前驅節點也行，本質上是保證刪除之後依然保證有序性)，將被刪除節點和其直接後繼交換位置。
當右孩子節點存在時，直接後繼節點必定存在於右子樹中，並且其直接後繼一定不存在左孩子節點(否則就不是直接後繼節點了)，因此被刪除節點的直接後繼節點至多隻存在一個右孩子節點(或沒有任何孩子節點)。在兩者交換位置後，可以轉換為第一或第二種情況進行處理。
節點刪除前：
1.無孩子節點的刪除：
2. 只有一個孩子節點的刪除：
3. 擁有兩個孩子的節點的刪除：
二叉搜尋樹節點刪除程式碼實現：
@Override
public V remove(K key) {
if(this.root == null){
return null;
}
//:::查詢目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition != RelativePosition.CURRENT){
//:::沒有找到目標節點
return null;
}else{
//:::找到了目標節點
//:::從二叉樹中刪除目標節點
deleteEntryNode(targetEntryNode.target);
return targetEntryNode.target.value;
}
}
/**
* 將目標節點從二叉搜尋樹中刪除
* @param target 需要被刪除的節點
* */
private void deleteEntryNode(EntryNode<K,V> target){
/*
* 刪除二叉搜尋樹節點
*1.無左右孩子
*直接刪除
*2.只有左孩子或者右孩子
*將唯一的孩子和parent節點直接相連
*3.既有左孩子，又有右孩子
*找到自己的直接前驅/後繼（左側的最右節點/右側的最左節點）
*將自己和直接後繼進行交換，轉換為第1或第2種情況，並將自己刪除
* */
//:::size自減1
size--;
//:::既有左孩子，又有右孩子
if(target.left != null && target.right != null){
//:::找到直接後繼(右側的最左節點)
EntryNode<K,V> targetSuccessor = getSuccessor(target);
//:::target的key/value和自己的後繼交換
target.key = targetSuccessor.key;
target.value = targetSuccessor.value;
//:::target指向自己的後繼，轉換為第一/第二種情況
target = targetSuccessor;
}
EntryNode<K,V> parent = target.parent;
RelativePosition relativePosition = getRelativeByParent(parent,target);
//:::獲得代替被刪除節點原先位置的節點(從左右孩子中選擇一個)
EntryNode<K,V> replacement = (target.left != null ? target.left : target.right);
if(replacement == null){
//:::無左右孩子
//:::直接刪除,斷開和雙親節點的聯絡
if(relativePosition == RelativePosition.LEFT){
parent.left = null;
}else{
parent.right = null;
}
target.parent = null;
}else{
//:::只有左孩子或者右孩子
replacement.parent = target.parent;
//:::被刪除節點的雙親節點指向被代替的節點
if(relativePosition == RelativePosition.LEFT){
parent.left = replacement;
}else{
parent.right = replacement;
}
}
}
3.6 二叉搜尋樹查詢介面實現
二叉搜尋樹的查詢介面使用了getTargetEntryNode方法。
當返回的相對位置為Current時，代表找到了目標節點，直接返回value；反之代表目標節點不存在，返回null。
@Override
public V get(K key) {
if(this.root == null){
return null;
}
//:::查詢目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition != RelativePosition.CURRENT){
//:::沒有找到目標節點
return null;
}else{
return targetEntryNode.target.value;
}
}
3.7 二叉搜尋樹其它介面實現
@Override
public boolean containsKey(K key) {
return (get(key) != null);
}
@Override
public boolean containsValue(V value) {
//:::尋找到第一個節點
EntryNode<K,V> entryNode = getFirstNode();
//:::從第一個節點開始，遍歷整顆二叉搜尋樹
while(entryNode != null){
if(Objects.equals(entryNode.value,value)){
//:::當前節點value匹配，返回true
return true;
}else{
//:::指向下一個直接後繼節點
entryNode = getSuccessor(entryNode);
}
}
//:::遍歷整顆樹之後，還未匹配，返回false
return false;
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return (this.size == 0);
}
@Override
public void clear() {
this.size = 0;
this.root = null;
}
@Override
public String toString(){
Iterator<Map.EntryNode<K,V>> iterator = this.iterator();
//:::空容器
if(!iterator.hasNext()){
return "[]";
}
//:::容器起始使用"["
StringBuilder s = new StringBuilder("[");
//:::反覆迭代
while(true){
//:::獲得迭代的當前元素
Map.EntryNode<K,V> data = iterator.next();
//:::判斷當前元素是否是最後一個元素
if(!iterator.hasNext()){
//:::是最後一個元素，用"]"收尾
s.append(data).append("]");
//:::返回 拼接完畢的字串
return s.toString();
}else{
//:::不是最後一個元素
//:::使用", "分割，拼接到後面
s.append(data).append(", ");
}
}
}
@Override
public Iterator<Map.EntryNode<K, V>> iterator() {
return new Itr();
}
4.二叉搜尋樹迭代器
1. 二叉搜尋樹從最左節點開始，以中序遍歷的方式遍歷整顆樹
2. 在迭代器初始化時，迭代器指向最小的節點(也就是最左節點)
3. 迭代器迭代時，下一個節點總是指向當前節點的直接後繼
/**
* 二叉搜尋樹 迭代器實現
* */
private class Itr implements Iterator<Map.EntryNode<K,V>>{
/**
* 當前迭代節點
* */
private EntryNode<K,V> currentNode;
/**
* 下一個節點
* */
private EntryNode<K,V> nextNode;
private Itr() {
//:::初始化時，nextNode指向第一個節點
this.nextNode = TreeMap.this.getFirstNode();
}
@Override
public boolean hasNext() {
return (this.nextNode != null);
}
@Override
public Map.EntryNode<K, V> next() {
this.currentNode = this.nextNode;
this.nextNode = TreeMap.this.getSuccessor(this.nextNode);
return this.currentNode;
}
@Override
public void remove() {
if(this.currentNode == null){
throw new IteratorStateErrorException("迭代器狀態異常: 可能在一次迭代中進行了多次remove操作");
}
//:::判斷當前被刪除的節點是否同時存在左右孩子
if(this.currentNode.left != null && this.currentNode.right != null){
/*
同時存在左右孩子的節點刪除時當前節點會和直接後繼(nextNode)進行交換
因此nextNode指向當前節點
*/
this.nextNode = this.currentNode;
}
//:::刪除當前節點
TreeMap.this.deleteEntryNode(this.currentNode);
//:::currentNode設定為null，防止反覆呼叫remove方法
this.currentNode = null;
}
}
5.二叉搜尋樹效能
5.1 空間效率
二叉搜尋樹的內部節點除了key，value的引用，同時還維護著雙親，左右孩子節點的引用(不一定存在)，因此其空間效率比連結串列稍差，更是不如向量結構緊湊。但是這一點點空間效率的損失，帶來的是二叉搜尋樹全面而優異的增刪改查效率。
5.2 時間效率
二叉搜尋樹的插入，刪除依賴於查詢介面，而查詢介面是以二分查詢的方式實現的。在理想狀態下(平衡的)，二叉搜尋樹的增刪改查介面的效率為(O(logN))，N為當前二叉搜尋樹儲存的元素總數；也可以說，二叉搜尋樹增刪改查介面的效率正比於二叉搜尋樹的高度。
6.二叉搜尋樹總結
6.1 當前版本缺陷：
至此，我們實現了一個最基礎的二叉搜尋樹，但還存在一個致命缺陷：
二叉搜尋樹在插入資料時，以二分查詢的方式確定插入的位置。但是當插入資料的資料不夠隨機時，會降低二叉搜尋樹的查詢效率。舉個極端例子，當按照順序插入1到10000的元素以從小到大順序插入，二叉搜尋樹將退化為一個一維的連結串列( 極端不平衡 )，查詢效率從O(logN)急劇降低為O(n)。
我們希望在插入，刪除元素時，通過及時的調整二叉搜尋樹結構，用一系列等價變換的操作，使二叉搜尋樹始終保持一個適度平衡的狀態(即所有的左右子樹的高度差其絕對值不超過1)。我們稱這樣的二叉搜尋樹為平衡二叉搜尋樹( B alanced B inary S earch T ree)，常見的平衡二叉搜尋樹有AVL樹、紅黑樹等。
只有平衡二叉搜尋樹才能始終保證始終高效的查詢效率(O(logN))，而不會因為極端資料集合的插入，造成效率的大幅降低。
6.2 完整程式碼
二叉搜尋樹ADT介面:
1 /**
2* Map ADT介面
3*/
4 public interface Map <K,V>{
5/**
6* 存入鍵值對
7* @param keykey值
8* @param value value
9* @return 被覆蓋的的value值
10*/
11V put(K key,V value);
12
13/**
14* 移除鍵值對
15* @param keykey值
16* @return 被刪除的value的值
17*/
18V remove(K key);
19
20/**
21* 獲取key對應的value值
22* @param keykey值
23* @return對應的value值
24*/
25V get(K key);
26
27/**
28* 是否包含當前key值
29* @param keykey值
30* @returntrue：包含 false：不包含
31*/
32boolean containsKey(K key);
33
34/**
35* 是否包含當前value值
36* @param valuevalue值
37* @returntrue：包含 false：不包含
38*/
39boolean containsValue(V value);
40
41/**
42* 獲得當前map儲存的鍵值對數量
43* @return 鍵值對數量
44* */
45int size();
46
47/**
48* 當前map是否為空
49* @returntrue：為空 false：不為空
50*/
51boolean isEmpty();
52
53/**
54* 清空當前map
55*/
56void clear();
57
58/**
59* 獲得迭代器
60* @return 迭代器物件
61*/
62Iterator<EntryNode<K,V>> iterator();
63
64/**
65* entry 鍵值對節點介面
66* */
67interface EntryNode<K,V>{
68/**
69* 獲得key值
70* */
71K getKey();
72
73/**
74* 獲得value值
75* */
76V getValue();
77
78/**
79* 設定value值
80* */
81void setValue(V value);
82}
83 }
View Code
二叉搜尋樹實現:
/**
* 二叉搜尋樹實現
*/
public class TreeMap<K,V> implements Map<K,V>{
/**
* 根節點
* */
private EntryNode<K,V> root;
/**
* 比較器(初始化之後，不能改)
* */
private final Comparator<? super K> comparator;
/**
* 當前二叉樹的大小
* */
private int size;
/**
* 預設建構函式
* */
public TreeMap() {
this.comparator = null;
}
/**
* 指定了比較器的建構函式
* */
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* target 和目標節點的相對位置
* */
private enum RelativePosition {
/**
* 左節點
* */
LEFT,
/**
* 右節點
* */
RIGHT,
/**
* 當前節點
* */
CURRENT;
}
/**
* 二叉搜尋樹 內部節點
* */
static class EntryNode<K,V> implements Map.EntryNode<K,V>{
/**
* key值
* */
K key;
/**
* value值
* */
V value;
/**
* 左孩子節點
* */
EntryNode<K,V> left;
/**
* 右孩子節點
* */
EntryNode<K,V> right;
/**
* 雙親節點
* */
EntryNode<K,V> parent;
EntryNode(K key, V value) {
this.key = key;
this.value = value;
}
EntryNode(K key, V value,EntryNode<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public void setValue(V value) {
this.value = value;
}
@Override
public String toString() {
return key + "=" + value;
}
}
/**
* 二叉搜尋樹 迭代器實現
* */
private class Itr implements Iterator<Map.EntryNode<K,V>>{
/**
* 當前迭代節點
* */
private EntryNode<K,V> currentNode;
/**
* 下一個節點
* */
private EntryNode<K,V> nextNode;
private Itr() {
//:::初始化時，nextNode指向第一個節點
this.nextNode = TreeMap.this.getFirstNode();
}
@Override
public boolean hasNext() {
return (this.nextNode != null);
}
@Override
public Map.EntryNode<K, V> next() {
this.currentNode = this.nextNode;
this.nextNode = TreeMap.this.getSuccessor(this.nextNode);
return this.currentNode;
}
@Override
public void remove() {
if(this.currentNode == null){
throw new IteratorStateErrorException("迭代器狀態異常: 可能在一次迭代中進行了多次remove操作");
}
//:::判斷當前被刪除的節點是否同時存在左右孩子
if(this.currentNode.left != null && this.currentNode.right != null){
/*
同時存在左右孩子的節點刪除時會和直接後繼(nextNode)進行交換
因此nextNode指向當前節點
*/
this.nextNode = this.currentNode;
}
//:::刪除當前節點
TreeMap.this.deleteEntryNode(this.currentNode);
//:::currentNode設定為null，防止反覆呼叫remove方法
this.currentNode = null;
}
}
/**
* 查詢目標節點 返回值
* */
private static class TargetEntryNode<K,V>{
/**
* 目標節點
* */
private EntryNode<K,V> target;
/**
* 目標節點的雙親節點
* */
private EntryNode<K,V> parent;
/**
* 相對位置
* */
private RelativePosition relativePosition;
TargetEntryNode(EntryNode<K, V> target, EntryNode<K, V> parent, RelativePosition relativePosition) {
this.target = target;
this.parent = parent;
this.relativePosition = relativePosition;
}
}
@Override
public V put(K key, V value) {
if(this.root == null){
this.root = new EntryNode<>(key,value);
this.size++;
return null;
}
//:::獲得目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition == RelativePosition.CURRENT){
//:::目標節點存在於當前容器
//:::暫存之前的value
V oldValue = targetEntryNode.target.value;
//:::替換為新的value
targetEntryNode.target.value = value;
//:::返回之前的value
return oldValue;
}else{
//:::目標節點不存在於當前容器
EntryNode<K,V> parent = targetEntryNode.parent;
if(targetEntryNode.relativePosition == RelativePosition.LEFT){
//:::目標節點位於左邊
parent.left = new EntryNode<>(key,value,parent);
}else{
//:::目標節點位於右邊
parent.right = new EntryNode<>(key,value,parent);
}
this.size++;
return null;
}
}
@Override
public V remove(K key) {
if(this.root == null){
return null;
}
//:::查詢目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition != RelativePosition.CURRENT){
//:::沒有找到目標節點
return null;
}else{
//:::找到了目標節點
//:::從二叉樹中刪除目標節點
deleteEntryNode(targetEntryNode.target);
return targetEntryNode.target.value;
}
}
@Override
public V get(K key) {
if(this.root == null){
return null;
}
//:::查詢目標節點
TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
if(targetEntryNode.relativePosition != RelativePosition.CURRENT){
//:::沒有找到目標節點
return null;
}else{
return targetEntryNode.target.value;
}
}
@Override
public boolean containsKey(K key) {
return (get(key) != null);
}
@Override
public boolean containsValue(V value) {
//:::尋找到第一個節點
EntryNode<K,V> entryNode = getFirstNode();
//:::從第一個節點開始，遍歷整顆二叉搜尋樹
while(entryNode != null){
if(Objects.equals(entryNode.value,value)){
//:::當前節點value匹配，返回true
return true;
}else{
//:::指向下一個直接後繼節點
entryNode = getSuccessor(entryNode);
}
}
//:::遍歷整顆樹之後，還未匹配，返回false
return false;
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return (this.size == 0);
}
@Override
public void clear() {
this.size = 0;
this.root = null;
}
@Override
public Iterator<Map.EntryNode<K, V>> iterator() {
return new Itr();
}
@Override
public String toString(){
Iterator<Map.EntryNode<K,V>> iterator = this.iterator();
//:::空容器
if(!iterator.hasNext()){
return "[]";
}
//:::容器起始使用"["
StringBuilder s = new StringBuilder("[");
//:::反覆迭代
while(true){
//:::獲得迭代的當前元素
Map.EntryNode<K,V> data = iterator.next();
//:::判斷當前元素是否是最後一個元素
if(!iterator.hasNext()){
//:::是最後一個元素，用"]"收尾
s.append(data).append("]");
//:::返回 拼接完畢的字串
return s.toString();
}else{
//:::不是最後一個元素
//:::使用", "分割，拼接到後面
s.append(data).append(", ");
}
}
}
/**
* 獲得key對應的目標節點
* @param key對應的key
* @return對應的目標節點
*返回null代表 目標節點不存在
* */
private TargetEntryNode<K,V> getTargetEntryNode(K key){
int compareResult = 0;
EntryNode<K,V> parent = null;
EntryNode<K,V> currentNode = this.root;
while(currentNode != null){
parent = currentNode;
//:::當前key 和 currentNode.key進行比較
compareResult = compare(key,currentNode.key);
if(compareResult > 0){
//:::當前key 大於currentNode 指向右邊節點
currentNode = currentNode.right;
}else if(compareResult < 0){
//:::當前key 小於currentNode 指向右邊節點
currentNode = currentNode.left;
}else{
return new TargetEntryNode<>(currentNode, parent, RelativePosition.CURRENT);
}
}
//:::沒有找到目標節點
if(compareResult > 0){
//:::返回 右孩子 哨兵節點
return new TargetEntryNode<>(null, parent, RelativePosition.RIGHT);
}else if(compareResult < 0){
//:::返回 左孩子 哨兵節點
return new TargetEntryNode<>(null, parent, RelativePosition.LEFT);
}else{
throw new RuntimeException("狀態異常");
}
}
/**
* key值進行比較
* */
@SuppressWarnings("unchecked")
private int compare(K k1,K k2){
//:::迭代器不存在
if(this.comparator == null){
//:::依賴物件本身的 Comparable，可能會轉型失敗
return ((Comparable) k1).compareTo(k2);
}else{
//:::通過迭代器邏輯進行比較
return this.comparator.compare(k1,k2);
}
}
/**
* 將目標節點從二叉搜尋樹中刪除
* @param target 需要被刪除的節點
* */
private void deleteEntryNode(EntryNode<K,V> target){
/*
* 刪除二叉搜尋樹節點
*1.無左右孩子
*直接刪除
*2.只有左孩子或者右孩子
*將唯一的孩子和parent節點直接相連
*3.既有左孩子，又有右孩子
*找到自己的直接前驅/後繼（左側的最右節點/右側的最左節點）
*將自己和直接後繼進行交換，轉換為第1或第2種情況，並將自己刪除
* */
//:::size自減1
this.size--;
//:::既有左孩子，又有右孩子
if(target.left != null && target.right != null){
//:::找到直接後繼(右側的最左節點)
EntryNode<K,V> targetSuccessor = getSuccessor(target);
//:::target的key/value和自己的後繼交換
target.key = targetSuccessor.key;
target.value = targetSuccessor.value;
//:::target指向自己的後繼，轉換為第一/第二種情況
target = targetSuccessor;
}
EntryNode<K,V> parent = target.parent;
RelativePosition relativePosition = getRelativeByParent(parent,target);
//:::獲得代替被刪除節點原先位置的節點(從左右孩子中選擇一個)
EntryNode<K,V> replacement = (target.left != null ? target.left : target.right);
if(replacement == null){
//:::無左右孩子
//:::直接刪除,斷開和雙親節點的聯絡
if(relativePosition == RelativePosition.LEFT){
parent.left = null;
}else{
parent.right = null;
}
target.parent = null;
}else{
//:::只有左孩子或者右孩子
replacement.parent = target.parent;
//:::被刪除節點的雙親節點指向被代替的節點
if(relativePosition == RelativePosition.LEFT){
parent.left = replacement;
}else{
parent.right = replacement;
}
}
}
/**
* 判斷雙親節點和目標節點 相對位置
* @param parent雙親節點
* @param target目標節點
* @return相對位置(左孩子/右孩子)
*/
private RelativePosition getRelativeByParent(EntryNode<K,V> parent,EntryNode<K,V> target){
if(parent.left == target){
return RelativePosition.LEFT;
}else if(parent.right == target){
return RelativePosition.RIGHT;
}else{
throw new RuntimeException("不是父子節點關係");
}
}
/**
* 獲得當前節點的直接後繼
* @param targetEntryNode當前節點
* @return當前節點的直接後繼
*/
private EntryNode<K,V> getSuccessor(EntryNode<K,V> targetEntryNode){
if(targetEntryNode == null){
//:::當前節點為null，則後繼也為null
return null;
}
//:::判斷當前節點是否存在右孩子
if(targetEntryNode.right != null){
//:::存在右孩子，右子樹的最左節點為直接後繼
EntryNode<K,V> rightChildSuccessor = targetEntryNode.right;
//:::迴圈往復，直至直接右孩子的最左節點
while(rightChildSuccessor.left != null){
rightChildSuccessor = rightChildSuccessor.left;
}
return rightChildSuccessor;
}else{
//:::不存在右孩子，尋找第一個靠右的雙親節點
EntryNode<K,V> parent = targetEntryNode.parent;
EntryNode<K,V> child = targetEntryNode;
//:::判斷當前孩子節點是否是雙親節點的左孩子
while(parent != null && parent.right == child){
//:::不是左孩子，是右孩子，繼續向上尋找
child = parent;
parent = parent.parent;
}
return parent;
}
}
/**
* 獲得二叉搜尋樹的第一個節點
* */
private EntryNode<K,V> getFirstNode(){
if(this.root == null){
//:::空樹，返回null
return null;
}
EntryNode<K,V> entryNode = this.root;
//:::迴圈往復，尋找整棵樹的最左節點(最小節點、第一個節點)
while(entryNode.left != null){
entryNode = entryNode.left;
}
return entryNode;
}
}
View Code
我們已經實現了一個二叉搜尋樹，遺憾的是，實現的並不是更強大的平衡二叉搜尋樹。
平衡二叉搜尋樹的實現遠比普通二叉搜尋樹複雜，難理解。但凡事不能一蹴而就，要想理解更復雜的平衡二叉搜尋樹，理解普通的、非平衡的二叉搜尋樹是基礎的一步。希望大家能更好的理解二叉搜尋樹，更好的理解自己所使用的資料結構，寫出更高效，易維護的程式。
本系列部落格的程式碼在我的 github上： https://github.com/1399852153/DataStructures ，存在許多不足之處，請多多指教。