一棵关于树节点变色的问题，欢迎感兴趣的大佬们讨论

[baptismOfTime]

• 有许多颗不断生长的树 千万级结点，百级的深度

• 某些结点会自身变色导致其子孙节点受影响变为相同的颜色 如 Node2_2 、Node3_2 自身变色 导致其子孙全部跟随变色

• 受父结点影响已经变色过的子孙节点有可能会再度变色，如 Node4_2

• 节点也有可能失色 如 Node2_2 、Node4_2 失色后恢复其原本或继承自上级的颜色

• 请教一下大家，有什么方案能在快速查询节点颜色的基础上，对变色和失色也有较好的性能

原谅我没表达清楚，这些节点和颜色属性要持久化保存并支持事务级别(可以非强一致性)的变色&失色操作

[seawing]

树配一个 hash 表？

[MoYi123]

可以参考 线段树的懒标记 的做法

[zhy0216]

没什么好优化的吧 本来这个查询就只有 log （ n ）的复杂度

[tool2d]

可以考虑多根节点。比如 Node3_2 有两个父节点，即属于 Node2_1 ，又属于红色节点。

[JasonLaw]

我觉得你应该说明“不同操作发生的次数”，这会影响最佳方案。

[baptismOfTime]

感谢各位回复，千万级别的节点 需要持久化各个节点的颜色和位置属性，查询操作大概有 3-4k 的 qps ，变色和失色频率比较低，tps 在 20 以内

[baptismOfTime]

棘手的地方在于每次变色和失色要考虑到向根 /子级追溯十几个层级、几万个节点的数据；有没有熟悉 neo4j 的大佬，请教一下在这种场景里把颜色当做边，节点当顶点，查询节点颜色实现为用边查询受关联影响的直接顶点属性，但是节点变色和失色的场景下会进行大量的边修改 这个理论上能否可行？

[airwalkers]

节点配一个时间戳，查询节点到跟路径上最新时间戳的颜色

[zhy0216]

想到一个 O （ log K ） 的办法 K 是节点上有颜色的 node
首先构造 id, id 是这个树在这一层的排序的 index 每多一层 加一个“-” 区分
比如 root 节点是 0
Node2_1 是 0-1

然后用字典树把这个每一层的 id 和颜色记录下来
当查询一个新的 node 的时候 就是查询字典树中的值 （最大前缀）

[Maboroshii]

给每个节点加一个日志，记录主动变色的历史。 子节点递归查找父节点的日志。 子节点的变色时间在父节点变色时间之前，那么和父节点同色，否则保持自己的颜色？

[wlsnx]

用一个 hash 表存到节点的指针，这样就可以快速找到这个节点，然后只有两种情况：节点本身有颜色，返回这个颜色；节点没颜色，向上找第一个有颜色的父节点。增加、删除、移动节点时要同步更新 hash 表。

[Nazz]

更新的时候只更新本节点颜色，记录下操作序列号(单调递增); 获取节点颜色需要递归到根节点，取最大序列号节点的颜色. 更新 O(1), 查找 O(logN)

[robbaa]

其实，主要是无限层级遍历问题。
分享 2 个方案，一个是看来的，另外一个算是改进，好不好不好说。

方案一：
每个节点 4 个属性：
id：编号
name：名称
parent：父节点编号
left：左子节点排序编号
right：右边子节点排序编号

1. 先构建树
2. 然后按照，先序遍历对每个节点的 left 、right 设值，每次加 1.

[robbaa]

大致如下：
root: 0,25
node2_1:1,18
node3_1:2,3
node3_2:4,15
node4_1:5,8
node5_1:6,7
ndoe4_2:9,14
node5_2:10,11
node5_3:12,13
node3_3:16,17
node2_2:19,22
node3_4:20,21
node2_3:23,24

需求 1：查询某节点下所有节点
select * from nodes where left > {left} and right < {right}

需求 2：查询某元素上级节点
select * from nodes where left < {left} and right > {right} order by left ASC

缺陷代价：
元素的添加与删除，都会导致大量 left 、right 值的更新。

[robbaa]

方案二：
基于方案一改良，把 left 和 right 的值换成 float 或 double ，不再递增只保证数值增加的。
新增元素，用两侧兄弟元素 right(leftNodeRight)与 left(rightNodeLeft)的值去计算新节点的 left 、right 。
left=(rightNodeLeft-leftNodeRight)/4+leftNodeRight
right=rightNodeLeft - (rightNodeLeft-leftNodeRight)/4

计算公式不一定，只要能保证有“足够空间”都可以，定时做好“空间”回收就行。

[aragakiyuii]

左右值

[xiangyuecn]

你看到的不一定是真的

所以，完全可以作假，前端视觉欺骗，点一下搞个几秒的动画

比如转个 5 秒的圈，夸张点，几百万人同时操作，都在那转圈迷惑一下，服务器将变更收集起来，几秒内只实际计算更新一次，随便搞

[CapNemo]

1. 删除颜色操作可以视为染成父节点颜色
2. 指定合适的遍历顺序时，树可以用数组表示
3. 因此应当搜索区间染色问题

[CapNemo]

@CapNemo 建议使用动态开点线段树