为什么遍历线段树的最大边界是date.length - 1呢

Question

为什么遍历线段树的最大边界是date.length - 1呢，而不是 date.length * 2 - 1 或者tree.length - 1 呢，不是应该是遍历tree这个数组吗

Answer 1

提问者 机电渣渣 2019-03-18 21:00:16

我好像懂了，其实这个是由于树这个结构导致的，遍历树只是需要遍历它的层数就好了，而数的层数是初始化数据的大小 - 1，所以遍历的是最大边界只需要data.length - 1

• 提问者 机电渣渣 #1

  额。。。想了想感觉还是不太懂

• 提问者 机电渣渣 #2

  我又有新的想法了，我之前纠结于这个data.length-1的原因是我还是用for循环的思维思考递归，总是想到第一个节点存什么第二个节点存什么，用递归的思维的话应该关注的是父节点子节点他们所代表的含义是什么，由于存的时候是整个data作为父节点，子节点为父节点区域的一半，那么应该data.length-1就是父节点的区域了，子节点就根据父节点的区域划分进行再查询这个是递归操作，是否找到节点是根据节点代表的左右区域边界是否于查询的左右区域相等这个是递归到底了

• liuyubobobo 回复 提问者 机电渣渣 #3

  大赞！你最后的这一段回复，我认为你已经完全理解了：）如果觉得自己理解的还不够“透彻”，以一个小样本为例，[1, 2, 3, 4]作为数据就可以，实际到代码里跟踪一下？看看这样的一个数组，建立出的线段树是什么样子的？tree数组是怎样的。进行一个具体查询，看看是怎样的过程？把date.length - 1改成你认为正确的数（date.length * 2 - 1 或者tree.length - 1 ），看看会发生什么？结果是不是依然正确？如果不正确，单步跟踪，看看哪里出了错误？为什么？再回过头比较一下课程的代码，理解一下我们为什么这么写？学习算法和数据结构，“想”通其中的逻辑固然重要，但很多时候，使用调试跟踪的方式，彻底理解程序每一步都再怎么执行，可能是想通具体逻辑的前提。同时，对编程能力，逻辑思维能力的提高，也发生在这个过程中哦：）加油！