C++算法之哈希二叉树

2015/06/15 40661

用过平衡二叉树的朋友都清楚，平衡二叉树的最大优点就是排序。不管是在数据插入的时候还是在数据删除的时候，我们都要考虑到数据的排序情况。但是和数据的添加、删除一样重要的，还有数据的查询。很不幸，平衡二叉树经常由于节点的添加和删除，数据的查询效率会变得非常低下。朋友们可以看看下面这样的一个极端场景，所有分支节点都只有一边存在数据：

/* 
*         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;

其实，相比较普通的平衡二叉树而言，也就是多了一个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 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）哈希二叉树的思想比较重要，同学们最好弄清楚为什么要建立hash二叉树？
（2）上面的代码不是很完整，对hash表不熟悉的朋友可以参考我写的这一篇博客（hash表），二叉树添加删除不熟悉的朋友同样可以参考我写的另外一篇博客（添加，删除1，删除2，删除3），把两部分代码按照上面给出的结构合起来基本上就可以实现哈希二叉树了。

代码片段