介绍LRU缓存实际就是将最近最少使用的数据删除的缓存策略，举个例子缓存长度为3，目前有三个值分别是 [1, 2, 3]然后我们访问缓存的顺序为 1 1 1 2 3此时我们需要新增一个缓存，因为超过缓存长度所以我们需要先将1删除空出位置，因为最近访问了2和3，1是最早访问的故删除(即使他之前访问次数最多)实现因为get和put都需要O(1)，因此我们采用哈希表来做，具体做法就是如果缓存命中，则...

介绍LFU缓存其实就是删除最不常用的缓存策略，例子如下缓存最大3个数，值为 [1,2,3]访问顺序: 1 1 1 2 2 3新增值时需要删除的值为3 因为3最访问了一次是最少的(即使他刚刚访问过)由此可见，相比较LRU缓存LFU更关注访问的次数而不是最近访问的啥，关于LRU缓存可以看我上一篇文章LRU缓存实现class LFUCache<T, U> { private siz...

基础满二叉树定义: 除最后一层没有任何子节点外 每一层节点都有两个子节点数学公式: 层次为h(从0开始) 深度为d(h+1) 节点总数n每一层的节点个数: 2^n节点总数: 2^d -1深度: log2n完全二叉树定义: 除了最后一层外 其他各层节点数都是满的 且最后一层的节点都连续集中在左边二叉堆定义: 二叉树就是满足如下性质的完全二叉树大顶堆: 父节点的值比每个子节点的值要大小顶堆: 父...

介绍定义平衡二叉树又叫平衡二叉排序树，听名字知道和二叉排序树相关。实际上平衡二叉树就是每个节点最大高度差为1的二叉排序树。相比较二叉排序树，平衡二叉树查找，插入和删除的时间复杂度都维持在O(logn)。不了解二叉排序树的可以看看我的上一篇文章二叉排序树平衡因子节点左右子树的高度差就是平衡因子，值只能为0, -1和1，分别对应左右等高，右比左高，左比右高。叶子节点的平衡因子始终为0最小失衡树新...

介绍二叉排序树又称二叉搜索树，听名字都知道是方便排序和查找的树定义可以是一颗空树 或者是具有如下性质的二叉树若左子树不空 则左子树上所有节点的值都小于根节点的值若右子树不空 则右子树上所有节点的值都大于根节点的值它的左右子树也都是二叉排序树特点中序遍历是一个有序序列，比如上图的中序遍历结果是: [1, 3, 4, 6, 7, 8, 9, 10, 13, 14]查找复杂度取决于深度，好的话是二...