哈希二叉樹：結合雜湊表與樹結構的高效查找方案

在資料結構的世界裡，平衡二叉樹（如 AVL 樹、紅黑樹）以其優異的排序特性聞名，無論是插入、刪除還是查詢，理論時間複雜度均為 O(log n)。然而，現實場景中，頻繁的節點增刪導致樹結構退化，查詢效率大幅下降。例如極端情況下，所有分支節點僅單側擁有資料，樹結構退化為鏈表，查詢深層節點時效率極低。

為什麼需要哈希二叉樹？

傳統平衡二叉樹雖能維持有序性，但查詢操作仍需從根節點逐層遍歷。當資料量龐大且查詢頻繁時，這種「由根至葉」的路徑代價不可忽視。為了讓所有節點的查找效率趨於均衡，業界主要提出三種改良方案：哈希二叉樹、AVL 樹、紅黑樹。本文重點探討哈希二叉樹的設計思想與實作細節。

核心概念：在樹節點加入 next 指標

哈希二叉樹的精髓極其簡單：在傳統二叉樹節點結構中新增一個 next 指標，並同步維護一個雜湊表。查詢時直接利用雜湊表的 O(1) 平均查找特性，繞過樹的層層遍歷。節點結構定義如下：

typedef struct _HASH_TREE {
    int data;
    struct _HASH_TREE* next;  // 雜湊鏈表指標
    struct _HASH_TREE* left;
    struct _HASH_TREE* right;
} HASH_TREE;

相較於普通平衡二叉樹，僅多出一個 next 指標。這個指標在節點插入與刪除時需同步維護。

關鍵操作實作

節點插入

STATUS add_node_into_tree(HASH_TREE** ppHash, int data) {
    /* 1. 將節點插入二叉樹（維持排序性） */
    /* 2. 將節點插入雜湊表（維護 next 指標鏈） */
    return TRUE;
}

節點刪除

STATUS delete_node_from_tree(HASH_TREE** ppHash, int data) {
    HASH_TREE* pNode;
    /* 1. 從二叉樹移除節點（暫不釋放記憶體） */
    /* 2. 從雜湊表移除節點（斷開 next 指標鏈） */
    free(pNode);
    return TRUE;
}

插入與刪除的核心邏輯在於「雙重維護」：二叉樹負責有序存儲與範圍查詢，雜湊表負責精確鍵值的極速定位。兩者互補，構建出兼具排序與高效查找的混合結構。

適用場景與優勢

• 高頻精確查詢、低頻範圍查詢的業務
• 需兼顧排序遍歷與 O(1) 定位的系統
• 記憶體資源允許額外雜湊表開銷的環境

後續文章將深入剖析 AVL 樹與紅黑樹的平衡機制，敬請期待。