雜湊二元樹：結合雜湊表與二元樹的高效查找混合結構

編輯：關於C語言

背景：平衡二元樹的查找瓶頸

AVL、紅黑樹等平衡二元樹雖保證 O(log N) 查找，但頻繁插入/刪除導致旋轉調整，實際效能波動大。極端情況下（如單邊鏈狀退化），查找降為 O(N)。

/* 極端退化範例：查找 1 需遍歷 7 個節點 */
      7           3
     /             \
    6               4
   /                 \
  5                   7
 /                     \
2                       12
/                         \
1                           20

三大改良方向比較

方案	核心思想	查找複雜度	維護成本
AVL 樹	嚴格平衡（高度差 ≤1）	O(log N)	高（頻繁旋轉）
紅黑樹	近似平衡（黑高一致）	O(log N)	中
雜湊二元樹	雜湊表直接定位 + 樹維持順序	O(1) 平均	低（雜湊表增刪 O(1)）

雜湊二元樹結構設計

節點新增 `next` 指標，串接同雜湊桶位的節點；外部維護一個雜湊表（指標陣列）。

typedef struct _HASH_TREE {
    int data;
    struct _HASH_TREE* next;  // 雜湊鏈表指標
    struct _HASH_TREE* left;  // 樹左子節點
    struct _HASH_TREE* right; // 樹右子節點
} HASH_TREE;

// 雜湊表：指標陣列，大小為質數
#define HASH_TABLE_SIZE 10007
HASH_TREE* g_hash_table[HASH_TABLE_SIZE] = {NULL};

unsigned int hash_func(int data) {
    return (unsigned int)data % HASH_TABLE_SIZE;
}

核心操作框架

插入：雙重維護

STATUS add_node_into_tree(HASH_TREE** ppHash, int data) {
    // 1. 樹中插入（標準 BST 邏輯，略）
    // insert_into_bst(ppHash, data);

    // 2. 雜湊表插入（頭插法）
    unsigned int idx = hash_func(data);
    HASH_TREE* pNode = find_in_bst(*ppHash, data); // 取得剛插入的節點指標
    if (pNode) {
        pNode->next = g_hash_table[idx];
        g_hash_table[idx] = pNode;
    }
    return TRUE;
}

刪除：雙重清理

STATUS delete_node_from_tree(HASH_TREE** ppHash, int data) {
    // 1. 從樹中刪除（標準 BST 刪除，取得被刪節點指標 pNode）
    HASH_TREE* pNode = find_in_bst(*ppHash, data);
    if (!pNode) return FALSE;

    // delete_from_bst(ppHash, data); // 樹結構調整

    // 2. 從雜湊表移除（單向鏈表刪除需記錄前驅）
    unsigned int idx = hash_func(data);
    HASH_TREE **pp = &g_hash_table[idx];
    while (*pp && *pp != pNode) pp = &(*pp)->next;
    if (*pp) *pp = pNode->next; // 旁路移除

    free(pNode);
    return TRUE;
}

查找：O(1) 直接命中

HASH_TREE* find_in_hash_tree(int data) {
    unsigned int idx = hash_func(data);
    HASH_TREE* p = g_hash_table[idx];
    while (p) {
        if (p->data == data) return p; // 精確匹配
        p = p->next;
    }
    return NULL;
}