golang二叉树遍历_2021年9月编程语言

golang二叉树遍历_2021年9月编程语言usingMicrosoft.AspNetCore.Builder;usingMicrosoft.Extensions.DependencyInjection;usingMicrosoft.Extensions.Hosting;usingMicrosoft.OpenApi.Models;usingVolo.Abp;usingVolo.Abp.AspNetCore.Mvc;usingVolo.Abp.Autofac;usingVolo.Abp.Modularity;using

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

/// <summary>
/// 线段树:线段树是二叉树的一种,常常被用于求区间和与区间最大值等操作
/// </summary>
public class SegmentTree
{ 

List<int> _orignalData = new List<int>();
List<int?> _tree = new List<int?>();
public SegmentTree()
{ 

for (int i = 0; i < 1000; i++)
{ 

_tree.Add(null);
}
}
public void Print()
{ 

for (int i = 0; i < _tree.Count; i++)
{ 

if (_tree[i] == null)
{ 

continue;
}
Console.WriteLine($"第{ 
i}:{ 
_tree[i]}");
}
}
public void Fill(List<int> data)
{ 

_orignalData = data;
Fill(0, 0, _orignalData.Count - 1);
}
private void Fill(int node, int start, int end)
{ 

if (start == end)
{ 

_tree[node] = _orignalData[start];
}
else
{ 

int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
Fill(leftNode, start, mid);
Fill(rightNode, mid + 1, end);
_tree[node] = _tree[leftNode] + _tree[rightNode];
}
}
public void Set(int index, int val)
{ 

SetValue(0, 0, _orignalData.Count - 1, index, val);
}
private void SetValue(int node, int start, int end, int index, int val)
{ 

if (start == end)
{ 

_orignalData[index] = val;
_tree[node] = val;
}
else
{ 

int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
if (index >= start && index <= mid)
{ 

SetValue(leftNode, start, mid, index, val);
}
else
{ 

SetValue(rightNode, mid + 1, end, index, val);
}
_tree[node] = _tree[leftNode] + _tree[rightNode];
}
}
public int? GetSum(int left, int right)
{ 

return Query(0, 0, _orignalData.Count - 1, left, right);
}
private int? Query(int node, int start, int end, int left, int right)
{ 

if (right < start || left > end)
{ 

return 0;
}
else if (left <= start && end <= right)
{ 

return _tree[node];
}
else if (start == end)
{ 

return _tree[node];
}
else
{ 

int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
int? sumLeft = Query(leftNode, start, mid, left, right);
int? sumRight = Query(rightNode, mid + 1, end, left, right);
return sumLeft + sumRight;
}
}
}

原理

(注:由于线段树的每个节点代表一个区间,以下叙述中不区分节点和区间,只是根据语境需要,选择合适的词)
线段树本质上是维护下标为1,2,…,n的n个按顺序排列的数的信息,所以,其实是“点树”,是维护n的点的信息,至于每个点的数据的含义可以有很多,
在对线段操作的线段树中,每个点代表一条线段,在用线段树维护数列信息的时候,每个点代表一个数,但本质上都是每个点代表一个数。以下,在讨论线段树的时候,区间[L,R]指的是下标从L到R的这(R-L+1)个数,而不是指一条连续的线段。只是有时候这些数代表实际上一条线段的统计结果而已。

线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法,即对结果下取整)直到 L==R 为止。
开始时是区间[1,n] ,通过递归来逐步分解,假设根的高度为1的话,树的最大高度为(n>1)。
线段树对于每个n的分解是唯一的,所以n相同的线段树结构相同,这也是实现可持久化线段树的基础。
下图展示了区间[1,13]的分解过程:
在这里插入图片描述
上图中,每个区间都是一个节点,每个节点存自己对应的区间的统计信息。

(1)线段树的点修改:

假设要修改[5]的值,可以发现,每层只有一个节点包含[5],所以修改了[5]之后,只需要每层更新一个节点就可以线段树每个节点的信息都是正确的,所以修改次数的最大值为层数。
复杂度O(log2(n))

(2)线段树的区间查询:

线段树能快速进行区间查询的基础是下面的定理:
定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。
这样,在查询[L,R]的统计值的时候,只需要访问不超过个节点,就可以获得[L,R]的统计信息,实现了O(log2(n))的区间查询。

下面给出证明:

(2.1)先给出一个粗略的证明(结合下图):
先考虑树的最下层,将所有在区间[L,R]内的点选中,然后,若相邻的点的直接父节点是同一个,那么就用这个父节点代替这两个节点(父节点在上一层)。这样操作之后,本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树,那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树,那么这个节点会被剩下。中间的所有节点都被父节点取代。
对最下层处理完之后,考虑它的上一层,继续进行同样的处理,可以发现,每一层最多留下2个节点,其余的节点升往上一层,这样可以说明分割成的区间(节点)个数是大概是树高的两倍左右。

下图为n=13的线段树,区间[2,12],按照上面的叙述进行操作的过程图:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
由图可以看出:在n=13的线段树中,[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。

(2.2)然后给出正式一点的证明:
定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。

用数学归纳法,证明上面的定理:
首先,n=3,4,5时,用穷举法不难证明定理成立。
假设对于n= 3,4,5,…,k-1上式都成立,下面来证明对于n=k ( k>=6 )成立:
分为4种情况来证明:

情况一:[L,R]包含根节点(L=1且R=n),此时,[L,R]被分解为了一个节点,定理成立。

情况二:[L,R]包含根节点的左子节点,此时[L,R]一定不包含根的右子节点(因为如果包含,就可以合并左右子节点,
用根节点替代,此时就是情况一)。这时,以右子节点为根的这个树的元素个数为。
[L,R]分成的子区间由两部分组成:
一:根的左子结点,区间数为1
二:以根的右子节点为根的树中,进行区间查询,这个可以递归使用本定理。
由归纳假设可得,[L,R]一共被分成了个区间。
情况三:跟情况二对称,不一样的是,以根的左子节点为根的树的元素个数为。
[L,R]一共被分成了个区间。
从公式可以看出,情况二的区间数小于等于情况三的区间数,于是只需要证明情况三的区间数符合条件就行了。

于是,情况二和情况三定理成立。

情况四:[L,R]不包括根节点以及根节点的左右子节点。
于是,剩下的层,每层最多两个节点(参考粗略证明中的内容)。
于是[L,R]最多被分解成了个区间,定理成立。

上面只证明了是上界,但是,其实它是最小上界。
n=3,4时,有很多组区间的分解可以达到最小上界。
当n>4时,当且仅当n=2^t (t>=3),L=2,R=2^t -1 时,区间[L,R]的分解可以达到最小上界。
就不证明了,有兴趣可以自己去证明。
下图是n=16 , L=2 , R=15 时的操作图,此图展示了达到最小上界的树的结构。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
(3)线段树的区间修改:
线段树的区间修改也是将区间分成子区间,但是要加一个标记,称作懒惰标记。
标记的含义:
本节点的统计信息已经根据标记更新过了,但是本节点的子节点仍需要进行更新。
即,如果要给一个区间的所有值都加上1,那么,实际上并没有给这个区间的所有值都加上1,而是打个标记,记下来,这个节点所包含的区间需要加1.打上标记后,要根据标记更新本节点的统计信息,比如,如果本节点维护的是区间和,而本节点包含5个数,那么,打上+1的标记之后,要给本节点维护的和+5。这是向下延迟修改,但是向上显示的信息是修改以后的信息,所以查询的时候可以得到正确的结果。有的标记之间会相互影响,所以比较简单的做法是,每递归到一个区间,首先下推标记(若本节点有标记,就下推标记),然后再打上新的标记,这样仍然每个区间操作的复杂度是O(log2(n))。

标记有相对标记和绝对标记之分:
相对标记是将区间的所有数+a之类的操作,标记之间可以共存,跟打标记的顺序无关(跟顺序无关才是重点)。
所以,可以在区间修改的时候不下推标记,留到查询的时候再下推。
注意:如果区间修改时不下推标记,那么PushUp函数中,必须考虑本节点的标记。
而如果所有操作都下推标记,那么PushUp函数可以不考虑本节点的标记,因为本节点的标记一定已经被下推了(也就是对本节点无效了)
绝对标记是将区间的所有数变成a之类的操作,打标记的顺序直接影响结果,
所以这种标记在区间修改的时候必须下推旧标记,不然会出错。

注意,有多个标记的时候,标记下推的顺序也很重要,错误的下推顺序可能会导致错误。

之所以要区分两种标记,是因为非递归线段树只能维护相对标记。
因为非递归线段树是自底向上直接修改分成的每个子区间,所以根本做不到在区间修改的时候下推标记。
非递归线段树一般不下推标记,而是自下而上求答案的过程中,根据标记更新答案。

(4)线段树的存储结构:
线段树是用数组来模拟树形结构,对于每一个节点R ,左子节点为 2R (一般写作R<<1)右子节点为 2R+1(一般写作R<<1|1)
然后以1为根节点,所以,整体的统计信息是存在节点1中的。
这么表示的原因看下图就很明白了,左子树的节点标号都是根节点的两倍,右子树的节点标号都是左子树+1:
在这里插入图片描述
线段树需要的数组元素个数是:,一般都开4倍空间,比如: int A[n<<2];

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/178377.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 内网IP段有哪些_为什么有些内网使用公网地址段

    内网IP段有哪些_为什么有些内网使用公网地址段常见的内网IP段有:10.0.0.0/810.0.0.0-10.255.255.255172.16.0.0/12172.16.0.0-172.31.255.255192.168.0.0/16192.168.0.0-192.168.255.255以上三个网段分别属于A、B、C三类IP地址,来自《RFC1918》。但是根据《ReservedIPaddresses-Wikipedia,thefreeencyclopedia》及《RFC6890-Special

  • VS2008序列号[通俗易懂]

    VS2008序列号[通俗易懂]VS2008.NET简体中文版序列号1.VisualStudio2008ProfessionalEdition:XMQ2Y-4T3V6-XJ48Y-D3K2V-6C4WT2.Visual

  • 上海电信光猫SA1456C桥接后4K IPTV继续使用[通俗易懂]

    上海电信光猫SA1456C桥接后4K IPTV继续使用[通俗易懂]上海电信光猫SA1456C路由器TL-R488GPM-AC背景:打电话给上海电信客服被告知,改桥接不能看4KIPTV,电信安装师傅也是同一口径。网上也是很多类似观点,解决方案是用软路由方式去改造。这种方案需要软路由,万一不稳定,会影响家庭安定团结的局面。需求:1、光猫直接接IPTV看,有两条IPTV接路由器即可,不需要更改任何东西。2、光猫桥接路由器,路由器宽带拨号,保证贤妻上网和IPTV的基本需求,再接旁路由满足自己小玩法。当然如有移动或联通送的宽带更好。核心:稳定简单,不折腾。如何光

  • Makefile 语法入门

    Makefile 语法入门一、Makefile简介Makefile是一种常用于编译的脚本语言。它可以更好更方便的管理你的项目的代码编译,节约编译时间(没改动的文件不编译)。注意Makefile文件命令必须是Makefile或者makefile,并使用make命令编译。 二、1个规则1.语法规则目标…:依赖…命令1命令2…2.目标…

  • 简述pki的体系结构_如何整理知识点

    简述pki的体系结构_如何整理知识点 

  • 浅谈辄止_java forkjoinpool

    浅谈辄止_java forkjoinpool文章目录一、ForkJoin是什么?它能用来实现什么功能?二、ForkJoin的实现原理三、ForkJoin的简单使用一、ForkJoin是什么?它能用来实现什么功能?二、ForkJoin的实现原理三、ForkJoin的简单使用在这里插入代码片…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号