红黑树是一种性能非常优秀的数据结构，关键在于它能保证最坏的性能也是对数的，主要是因为它是一种平衡的树，所以也叫平衡查找树。要理解红黑树，最好先看看我的上一篇博客《算法4》符号表以及二叉查找树，了解二叉查找树以及我们为什么需要平衡查找树。

2-3查找树

二叉查找树中树高会受到输入数据的影响，极端情况下一棵树和一个链表没什么区别，所以我们需要一种树，它的所有叶节点到根节点的距离都是相等的

符号表

符号表就是键值对的集合，并且支持put和get操作。现实中符号表的应用非常广泛，所以这里介绍几种键值对的实现，主要是二叉查找树以及之后将要介绍的红黑树。 一个值得注意的点就是，符号表里面不允许重复的key，也就是put一个键值对时，会先查找符号表里面是否含有这个key，有的话就更改这个key对应的值，没有的话就新加一个键值对

两种简单实现：

（1）使用无序链表的顺序查找

我们维

Go 语言的 strings 包（strings.go）中用到了 Rabin-Karp 算法。Rabin-Karp 算法是基于这样的思路：即把字符串看作是字符集长度进制的数，由数值的比较结果得出字符串的比较结果。

　　朴素的字符串匹配算法为什么慢？因为它太健忘了，前一次匹配的信息其实有部分可以应用到后一次匹配中去，而朴素的字符串匹配算法只是简单的把这个信息扔掉，从头再来，因此，浪费了时间。好

今天要介绍一个这样的数据结构：

1. 单向链接
2. 有序保存
3. 支持添加、删除和检索操作
4. 链表的元素查询接近线性时间

——跳跃表 Skip List

一、普通链表

对于普通链接来说，越靠前的节点检索的时间花费越低，反之则越高。而且，即使我们引入复杂算法，其检索的时间花费依然为O(n)。为了解决长链表结构的检索问题，一位名叫William Pugh的人于1990年提出了跳跃表结构。基

题目：删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例：

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4  
你不需要考虑数组中超出新长度后面的元素。

思考：

因为是已排序的数组，所以重复的数会连续出现。例如：1,2,2,3,3,4
用两个指针i、j分别指向第0个和第一个元素，然后不断后移j，将其指向的元素分别与i指向的元素比较。
如果相等则不做任何操作，如果不等则将j指向的元素复制到i+1的位置，直到j到数组末尾位置。

实现：

public int removeDuplicates(int[] nums) {
int i = 0;
for (int j = 1; j < nums.length; j++) {
    if (nums[j] != nums[i]) {
        i++;
        nums[i] = nums[j];
    }
}
     return i + 1;
}

  本文转载自(https://juejin.im/post/5c891eaef265da2dd37c5dbe)

汉诺塔

有三个柱子，分别为 from、buffer、to。需要将 from 上的圆盘全部移动到 to 上，并且要保证小圆盘始终在大圆盘上。

这是一个经典的递归问题，分为三步求解：

① 将 n-1 个圆盘从 from -> buffer

② 将 1 个圆盘从 from -> to

③ 将 n-1 个圆盘从 buffer -> to

如果只有一个圆盘，那么只需要进行一次移动操作。

从上面的讨论可以知道，a_n = 2 * a_n-1 + 1，显然 a_n = 2ⁿ - 1，n 个圆盘需要移动 2ⁿ - 1 次。

public class Hanoi {
    public static void move(int n, String from, String buffer, String to) {
        if (n == 1) {
            System.out.println("from " + from + " to " + to);
            return;
        }
        move(n - 1, from, to, buffer);
        move(1, from, buffer, to);
        move(n - 1, buffer, from, to);
    }
 
    public static void main(String[] args) {
        Hanoi.move(3, "H1", "H2", "H3");
    }
}

from H1 to H3
from H1 to H2
from H3 to H2
from H1 to H3
from H2 to H1
from H2 to H3
from H1 to H3

哈夫曼编码

根据数据出现的频率对数据进行编码，从而压缩原始数据。

例如对于一个文本文件，其中各种字符出现的次数如下：

• a : 10
• b : 20
• c : 40
• d : 80

可以将每种字符转换成二进制编码，例如将 a 转换为 00，b 转换为 01，c 转换为 10，d 转换为 11。这是最简单的一种编码方式，没有考虑各个字符的权值（出现频率）。而哈夫曼编码采用了贪心策略，使出现频率最高的字符的编码最短，从而保证整体的编码长度最短。

首先生成一颗哈夫曼树，每次生成过程中选取频率



前言

符号表（Symbol Table）是一种存储键值对的数据结构，可以支持快速查找操作。

符号表分为有序和无序两种，有序符号表主要指支持 min()、max() 等根据键的大小关系来实现的操作。

有序符号表的键需要实现 Comparable 接口。

public interface UnorderedST<Key, Value> {
 
    int size();
 
    Value get(Key key);
 
    void put(Key key, Value value);
 
    void delete(Key key);
}

public interface OrderedST<Key extends Comparable<Key>, Value> {
 
    int size();
 
    void put(Key key, Value value);
 
    Value get(Key key);
 
    Key min();
 
    Key max();
 
    int rank(Key key);
 
    List<Key> keys(Key l, Key h);
}

初级实现

1. 链表实现无序符号表

public class ListUnorderedST<Key, Value> implements UnorderedST<Key, Value> {
 
    private Node first;
 
    private class Node {
        Key key;
        Value value;
        Node next;
 
        Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
 
    @Override
    public int size() {
        int cnt = 0;
        Node cur = first;
        while (cur != null) {
            cnt++;

栈

public interface MyStack<Item> extends Iterable<Item> {
 
    MyStack<Item> push(Item item);
 
    Item pop() throws Exception;
 
    boolean isEmpty();
 
    int size();
 
}

1. 数组实现

public clas

前言

用于解决动态连通性问题，能动态连接两个点，并且判断两个点是否连通。

约定

待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。

使用辅助函数 less() 和 swap() 来进行比较和交换的操作，使得代码的可读性和可移植性更好。

排序算法的成本模型是比较和交换的次数。

public abstract class Sort<T extends Comparable<