Data Structure_树线段树Segment Tree红黑树

线段树Segment Tree

对于有一类问题，时常关注的是一个区间或者是一个线段，那么就可以使用线段树来解决。比较经典的问题，就是区间染色问题：有一面墙，长度为n，每次选择一段墙来染色，一开始4-6绘制成黄色，然后1-10绘制蓝色，2-7绘制红色，若干次绘色之后能看见多少种颜色，或者是在区间「i，j」区间里面可以看到多少种颜色。所以主要有两个操作，染色操作和查询操作。使用数组操作其实是可以的，染色就只需要把对应下标的内容，修改就好了；查找只需要遍历，这样复杂度就都是

O(n)

，这样很明显效率是不够的。 实质的应用就是区间查询，比如统计2017年的消费最高的用户，或者是某一个太空区间天体的总量。使用线段树的之后：

线段树大致的样子。可以看到线段树不是完全二叉树，因为如果是十个元素，是不一定都集中在左边的，这时候就不一定是完全二叉树了，但是一定是平衡二叉树。平衡二叉树的定义是，最短深度和最大深度的差只能为1，也就是不能超过1。虽然不是完全二叉树，但是依然可以用数组来表示，将下面的空节点全部补全，这样这棵树就变成满二叉树了。如果区间有n个元素，而

n = 2^k

，那么就需要2n个空间来存储。如果不是，那么就需要4n个，因为多出的那一个需要一整行取填补它。

Create

创建线段树其实很简单，可以看到上面是对半分开。

    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

求左右子树的下标。

public class SegmentTree<E> {
    private E[] data;
    private E[] tree;
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger<E> merger) {
        this.merger = merger;
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }

        tree = (E[]) new Object[4 * arr.length];
        buildSegmentTree(0, 0, data.length - 1);
    }

data是传进来的数据，tree是树的数据merger是操作。还是递归，因为树这种数据结构用起递归是天然的方便。参数要有两个主要的参数，左边和右边的边界，其实按照上面的图就是中分。当l >= r的时候就是递归的最终条件，这个时候直接相等即可，否则就递归构建。

    private void buildSegmentTree(int treeIndex, int l, int r) {
        if (l >= r) {
            tree[treeIndex] = data[l];
            return;
        } else {
            int leftTreeIndex = leftChild(treeIndex);
            int rightTreeIndex = rightChild(treeIndex);
            int mid = l + (r - l) / 2;
            buildSegmentTree(leftTreeIndex, l, mid);
            buildSegmentTree(rightTreeIndex, mid + 1, r);
            tree[treeIndex] = merger.merger(tree[leftTreeIndex], tree[rightTreeIndex]);
        }
    }

merger是一个接口，这是因为如果把这个功能写死了，那么线段树的功能就死了。比如求和，如果写死了那么这个树就只能求和。而如果加上了接口，最小值最大值也是可以的。线段树其实也是一种空间换时间的做法。

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(arr, (a, b) -> a > b?a:b);
        segmentTree.show();
    }

查找最大值。

红黑树

树的平衡

树的平衡是指树的每一个节点的左右子节点的数目大致一样。两边都相等是最好的，当然这种情况很少见，一般都是两边大致相等。比如在二叉搜索树的时候，如果插入的数字是有顺序的，那么就容易退化成极其不平衡的链表，搜索复杂度就会变成

O(n)

了。所以对于插入顺序不是平衡的时候，之前所学过的二叉树就不再是一种好的数据结构了。这个时候就要使用红黑树了，红黑树其实也是一种二叉树，只不过是增加了某种特性的二叉树。如果在插入或删除的时候如果出现了不平衡的状态，那么就要进行调整，保持树的平衡。

红黑树的特征

首先每一个节点都有颜色，在删除和添加的过程中是需要保持这些颜色的排列规律。

红黑树的规则

1.每一个节点不是红色就是黑色。 2.根节点总是黑色。 3.如果节点是红色，那么子节点一定是黑色。但是黑色节点下面的子节点可以是红色也可以是黑色。 4.空子节点一定是黑色。对于空子节点而言，本来可能有，但是实际没有的那个字节点就叫做空子节点，比如一个节点只有右子节点，左子节点是没有的，但是左子节点是可以存在的，那么空的这个左子节点就是空子节点。 5.从根到叶节点或者空子节点的没条路径，必须包含相同数目的黑色节点。

红黑树的修正手段也就几种，首先就是改变颜色了，然后就是执行旋转操作。

旋转其实也很容易理解，左旋转的时候，beta这个节点接上了x没有位置放了，所以只能接在x上，右旋转也是一样的意思。所以红黑树的插入算法就需要做出改变，插入的时候前面的步骤是一样的，从根节点向下查找要插入的位置，插入节点之后，后面就需要添加检测树的操作，检测这个树是否是红黑树了，如果不是，那么就要进行修正。一开始插入的这个节点，通常会把它设置成红色，因为这样违法的概率会低一点。 1.如果插入的节点是根节点，那么违法规则2，直接把节点修改成黑色。 2.如果插入的节点父节点是黑色，那么符合，什么都不用做。 3.如果插入的节点的父节点是红色的，而且祖父节点的另一个节点也是红色的，那么就要把祖父节点变红，父节点和叔节点变黑，然后设置祖父节点为当前节点重新开始判断。

这样做的原因其实很简单。首新节点和父节点都是红色，这个时候的常规操作就是要把当前节点变成红色，因为如果节点是黑色的，那么子节点一定要是红色的。但是如果变成黑色的了，那么这边就会多出黑色的一个，这就违法了相同数目的黑色节点的原则了。所以正确的操作应该是要么两边不加，要么两边加，很明显这里只能两边加了，因为添加的节点和父节点是一定要有一个要加的。

4.如果插入的父节点是红色，叔叔节点是黑色，