Tag-数据结构

 2017-08-08 22:32:07 |  0 Comments  |  数据结构

散列表

# 介绍 散列表(Hash table,也叫哈希表),是根据键值(Key value)而直接进行访问的数据结构。 类比数组,数组的键就是0,1,2,3...依次对应val1,val2。在物理上,数据也的确是按这样顺序排列在内存中,所以数组的查找是非常快的,它是用数组指针加偏移量来快速定位(O(1)),但是他的插入与删除就很糟糕需要大量的移动来腾出空间。 ![](https://leanot
 2017-07-31 10:37:32 |  0 Comments  |  数据结构

并查集

# 介绍 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表。 并查集用于塑造一组不相交的集合,并且能高效的(接近常数级)判断某个元素属于哪个集合,能判断两个元素是否属于同一个集合中,在必要的时候能合并两个集合。 它可以用于在无向图中查找连接的组件,因此可以用作Kruskal的最小生成树(MST)问题的算法的一部分。 ## 并查集的表示 并查集可以使用树来实现, 下图中,每棵树
 2017-06-10 20:27:30 |  0 Comments  |  数据结构

优先队列与二叉堆

# 优先队列 这个是优先队列的概念图 ![](https://leanote.com/api/file/getImage?fileId=593a89feab64410b6b001eff) 虽然名字中有队列二字,但操作上却不是先进后出,取数据时是取出优先级最高的,这里优先级可以通过元素的值来体现,可以认为值越小的优先级越高,或者值越大的优先级越高. 优先队列的操作基本上就上图所述的那两个
 2017-02-15 20:15:21 |  0 Comments  |  数据结构

树_AVL

# AVL树的实现 普通的二叉搜索树在多出插入删除后,左右子树节点数可能会出现较大的差异,此时插入删除操作的复杂度就不确定了。而AVL树能在插入或删除后自行调整结构,做到左右子树差不多高。 AVL是**平衡树**的一种 AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis ## 特点 - 自平衡的二叉搜索树,AVL树中任何节点的两个子树的高度最大差
 2017-02-15 20:15:11 |  0 Comments  |  数据结构

树_二叉查找树

# 二叉搜索树的实现 二叉搜索树也称二叉查找树 ## 特点 - 左子节点的值<根节点的值<右子节点的值 - 左右子树都是二叉搜索树 - 所有的节点的值不重复 **性能特点** 查找、插入的时间复杂度较低。为O(log n) 查找过程有点像`折半查找`,从父节点到子节点问题的规模就减半`t(n) = t(n/2) + c2`,所有其复杂度是O(log n),插入也是类似的。 ## 节点结构 ``` Python class SBTNode(): def __init__(self,value=None,parent=None,left=None,right=None): self.left = left self.parent = parent self.right = right self.value=value #使用魔法方法自定义比较运算符效果 def __gt__(self, other): return self.value>other.value def __ge__(self, other): return self.value>=other.value def __lt__(self, other): return self.value temp:
 2017-01-19 21:34:29 |  0 Comments  |  数据结构

树_基本概念

# 前言 本文继承自http://www.cnblogs.com/skywang12345/p/3576452.html 结合<<数据结构与算法分析>> 使用Python实现 # 名词解释 **结点的度**:结点拥有的子树的数目。 **叶子**:度为零的结点。 **分支结点**:度不为零的结点。 **树的度**:树中结点的最大的度。 **层次**:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1。