logo头像

待到风起时,扬帆济沧海

数据结构

二叉堆

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

伸展树(SplayTree)

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

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...

数据结构算法总结

常用数据结构 数据结构分类 数据结构比较 O符号 O(1):最低的复杂度,无论数据量大小,耗时都不变,都可以在一次计算后获得。哈希算法就是典型的O(1) O(n):线性,n表示数据的量,当量增大,耗时也增大,常见有遍历算法 O(n²)...

栈和队列

栈概念 栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数...

双向链表

示意图 双向链表:只有一个指针指向最开始的结点。 双端(双向)链表:有两个指针分别指向两端的节点。 循环(双向)链表:指向形成一个闭环。:有两个指针分别指向两端的节点。 完整代码123456789101112131415161...

单向链表

操作流程示意图 完整代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657...