【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
用过平衡二叉树的朋友都清楚,平衡二叉树的最大优点就是排序。不管是在数据插入的时候还是在数据删除的时候,我们都要考虑到数据的排序情况。但是和数据的添加、删除一样重要的,还有数据的查询。很不幸,平衡二叉树经常由于节点的添加和删除,数据的查询效率会变得非常低下。朋友们可以看看下面这样的一个极端场景,所有分支节点都只有一边存在数据:
/*
* 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),把两部分代码按照上面给出的结构合起来基本上就可以实现哈希二叉树了。
分享到:
相关推荐
4、写出查找的递归函数;注意:递归出口的处理要求:二叉排序树的程序填空:修改 “BiSearchTree.h” 文件中的myorder()函数,得到二叉排序树的降序序列,要求达到BiSearchTree.exe的执行效果。
清楚明白的演示了数据结构中栈、队列、二叉树、霍夫曼算法、哈希表等等一系列数据结构里面有关算法 实用 有效 是学习数据结构必备“良药”!
C#算法实现(哈希表 图 二叉树 KMP prim 最短路径 各种排序)!希望大家喜欢!
C++股票信息查询系统源代码,实现多种查询排序算法KMP算法、二叉树、哈希表等,C++课程设计
数据结构-查找算法 二分查找 二叉顺序数 哈希查找
C语言版 数据结构与算法课程 第4章 哈希表(共49页).ppt C语言版 数据结构与算法课程 第5章 递归算法(共77页).pptx C语言版 数据结构与算法课程 第6章 二叉树(共117页).ppt C语言版 数据结构与算法课程 第7章 ...
此文档,包含了 树,二叉树,数据结构与算法,排序,哈希表等难点重点详解。希望对于学习有帮助。
面试中,经常要用到的数据结构(链表、队列、栈、二叉树、哈希表等)以及一些常用的算法(排序:归并、快速排序、基数排序等,查找:二分查找法),,统一由JAVA实现.
面试中,经常要用到的数据结构(链表、队列、栈、二叉树、哈希表等)以及一些常用的算法(排序:归并、快速排序、基数排序等,查找:二分查找法),,统一由JAVA实现..zip
C语言版 数据结构与算法课程 第4章 哈希表(共49页).ppt C语言版 数据结构与算法课程 第5章 递归算法(共77页).pptx C语言版 数据结构与算法课程 第6章 二叉树(共117页).ppt C语言版 数据结构与算法课程 第7章 ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
KMP模式匹配算法、哈夫曼编码算法、由遍历序列恢复二叉树、Prim算法、Kruskal算法、Floyd算法、Dijkstra算法、拓扑排序、关键路径算法、二叉排序树生成算法(含平衡化)、哈希表生成及哈希查找算法、希尔排序、快速...
从查找时间与存储形式2个方面对读卡器信息哈希存储算法进行了试验与研究,通过试验得到了哈希表存储算法和哈希二叉树存储算法2种算法的查找效率与应用场合,为读卡器存储算法的选择提供了借鉴。
包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
10.s8算法2-4 链表 哈希表 11.s8算法2-5 算法题 12.S8设计模式-1 设计模式简介 13.S8设计模式-2 创建型模式 14.S8设计模式-3 结构型模式 15.S8设计模式-4 行为型模式 16.5 设计模式总结 17.6 二叉树 18.7 算法进阶 2...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题...哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS...
【数据结构】基数排序的...寻位和定位算法基于键对象之哈希值的每一个二进制位的状态所构造的二叉树。 32位长最多执行4次寻位或定位运算(近似常数时间)。 64位长哈希表最多执行8次寻位或定位运算(近似常数时间)。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用循环双向链表, 能实现多个长整型进行加法运算 插入排序法 程序设计...