专栏首页自学笔记Data Structure_树线段树Segment Tree红黑树

Data Structure_树线段树Segment Tree红黑树

线段树Segment Tree

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

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

使用数组实现

使用线段树实现

更新

查询

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

,那么就需要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();
    }

查找最大值。

红黑树

树的平衡

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

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

红黑树的特征

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

红黑树的规则

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

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

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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Data Structure_树

    对于有一类问题,时常关注的是一个区间或者是一个线段,那么就可以使用线段树来解决。比较经典的问题,就是区间染色问题:有一面墙,长度为n,每次选择一段墙来染色,一开...

    西红柿炒鸡蛋
  • Data Structure前情提要——二叉树红黑树

    叶子节点就是左右孩子都是空的,但是并不是每一颗树都像上图所示的那样这么规整,有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值,...

    西红柿炒鸡蛋
  • Astar Algorithm

    参考文献:https://www.gamedev.net/reference/articles/article2003.asp 这篇东西写的贼好。

    西红柿炒鸡蛋
  • javascript入门笔记9-认识DOM

    认识DOM 文档对象模型DOM(Document Object Model)定义访问和处理HTML文档的标准方法。DOM 将HTML文档呈现为带有元素、属性和...

    方志朋
  • 简述 zookeeper 基于 Zab 协议实现选主及事务提交

    Zab 协议:zookeeper 基于 Paxos 协议的改进协议 zookeeper atomic broadcast 原子广播协议。

    WindWant
  • 「容器架构」 K8s 集群如何规划工作节点的大小?

    欢迎来到小巧的Kubernetes学习——一个定期的专栏,讨论我们在网上看到的最有趣的问题,以及Kubernetes专家在我们的研讨会上回答的问题。

    首席架构师智库
  • 最强大的GNN出现了!

    论文:https://arxiv.org/pdf/2009.00142.pdf 代码:https://github.com/snap-stanford/dist...

    Houye
  • Redis Cluster执行流程

    集群(cluster)是Redis提供的分布式数据库解决方案,集群通过分片(sharding)来进行数据共享,并提供数据复制(replication)和故障转移...

    张申傲
  • 小白初识Zookeeper

    首先,了解一个Zookeeper是什么,其是一个开源的分布式协调服务,分布式数据一致性的解决方案。

    Liusy

扫码关注云+社区

领取腾讯云代金券