An implementation of range lists for YAP¶

range list trees

Node Each node (non leaf) uses 8 bits.

• 8 bits are used to represent the state of the 4 subtrees ( subranges ).

• 2 bits are used to represent the state for each subtreee

States of a subtree: 00 (0) - range not in interval 11 (3)- all range in interval 10 (2)- range parcially in interval

An extra byte is used to keep the number of nodes in the subtrees.