前言：耗费了五个多小时，算是差不多了 红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下要求： 下图就是一个典型的红黑树： 但实现上我省略了其中的 Nil 结点，一般如下图，大家理解时也可以忽略它们。 优势和用途 我们知道二叉查找树在不停地添加或删除结点后，可能会导致结点情况如下： 这种情况下，二叉查找树的查找效率最坏会降低为 O(n)。 而红黑树由于在插入和删除结点时都会进行变色旋转等操作，在符合红黑树条件的情况下，即使一边子树全是黑色结点，另一边子树全是红黑相间，两子树的高度差也不会超过一半。一棵有 n 个结点的红黑树高度至多为 2log(n+1)，查找效率最坏为 O(log(n))。 所以红黑树常被用于需求查找效率稳定的场景，如 Linux 中内核使用它管理内存区域对象、Java8 中 HashMap 的实现等，所以了解红黑树也很有意义。 下面介绍一下红黑树的等同 2-3-4树。 2-3-4树 2-3-4树是四阶的 B树(Balance Tree)，它的结构有以下限制： 下图是一个典型的 2-3-4树（来自维基百科）： 2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。 红黑树维持平衡的方式 对应红黑树 至于为什么说红黑树是 2-3-4树的一种等同呢，这是因为 2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵 2-3-4树也都对应一棵红黑树，下图是 2-3-4树不同结点与红黑树子树的对应。 而上文中的 2-3-4树也可以转换成一棵红黑树： 由红黑树的性质5，和 2-3-4树的性质1，为了便于理解红黑树和 2-3-4树的对应关系，我们可以把红黑树从根结点到叶子结点的黑色结点个数定义为高度。 红黑树和 2-3-4树的结点添加和删除都有一个基本规则：避免子树高度变化，因为无论是 2-3-4树还是红黑树，一旦子树高度有变动，势必会影响其他子树进行调整，所以我们在插入和删除结点时尽量通过子树内部调整来达到平衡，2-3-4树实现平衡是通过结点的旋转和结点元素数变化，红黑树是通过结点旋转和变色。 下面来对照着 2-3-4树说一下红黑树结点的添加和删除： 结点插入 2-3-4树中结点添加需要遵守以下规则： 而将这些规则对应到红黑树里，就是： 如上图所示，虽然向红黑树中插入了一个新结点，但由于旋转和变色，子树的高度保持不变。 删除结点 红黑树的删除要比插入要复杂一些，我们还是类比 2-3-4树来讲： 将这些规则对应到红黑树中即： […]

基本概念 字典树是一种有序的树状结构，每个节点表示字符与字符串。字典树可以合并储存有相同前缀的字符串。常用于解决前缀匹配和字串查找的问题。是一种牺牲空间换取时间的做法。 插入 字串长度的时间 插入一个新单词 查找 单词长度的时间 查找是否存在某单词 查找是否存在某前缀 实现 通过HashMap实现子节点 class TrieNode {    String word;    HashMap<Character, TrieNode> next;​    public TrieNode() {        next = new HashMap<>();   }}​class TrieTree {    public TrieNode root;​    public TrieTree(TrieNode root) {        this.root = root;   }​    public […]