首页 > 程序开发 > 软件开发 > C语言 >

一步一步写算法(之哈希二叉树)

2011-11-02

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 用过平衡二叉树的朋友都清楚,平衡二叉树的最大优点就是排序。不管是在数据插入的时候还是在数据删除的时候,我们都要考...

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱: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;

}

相关文章
最新文章
热点推荐