Data Structure
2 篇二叉平衡树之 AVL 树
最近折腾了一下 AVL 树，留点笔记给未来的自己看看 :) 二叉树是基本的树结构，有左右两个孩子。一般情况下，查找可以做到 O(log n) 的时间复杂度。但是对于极端情况，可能恶化成 O(n)，这相当不妙。当输入的数据是线性的，新增的子节点就会都在左子树（递减情况）或者右子树（递增情况）。如下图：  二叉树是基本的树结构，有左右两个孩子。一般情况下，查找可以做到 O(log n) 的时间复杂度。但是对于极端情况，可能恶化成 O(n)，这相当不妙。当输入的数据是线性的，新增的子节点就会都在左子树（递减情况）或者右子树（递增情况）。如下图： ![ 二叉树蜕变成线性查找 ](https://g.gravizo.com/svg? digraph G { n1 [label=None] n2 [label=None] n3 …
博客中英文间添加空格
因为新冠病毒肺炎疫情，春节在家待了 11 天了，百无聊赖之下，想着优化一下老博客的排版。准备在中英文间补上空格，显得更美观一点，结果一篇博客都没改完就觉得累死了。。准备写工具来搞 搜了一下有 现成的代码 ，但是依赖 Pelican。作者还提到可以用 MPT 优化，但是我看了一下 MPT 的介绍，是类似前缀树的东西，每次取一个字符分析的话，是不会取到一个串的，前缀树用不上，倒是可以用二叉树简化一下区间查找。于是读完了 GeeksForGeeks 的 interval tree 介绍 ，自己实现了二 …
因为新冠病毒肺炎疫情，春节在家待了 11 天了，百无聊赖之下，想着优化一下老博客的排版。准备在中英文间补上空格，显得更美观一点，结果一篇博客都没改完就觉得累死了。。准备写工具来搞 搜了一下有 现成的代码 ，但是依赖 Pelican。作者还提到可以用 MPT 优化，但是我看了一下 MPT 的介绍，是类似前缀树的东西，每次取一个字符分析的话，是不会取到一个串的，前缀树用不上，倒是可以用二叉树简化一下区间查找。于是读完了 GeeksForGeeks 的 interval tree 介绍 ，自己实现了二 …