"绿色"树是不可变的,持久的,没有父引用,是"自下而上"构建的,并且每个节点都跟踪其宽度而不是其绝对位置.当编辑发生时,我们只重建受编辑影响的绿树部分,这通常是树中总解析节点的O(log n).
"红色"树是一个不变的立面,围绕绿树建造; 它根据需要"自上而下"构建,并在每次编辑时丢弃.它通过在从顶部向下穿过树时按需制造它们来计算父引用.它通过从宽度计算它们来制造绝对位置,同样,当你下降时.
你,Roslyn API的消费者,只看到红树; 绿树是一个实现细节.(如果你使用调试器来查看解析节点的内部状态,你实际上会看到存在对另一个不同类型的解析节点的引用;那就是绿树节点.)
顺便提一下,这些被称为"红/绿树",因为它们是我们在设计会议中用于绘制数据结构的白板标记颜色.颜色没有其他意义.