Tag Archives: 数据结构

数据结构重读 - 哈希表

无论是折半查找、二叉排序树查找还是B树,性能都依赖于查找中的比较次数。

一种理想情况是不经过任何比较,一次直接定位索要查找的记录,即:若数据结构中存在关键字和K相等,则其必定在f(K)的存储位置上,我们称这个对应关系f为哈希函数

冲突(Collision):对不同的关键字,可能得到同一哈希地址,即存在key1!=key2,但f(key1)=f(key2)。此时称为冲突或碰撞。

由于在实际应用中,哈希函数都是压缩函数,所以冲突只能尽可能的减少,很难完全避免。

哈希表:根据[......]

继续阅读

数据结构重读 - 键树、字典树

键树,又称数字查找树(Digital Search Trees)是一棵度>=2的树,每个结点只含有组成关键字的符号。

键树有两种存储结构:

1、树的孩子-兄弟链表来表示键树。

每个Node有三个域:first指向第一棵子树的根指针;next指向右兄弟;info(可选的)记录附加数据。如下图:

查找过程是,从根结点出发,顺着first查找,如果相等,继续下一个first。否则沿着next查找。直到到了空指针为止。此时若仍未完成key的匹配,查找不成功。[......]

继续阅读

数据结构重读 - B树、B-树、B+树、B*树

本文是转载的,《B树、B-树、B+树、B*树》
B树
即二叉搜索树:

1.所有非叶子结点至多拥有两个儿子(Left和Right);

2.所有结点存储一个关键字;

3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

如:

B树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;

否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字[......]

继续阅读

数据结构重读 - 平衡二叉树(AVL树)

大二那会根本没蹋下心来看,觉得天书一般,连旋转都没搞明白。

今天仔细看了书,发现真的一点不难啊,鄙视自己……

首先是概念:

平衡二叉树是为了解决前面二叉排序树不均衡的问题,而加入了一种平衡机制。所以,平衡二叉树是一种特殊的二叉排序树(BST)

AVL树查找的平均和最差复杂度都是O(logn) !!!(BST的最坏是O(n))

AVL树的插入复杂度是O(logn)。

平衡二叉树(简称AVL树):对任意一个结点,它的左子树和又子树都是平衡二叉树(左子树都小于结点[......]

继续阅读

数据结构重读 - 二叉排序树(BST)

1、前面讨论了静态查找表,它们的特点是,数据是一次性就给好了。

2、而对于动态查找表,数据可以是在查找过程中动态添加、生成的。其实这概念不太严谨。

3、二叉排序树(BST):左子树上所有结点的值均小于根结点的值;右子树上所有结点的值均大于根结点上的值。

4、二叉排序树的查找过程:
(1)若树为空,直接返回/跳出。
(2)树非空,则
(a)若key==root.data,return true。
(b)若key<root.data, root = root.left[......]

继续阅读