分类 数据结构 下的文章

并查集是一种树型的数据结构,是一种从子节点指向父辈节点的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题,如网络中的连接问题,数学中集合类的问题。主要有两个方法:isConnected和union。

- 阅读剩余部分 -

又称单词查找树、前缀树、Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

- 阅读剩余部分 -

线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。

线段树用于解决和区间相关的问题。比如数组中索引a到索引b之间的最大值、和等。

- 阅读剩余部分 -

二叉堆(英语:binary heap)是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父節点的键值总是保持固定的序关系于任何一个子节点的键值,且每个節点的左子树和右子树都是一个二叉堆。

当父節点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父節点的键值总是小于或等于任何一个子节点的键值时为最小堆。

使用堆做优先队列非常方便。

- 阅读剩余部分 -

二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、多重集、关联数组等。

- 阅读剩余部分 -