You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Today, Rowan's logical tree shape is identical to the physical shape of the tree data structure. That's natural (you might even wonder what is the other option), but is not necessary optimal. In particular, natural tree sometimes have very wide nodes with hundreds of children. Traversing or modifying such nodes sometimes is O(len(children)), which might give poor worst-case complexity.
An alternative is to make sure that the physical shape of the data structure is always a ballaned tree. For example, we can introduce a TRANSPARENTSyntaxKind, and represent long sequences as deep, balanced trees with TRANSPARENT internal nodes.
The text was updated successfully, but these errors were encountered:
Today, Rowan's logical tree shape is identical to the physical shape of the tree data structure. That's natural (you might even wonder what is the other option), but is not necessary optimal. In particular, natural tree sometimes have very wide nodes with hundreds of children. Traversing or modifying such nodes sometimes is
O(len(children))
, which might give poor worst-case complexity.An alternative is to make sure that the physical shape of the data structure is always a ballaned tree. For example, we can introduce a
TRANSPARENT
SyntaxKind
, and represent long sequences as deep, balanced trees withTRANSPARENT
internal nodes.The text was updated successfully, but these errors were encountered: