基于二叉樹(shù)實(shí)現(xiàn)Map
“程序員常用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin
微信公眾號(hào)：貝塔學(xué)Java
”
前言
在上一篇中我們基于數(shù)組和鏈表實(shí)現(xiàn)了Map的相關(guān)操作，但是對(duì)于數(shù)據(jù)量稍大的情況下，這兩種實(shí)現(xiàn)方式效率都比較低，為了改進(jìn)這個(gè)問(wèn)題，本篇我們將來(lái)學(xué)習(xí)二叉樹(shù)，并通過(guò)二叉樹(shù)來(lái)實(shí)現(xiàn)上一篇中定義的Map結(jié)構(gòu)
二叉樹(shù)簡(jiǎn)介
雖然大家都知道二叉樹(shù)是什么，但是為了保證文章的完整性，這里還是簡(jiǎn)單說(shuō)說(shuō)什么是二叉樹(shù)
二叉樹(shù)中每個(gè)節(jié)點(diǎn)都包含了兩個(gè)指針指向自己的左子樹(shù)和右子樹(shù)。
二叉樹(shù)的每個(gè)節(jié)點(diǎn)都包含了一個(gè)Key, 并且每個(gè)節(jié)點(diǎn)的Key都大于其左子樹(shù)中的任意節(jié)點(diǎn)，小于右子樹(shù)中的任意節(jié)點(diǎn)。
節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義：
class Node {
private K key;
private V value;
private Node left;
private Node right;
private int size = 1;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
size 記錄當(dāng)前節(jié)點(diǎn)所在子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，計(jì)算方式：size=左子樹(shù)的個(gè)數(shù) + 1 + 右子樹(shù)的個(gè)數(shù)
基于二叉樹(shù)實(shí)現(xiàn)Map
在上一篇《基于數(shù)組或鏈表實(shí)現(xiàn)Map》中我們定義了Map的接口，本篇我們繼續(xù)使用該map接口
public interface Map<K, V> {
void put(K key, V value);
V get(K key);
void delete(K key);
int size();
Iterable<K> keys();
Iterable<TreeNode> nodes();
default boolean contains(K key) {
return get(key) != null;
}
default boolean isEmpty() {
return size() == 0;
}
}
public interface SortedMap<K extends Comparable<K>, V> extends Map<K, V> {
int rank(K key);
void deleteMin();
void deleteMax();
K min();
K max();
}
查詢
在二叉樹(shù)中查找一個(gè)鍵最簡(jiǎn)單直接的方式就是使用遞歸，把查找的key和節(jié)點(diǎn)的key進(jìn)行比較，如果較小就去左子樹(shù)中繼續(xù)遞歸查找，如果較大就在右子樹(shù)中查找，如果相等，表示已找到直接返回value，如果遞歸結(jié)束還未找到就返回null
代碼實(shí)現(xiàn)：
@Override
public V get(K key) {
if (Objects.isNull(key)) {
throw new IllegalArgumentException("key can not null");
}
Node node = get(root, key);
return Objects.isNull(node) ? null : node.value;
}
private Node get(Node node, K key) {
if (Objects.isNull(node)) {
return null;
}
int compare = key.compareTo(node.key);
if (compare > 0) {
return get(node.right, key);
} else if (compare < 0) {
return get(node.left, key);
} else {
return node;
}
}
查詢出最大值和最小值
在二叉樹(shù)中我們可能會(huì)經(jīng)常使用到查詢樹(shù)中的最大值和最小值，包括后面我們的刪除操作也會(huì)使用到，所以這里我們需要實(shí)現(xiàn)這兩個(gè)方法；
最大值的實(shí)現(xiàn)：從根節(jié)點(diǎn)開(kāi)始沿著右子樹(shù)遞歸，直到遇到右子樹(shù)為null的時(shí)候就結(jié)束，此時(shí)的節(jié)點(diǎn)就是最大值 最小值的實(shí)現(xiàn)：從根節(jié)點(diǎn)開(kāi)始沿著左子樹(shù)遞歸，知道遇到左子樹(shù)為null的時(shí)候就結(jié)束，此時(shí)的節(jié)點(diǎn)就是最小值
@Override
public K max() {
Node max = max(root);
return max.key;
}
protected Node min(Node node) {
if (Objects.isNull(node.left)) {
return node;
}
return min(node.left);
}
protected Node max(Node node) {
if (Objects.isNull(node.right)) {
return node;
}
return max(node.right);
}
插入
從上面的實(shí)現(xiàn)我們可以看出二叉樹(shù)的查詢方法和上篇中數(shù)組二分查找法實(shí)現(xiàn)的一樣簡(jiǎn)單高效，這是二叉樹(shù)的一個(gè)重要特性，而且二叉樹(shù)的插入與查詢操作一樣簡(jiǎn)單，理想情況下插入和查詢操作時(shí)間復(fù)雜度都是log(N)
插入操作的實(shí)現(xiàn)思路：與查詢操作類似，依然是遞歸，如果put的key值比當(dāng)前節(jié)點(diǎn)大就需要去右子樹(shù)遞歸，如果較小就去左子樹(shù)遞歸，如果相等就直接更新節(jié)點(diǎn)的值。如果遞歸結(jié)束后還未找到值就新建一個(gè)節(jié)點(diǎn)并返回
private Node put(Node node, K key, V value) {
if (Objects.isNull(node)) {
return new Node(key, value);
}
int compare = key.compareTo(node.key);
if (compare > 0) {
node.right = put(node.right, key, value);
} else if (compare < 0) {
node.left = put(node.left, key, value);
} else {
node.value = value;
}
node.size = size(node.left) + 1 + size(node.right);
return node;
}
private int size(Node node) {
if (Objects.isNull(node)) {
return 0;
}
return node.size;
}
其中size的計(jì)算在前面已經(jīng)說(shuō)到，當(dāng)前節(jié)點(diǎn)的size = 左子樹(shù).size + 1 + 右子樹(shù).size
刪除最大值和最小值
二叉樹(shù)中相對(duì)比較麻煩的操作就是刪除操作，所以我們先來(lái)了解下刪除最大值和最小值應(yīng)該如何實(shí)現(xiàn)。
刪除最小值：和前面實(shí)現(xiàn)查找最小值有些相似，沿著左邊路徑一直深入，直到遇到一個(gè)節(jié)點(diǎn)的左子樹(shù)為null, 那么這個(gè)當(dāng)前節(jié)點(diǎn)就是最小值，在遞歸中把當(dāng)前節(jié)點(diǎn)的右子樹(shù)返回即可；
最大值實(shí)現(xiàn)思路類似
代碼如下：
@Override
public void deleteMin() {
root = deleteMin(root);
}
public Node deleteMin(Node node) {
if (Objects.isNull(node.left)) {
return node.right;
}
node.left = deleteMin(node.left);
node.size = size(node.left) + 1 + size(node.right);
return node;
}
@Override
public void deleteMax() {
root = deleteMax(root);
}
public Node deleteMax(Node node) {
if (Objects.isNull(node.right)) {
return node.left;
}
node.right = deleteMax(node.right);
node.size = size(node.left) + 1 + size(node.right);
return node;
}
刪除
我們可以通過(guò)類似的方式去刪除只有一個(gè)子節(jié)點(diǎn)或者是沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)；但是如果遇到需要?jiǎng)h除有兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)應(yīng)該怎么操作呢？
兩種思路：用左子樹(shù)的最大值替換待刪除節(jié)點(diǎn)，然后刪除掉左子樹(shù)的最大值；或者是用右子樹(shù)中的最小值替換待刪除節(jié)點(diǎn)，然后刪除右子樹(shù)中的最小值
步驟：
從該節(jié)點(diǎn)的左子樹(shù)中取出最大值或者是從右子樹(shù)中取出最小值 用最大值或者最小值替換當(dāng)前的節(jié)點(diǎn) 調(diào)用刪除最大值或者刪除最小值
代碼實(shí)現(xiàn)
@Override
public void delete(K key) {
root = delete(root, key);
}
private Node delete(Node node, K key) {
if (Objects.isNull(node)) {
return null;
}
int compare = key.compareTo(node.key);
if (compare > 0) {
node.right = delete(node.right, key);
} else if (compare < 0) {
node.left = delete(node.left, key);
} else {
if (Objects.isNull(node.left)) {
return node.right;
}
if (Objects.isNull(node.right)) {
return node.left;
}
Node max = max(node.left);
node.key = max.key;
node.value = max.value;
node.left = deleteMax(node.left);
}
node.size = size(node.left) + 1 + size(node.right);
return node;
}
分析
使用二叉樹(shù)實(shí)現(xiàn)的Map運(yùn)行的效率取決于樹(shù)的形狀，而樹(shù)的形狀取決于數(shù)據(jù)輸入的順序；最好的情況下二叉樹(shù)是平衡的，那么get、put的時(shí)間復(fù)雜度都是log(N); 但是如果插入的數(shù)據(jù)是有序的，那么二叉樹(shù)就會(huì)演變成鏈表，那么get、put的性能將會(huì)大大減低；
基于這個(gè)問(wèn)題，我們會(huì)繼續(xù)改進(jìn)我們實(shí)現(xiàn)的Map，下一篇我們將會(huì)學(xué)習(xí)使用紅黑樹(shù)來(lái)實(shí)現(xiàn)我們的Map操作，無(wú)論數(shù)據(jù)插入的順序如何都能保證二叉樹(shù)近似平衡
文中所有源碼已放入到了github倉(cāng)庫(kù)https://github.com/silently9527/JavaCore
最后（點(diǎn)關(guān)注，不迷路）
文中或許會(huì)存在或多或少的不足、錯(cuò)誤之處，有建議或者意見(jiàn)也非常歡迎大家在評(píng)論交流。
最后，寫(xiě)作不易，請(qǐng)不要白嫖我喲，希望朋友們可以點(diǎn)贊評(píng)論關(guān)注三連，因?yàn)檫@些就是我分享的全部動(dòng)力來(lái)源??