上面的这幅图很能说明问题,虽然查询7、6很方便,但是查询5、2、1的时候效率就非常低了,右边的二叉树也是这种情况。那么有没有办法使得数据之间的查找效率不至于相差太大呢?截止目前为止,主要有下面三种方法: (1)哈希二叉树 (2)avl树 (3)红黑树 今天我们主要讲解的内容就是哈希树。其他两个内容会在后面的博客里面介绍。 那么什么是哈希树呢?其实也非常简单,就是我们在二叉树节点中添加一个next指针,同时建立一个hash表,这样我们在查询数据的时候就可以直接利用hash查询代替平衡二叉树的查询了。一般来说,哈希树的节点应该是这样定义的:
- /*
- * 7 3
- * / \
- * 6 4
- * / \
- * 5 7
- * / \
- * 2 12
- * / \
- * 1 20
- */
其实,相比较普通的平衡二叉树而言,也就是多了一个next指针而已,那么这个next指针什么时候需要处理呢?主要就是在添加节点和删除节点的时候处理。
- typedef struct _HASH_TREE
- {
- int data;
- struct _HASH_TREE* next;
- struct _HASH_TREE* left;
- struct _HASH_TREE* right;
- }HASH_TREE;
添加的代码如此,删除工作也比较类似。
- 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;
- }
来源: http://www.phpxs.com/code/1004158/