Trie树


Trie树一切知识都从一个小问题开始:​给定一些命令,如set, setbit, setnx, strlen,get, getbit, exists 实现自动补全功能,例如输入se, 提示set, setbit, setnx 此视频为录制的redis客户端命令操作,很显然r

布隆过滤器


布隆过滤器前置知识:位图算法在讲位图算法时我们说到位图算法的缺陷是不能处理数据重复问题,也就是数据hash值产生冲突时,只知道这里有值,但是不知道有几个,是谁的。最经典的问题就像这个:假设有一个10亿的email黑名单,怎么通过这个黑名单过滤邮件?当然,你可能会说,是不是布隆过滤器?我当然也会回答你

数据结构与算法(十五)堆树


定义是一颗完全二叉树每一个结点都大于等于它的子结点(大顶堆),或者小于等于它的子结点(小顶堆)图解堆的插入过程从下往上从上往下其插入的过程就叫做堆化堆的删除过程初始化堆的过程代码实现publicclassHeapTree{privateint[]arr;publicHeapTree(){}publi

数据结构与算法(十四)哈夫曼树


问题给定一串字符串:abcd,如何压缩?我们知道每个字节在计算机中占8bit,假使我们定义二进制00表示a,01表示b,10表示c,11表示d那么abcd转为二进制后就变成了00011011,看,原本占4*8=32bit的一串字符串,现在只占8bit了,是不是压缩了4倍,nice!给定一串字符串:a

数据结构与算法(十三)B+树


性质M阶的B+数据每个结点最多存储m-1个元素每个结点最多有m个子结点根结点要么为空,要么为独根,否则至少有2个子结点除根节点外,每个结点至少有m/2个子结点,除不尽则往上取整,7/2=3.5-->4叶子结点的高度一致只有叶子结点才存储数据叶子结点之间通过指针相连,提高区间的访问性能图示构建过

数据结构与算法(十二)红黑树


数据结构可视化学习网址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html性质1.每个结点不是红色就是黑色2.每个叶子节点都是黑色的空节点(NIL),根结点都是黑色3.不可能有相连的红色的结点。4.每个结点到其可达叶子结点的所

数据结构与算法(十一)二叉搜索树


特点左子树的每个结点的值都比根节点小,右子树的每个结点的值都比根节点大中序遍历为一个有序序列图时间复杂度查找O(logn)插入O(1)删除O(logn)寻找前继结点或者后继结点替换删除的结点前继结点:第一个比根节点小的数后继结点:第一个比根节点大的数代码实现publicclassTreeNode&l

数据结构与算法(十)树


树形结构的相关术语结点:树里面的元素父子关系:结点之间相连的边子树:当结点大于1时,其余结点分为的互不相交的集合度:一个结点拥有的子树数量称为结点的度叶子:度为0的结点孩子:结点的子树的根节点双亲:兄弟:同一个双亲结点森林:由N个互不相交的树构成深林结点的高度:结点到叶子结点的最长路径结点的深度:根