数据结构与算法总结——树

关于树的一些概念

树叶：没有儿子的节点
兄弟：具有相同父亲的节点；类似还有祖父和孙子节点
深度：某节点的深度为树根到该节点的唯一路径的长度
层次：深度相同的节点在同一层中，深度值为层数
结点的度：结点拥有的子树的数目
树的度：树中结点的最大层次
树宽度：树的各层中节点数最多的一层的节点数为树的宽度
无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置
有序树：如果树中结点的各子树之间的次序是重要的, 不可以交换位置
森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林
二叉树：一种特殊的树，每个双亲的孩子数不超过2个（0个，1个或2个），提供对元素的高效访问。有左孩子和右孩子
退化树：树中只有一个叶子结点，每个非叶子结点只有一个孩子。一颗退化树等价于一个链表

二叉树

二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

性质

二叉树第i层上的结点数目最多为 2^i-1^ (i≥1)
深度为k的二叉树至多有2^k^-1个结点(k≥1)
包含n个结点的二叉树的高度至少为log₂(n+1)。
在任意一棵二叉树中，若终端结点的个数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

完全二叉树

一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。（叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部）

满二叉树

高度为h，并且由2^h^ –1个结点的二叉树，被称为满二叉树。

一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

应用

哈夫曼编码，构建哈夫曼树，用于数据压缩。
二叉搜索树，用于大量数据查询
平衡二叉树、红黑树，用于大量数据快速插入、删除、查询

二叉搜索树

二叉搜索树是一棵二叉树，其中每一个节点都含有一个可以对比（IComparable）的键，且每个节点的键都大于其左子树的任意节点的键，且小于右子树的任意节点的键。没有键相等的节点。

性质

二叉搜索树中序遍历打印出来的序列是顺序序列

实现

public class TreeNode<K, V>
{
    public K key;
    public V value;
    public TreeNode<K, V> left, right;
    public int N;

    public TreeNode(K key, V value, int n)
    {
        this.key = key;
        this.value = value;
        this.N = n;
    }
}

class BinarySearchTree<K, V> where K : IComparable
{
    private TreeNode<K, V> root;

    public int Count => Size(root);

    private int Size(TreeNode<K, V> node)
    {
        if (node == null)
            return 0;

        return node.N;
    }

    public V Get(K key)
    {
        if (root == null)
            throw new Exception("BinarySearchTree is null");

        return Get(root, key);
    }

    private V Get(TreeNode<K, V> node, K key)
    {
        if (node == null)
            return default(V);

        int compareResult = key.CompareTo(node.key);
        if (compareResult < 0)
            return Get(node.left, key);
        else if (compareResult > 0)
            return Get(node.right, key);
        else
            return node.value;
    }

    public void Set(K key, V value)
    {
        root = Set(root, key, value);
    }

    private TreeNode<K, V> Set(TreeNode<K, V> node, K key, V value)
    {
        if (node == null)//若当前结点为空，说明已递归到合适的地方，构建新节点并返回
            return new TreeNode<K, V>(key, value, 1);

        int compareResult = key.CompareTo(node.key);
        if (compareResult < 0)
            node.left = Set(node.left, key, value);//若目标键大于当前键，递归右子树
        else if (compareResult > 0)
            node.right = Set(node.right, key, value);//若目标键小于当前键，递归左子树
        else
            node.value = value;//若与当前节点键相等，更新value

        node.N = Size(node.left) + Size(node.right) + 1;//更新子树节点数

        return node;
    }

    public K MinKey()
    {
        if (root == null)
            throw new Exception("BinarySearchTree is null");

        return MinKey(root).key;
    }

    private TreeNode<K, V> MinKey(TreeNode<K, V> node)
    {
        if (node.left == null)
            return node;
        else
            return MinKey(node.left);
    }

    public K MaxKey()
    {
        if (root == null)
            throw new Exception("BinarySearchTree is null");

        return MaxKey(root).key;
    }

    private TreeNode<K, V> MaxKey(TreeNode<K, V> node)
    {
        if (node.right == null)
            return node;
        else
            return MaxKey(node.right);
    }

    public void DeleteMin()
    {
        root = DeleteMin(root);
    }

    private TreeNode<K, V> DeleteMin(TreeNode<K, V> node)
    {
        if (node.left == null)
            return node.right;

        node.left = DeleteMin(node.left);
        node.N = Size(node.left) + Size(node.right) + 1;

        return node;
    }

    public void DeleteMax()
    {
        root = DeleteMax(root);
    }

    private TreeNode<K, V> DeleteMax(TreeNode<K, V> node)
    {
        if (node.right == null)
            return node.left;

        node.right = DeleteMax(node.right);
        node.N = Size(node.left) + Size(node.right) + 1;
        return node;
    }

    public void Delete(K key)
    {
        root = Delete(root, key);
    }

    private TreeNode<K, V> Delete(TreeNode<K, V> node, K key)
    {
        if (node == null)//若为空，则树中没有目标节点
            return null;
        //递归找到要删除的节点，若当前节点键比目标键小，则递归左子树，否则递归右子树
        int compareResult = key.CompareTo(node.key);
        if (compareResult < 0)
            node.left = Delete(node.left, key);
        else if (compareResult > 0)
            node.right = Delete(node.right, key);
        else
        {
            //若当前节点只有一个子节点，直接返回该孩子节点
            //若当前节点没有子节点，返回空
            if (node.right == null) return node.left;
            if (node.left == null) return node.right;

            //若有两个节点，则用目标节点的后继节点（右子树中的最小节点）填补目标节点的位置
            TreeNode<K, V> t = node;
            node = MinKey(node.right);
            node.right = DeleteMin(t.right);
            node.left = t.left;
        }

        node.N = Size(node.left) + Size(node.right) + 1;
        return node;
    }
}

插入

如果当前节点为空，构建新节点返回
若新节点键比当前节点小，递归插入左子树
若新节点键比当前节点大，递归插入右子树

删除最小节点

向左子树递归，若遇到某个节点的左节点为空，则返回其右节点

删除最大值则反之

删除指定节点

删除指定节点是二叉搜索树最麻烦的一步操作，具体可以分为下面3中情况

对于没有子节点的节点，直接删除即可。
对于有一个子节点的，我们用类似上文删除最小节点的方法，返回非空子节点即可。
若要删除的节点有两个子节点，我们可以用它的后继节点填补他的位置

后继节点就是树中所有大于目标节点的值的最小值，也就是目标节点的右子树中的最小值。

删除过程中，我们先获取右子树的最小值，取代目标节点，然后在该右子树中删除该最小值，然后衔接上原节点的左子树，以及被删除了最小值的右子树。

时间复杂度

/	最坏	平均
查找	N	logN
插入	N	logN
删除	N	logN

平衡树

二叉搜索树在最坏情况下会退化为链表，这种情况下查找的时间复杂度会变成了O(N),为了解决这一问题，在插入操作时添加“平衡”的操作，防止树深度过深，具备平衡功能的树，我们成为平衡树，包括有AVL树、红黑树、B树等。

AVL树/平衡二叉搜索树

一颗AVL树（平衡二叉搜索树）是其每个节点的左子树和右子树的高度最多差1的二叉搜索树。

旋转

当我们向AVL树插入新节点时，可能会破坏AVL树的平衡要求，此时我们通过旋转来对树进行修正以符合左子树和右子树的高度最多差1的性质。

在新节点插入后，只有那些从插入点到根节点的路径上的节点的平衡可能被改变，因为只有这些节点的子树可能发生变化。我们需要在这条路径找到一个破坏了AVL树平衡条件且最深的节点，对它所在的子树进行调整，以重新平衡并满足AVL树的性质。

我们把上述的那个节点称为node，那么出现不平衡可能有以下四种情况：

对node的左儿子的左子树进行一次插入
对node的做儿子的右子树进行一次插入
对node的右儿子的左子树进行一次插入
对node的右儿子的右子树进行一次插入

实际上1和4，2和3是镜像对称的

我们可以把以上概括为两种情况

插入发生在外边的情况（左-左型和右-右型），这种情况只需要单次旋转即可完成调整，左-左型右旋，右-右型左旋
插入发生在内部的情况（左-右型和右-左型），这种情况需要双旋转来处理，右-左型先右旋再左旋，左-右型先左旋再右旋

参考：
https://mp.weixin.qq.com/s/dYP5-fM22BgM3viWg4V44A

应用

主要负责出现在教课书中（逃

2-3搜索树

为了保证搜索树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。确切地说，我们将一棵标准的二叉搜索树的节点称为2-节点（含有一个键和两条链接），而现在我们引入3-节点，它含有两个键和三条链接。2-节点和3-节点中的每条链接都对应着其中保存的键所分割产生的一个区间。

定义

一棵2-3搜索树或为一颗空树，或由以下节点组成：

2-节点，含有一个键和两条链接，左链接指向的子树中的键都小于该节点，右链接指向的子树中的键都大于该节点
3-节点，含有两个键和三条链接，左链接指向的子树中的键都小于该节点，右链接指向的子树中的键都大于该节点，中间链接指向的子树中的键位于该节点的两个键之间

查找

与二叉搜索树相似，判断目标与当前节点大小关系，若相等就返回，若不等则在对应的区间递归地继续查找，只不过对于3-节点，多了一个中间区间。

插入

2-3搜索树插入新节点时，先进行一次未命中查找，为了保持一定平衡，需要根据查找最后结束的情况来调整树。

向2-节点中插入新节点

若未命中查找结束于一个2-节点，我们只需要把这个节点替换成3-节点，把新键保存其中即可。

向一棵只有含有一个3-节点的树中插入新节点

先把新键临时存入到3-结束节点中，使其成为临时的4-节点，然后把他们拆分为3个2-节点组成的2-3树，其中大小适中的键成为父节点，最小的键成为左子节点，最大的键成为右子节点。

向一个父节点为2-节点的3-结束节点插入新节点

像上面向3-节点插入新节点一样，先成为临时的4-节点，但不会为中键创建新的节点，而是将其移动到父节点中，使父节点成为3-节点。

向一个父节点为3-节点的3-结束节点插入新节点

仍然是先向3-节点插入新节点一样，先成为临时的4-节点，然后在中键移动到父节点中，但父节点也是一个3-节点，那么我们一直重复此操作再向上推广，直到遇到一个2-节点，或者到达3-节点的根。

分解根节点

如果从插入节点到根节点的路径上全部都是3-节点，我们的根节点最终变成一个4-节点，此时我们可以按照向一棵只有含有一个3-节点的树中插入新节点的方法，把临时的4-节点分解成3个2-节点的树，使得树高加1。

和标准的二叉搜索树不一样，2-3树的生长是从下向上的

红黑树（《算法》第四版中 2-3树转换的左偏红黑树）

左偏红黑树的基本思想是用标准的二叉搜索树（完全由2-节点构成）和一些额外的信息（替换3-节点）来表示2-3树。

我们把树的链接分为两种类型：

红链接将两个2-节点连起来构成一个3-节点
黑链接就是2-3树中的普通链接

左偏红黑树性质

红链接均为左链接
没有任何一个节点同时和两条红链接相连
该树是完美黑色平衡的，即任何空链接到根节点的路径上的黑链接数量相同

满足这样定义的红黑树和相应的2-3树是一一对应的。

颜色表示

因为每个节点都只会有一条指向自己的链接，我们将链接的颜色保存在节点的数据类型中。当我们提到一个节点的颜色的时候，是指指向该节点链接的颜色。约定空链接为黑色。

插入

向单个2-节点中插入新节点

如果新键小于老键，我们只需要新增一个红色的节点即可，新的红黑树和单个3-节点完全等价
如果新建大于老键，那么新增的红色节点将会产生一条红色的右链接，需要将其进行左旋转并修正根节点链接

两种情况的结果均为一棵和单个3-节点等价的红黑树，其中含有两个键，一条红链接，树的黑链接高度为1。

向一棵双键树（一个3-节点）中插入新键

新键大于原树内两个键，新键会被链接到3-节点的右链接。其中根节点为中间大小的键，左节点为较小键，右结点为较大键，这事根节点（中间键）两边的链接均为红色，需要颜色转换都变成黑色。
如果新键小于原树中的两个键，会被链接到最左边的空链接，这个时候左侧会产生两条连续的红链接，我们需要把上层的红链接进行右旋转，得到左右侧都是红链接的树（与情况1相同），再进行颜色转换变成黑色。
如果新键处于原树中的两个键之间，这个时候会产生两条红链接，一条红色左链接接一条红色右链接，我们需要把下层的红链接进行左旋（得到情况2），再右旋得到情况1，再进行颜色转换变成黑色。

颜色转换

上述颜色转换中，一个根节点的左右链接均为红色，进行颜色转换后，左右链接变成黑色，而根节点变成红色。这项操作最重要的性质在于它和旋转操作一样是局部变换，不会影响整棵树的黑色平衡性。

根节点总是黑色

颜色转换后有可能使得整棵树的根节点变成红色，也就是根节点可能会成为一个3-节点，但实际情况并不是这样，因此我们需要在每次插入后把根节点设为黑色。每当根节点由红转黑时树的黑链接高度就会增加1。

向树的底部的3-节点插入新键，将红链接在树中向上传递

向树的底部的一个3-节点加入一个新节点，会出现上面讨论过的“向一棵双键树（一个3-节点）中插入新键”的3种情况，由于颜色转换最后会把根节点变成红色，这意味着向父节点插入了一个新的节点，我们需要通过左旋转、右旋转和颜色变换3个操作来让红链接在树中向上传递，知道遇到一个2-节点或者根节点。

总的来说：

如果右子结点是红色，而左子结点是黑色，则需要左旋转。
如果左子结点是红色和左子结点的左子结点也是红色，则进行右旋转。
如果左子结点和右子结点都是红色，进行颜色转换。

删除

删除最小键

从树底部的3-节点删除一个键很简单，但是2-节点则不然，因为从2-节点中删除一个键会留下一个空节点，则会破坏了树的完美黑平衡。为了保证我们不会删除一个2-节点，我们沿着左链接向下变换确保当前节点不是2-节点（可能是3-节点，也可能是临时的4-节点），沿着左链接向下的过程中，我们要保证：

当前结点的左子结点不是2-结点时，完成。
如果当前结点的左子结点是2-结点而它的亲兄弟结点不是2-结点，将左子结点的兄弟结点中的一个键移动到左子结点中。
如果当前结点的左子结点和它的亲兄弟结点都是2-结点，将左子结点、父结点总的最小键和左子结点最近的兄弟结点合成一个4-结点，使父结点由3-结点变成2-结点或者4-结点变成3-结点。

最后得到一个含有最小键的3-节点或临时的4-节点，然后我们就可以直接从中将其删除。然后我们再回头向上分解所有临时4-节点。