程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 一步一步寫算法(之哈希二叉樹)

一步一步寫算法(之哈希二叉樹)

編輯:關於C

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

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

 

 

/*

*         7        3

*        /           \

*       6             4

*      /                \

*     5                  7

*    /                    \

*   2                     12

*  /                        \

* 1                         20

*/ 

/*

*         7        3

*        /           \

*       6             4

*      /                \

*     5                  7

*    /                    \

*   2                     12

*  /                        \

* 1                         20

*/

 

 

    上面的這幅圖很能說明問題,雖然查詢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; 

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; 

STATUS add_node_into_tree(HASH_TREE** ppHash, int data)

{

 

       /* add hash node into tree */

 

       /* add hash node into hash table */

 

       return TRUE;

}    添加的代碼如此,刪除工作也比較類似。

 

 

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; 

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;

}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved