logo头像

待到风起时,扬帆济沧海

深度优先和广度优先

深度优先和广度优先

1、深度优先搜索介绍图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先...

图-基本概念

图-基本概念

图的定义定义:图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的;其中,点通常被成为”顶点(vertex)”,而点与点之间的连线则被成为”边或弧”(edege)。通常记为,G=(V,E)。 图的种类根据边...

二叉堆

二叉堆

堆和二叉堆的介绍堆的定义堆(heap),这里所说的堆是数据结构中的堆,而不是内存模型中的堆。堆通常是一个可以被看做一棵树,它满足下列性质: 堆中任意节点的值总是不大于(不小于)其子节点的值 堆总是一棵完全树。将任意节点不大于其子节点...

伸展树(SplayTree)

伸展树(SplayTree)

伸展树介绍伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。(01) 伸展树属于二叉查找树,即它具有和二叉查找树一样的性...

AVL树

AVL树

AVL树介绍AVL树是高度平衡的而二叉树。它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。上面的两张图片,左边的是AVL树,它的任何节点的两个子树的高度差别都<=1;而右边的不是AVL树,因为7的两颗子树的高度相差为...

红黑树

红黑树

红-黑树的概念上一篇二叉搜索树,二叉搜索树对于某个节点而言,其左子树的节点关键值都小于该节点关键值,右子树的所有节点关键值都大于该节点关键值。二叉搜索树作为一种数据结构,其查找、插入和删除操作的时间复杂度都为O(logn),底数为2。...

二叉树

二叉树

树的基本概念 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上...

算法笔记

算法推导大O阶方法 用常数1取代运行时间中的所有加法常数 在修改后的运行次数函数中,只保留最高阶项 如果最高阶存在且不是1,则去除与这个项相乘的常数 常数阶首先顺序结构的时间复杂度。下面这个算法案例:123int sum=0,n=1...

Go-channel总结

channel的使用场景把channel用在数据流动的地方: 消息传递、消息过滤 信号广播 事件订阅与广播 请求、响应转发 任务分发 结果汇总 并发控制 同步与异步 channel的基本操作和注意事项channel 存在3种状态 ...