C++算法之哈希二叉樹

用過平衡二叉樹的朋友都清楚，平衡二叉樹的最大優點就是排序。不管是在數據插入的時候還是在數據刪除的時候，我們都要考慮到數據的排序情況。但是和數據的 添加、刪除一樣重要的，還有數據的查詢。很不幸，平衡二叉樹經常由于節點的添加和刪除，數據的查詢效率會變得非常低下。朋友們可以看看下面這樣的一個極端 場景，所有分支節點都只有一邊存在數據：

/*


7        3 
/           \ 
6             4 
/                \ 
5                  7 
/                    \ 
2                     12 
/                        \ 
1                         20 
*/  

</pre>     上面的這幅圖很能說明問題，雖然查詢7、6很方便，但是查詢5、2、1的時候效率就非常低了，右邊的二叉樹也是這種情況。那么有沒有辦法使得數據之間的查找效率不至于相差太大呢？截止目前為止，主要有下面三種方法：

     （1）哈希二叉樹

     （2）avl樹

     （3）紅黑樹

      今天我們主要講解的內容就是哈希樹。其他兩個內容會在后面的博客里面介紹。

     那么什么是哈希樹呢？其實也非常簡單，就是我們在二叉樹節點中添加一個next指針，同時建立一個hash表，這樣我們在查詢數據的時候就可以直接利用hash查詢代替平衡二叉樹的查詢了。一般來說，哈希樹的節點應該是這樣定義的：


typedef struct _HASH_TREE  
{  
    int data;  
    struct _HASH_TREE* next;  
    struct _HASH_TREE* left;  
    struct _HASH_TREE* right;  
}HASH_TREE;  
     其實，相比較普通的平衡二叉樹而言，也就是多了一個next指針而已，那么這個next指針什么時候需要處理呢？主要就是在添加節點和刪除節點的時候處理。

STATUS add_node_into_tree(HASH_TREE** ppHash, int data)

{


/* add hash node into tree */  

/* add hash node into hash table */  

return TRUE;  

}

    </pre> 添加的代碼如此，刪除工作也比較類似。
STATUS delete_node_from_tree(HASH_TREE* ppHash, int data)

{

    HASH_TREE pNode;

    / delete hash node from tree, but not free space/


/* delete hash node from hash table */  

free(pNode);  
return TRUE;  

}

</pre> 

 說明：

     （1）哈希二叉樹的思想比較重要，同學們最好弄清楚為什么要建立hash二叉樹？

     （2）上面的代碼不是很完整，對hash表不熟悉的朋友可以參考我寫的這一篇博客（hash表），二叉樹添加刪除不熟悉的朋友同樣可以參考我寫的另外一篇博客（添加，刪除1，刪除2，刪除3），把兩部分代碼按照上面給出的結構合起來基本上就可以實現哈希二叉樹了。