3 ms·
I would guess a G-tree is still a B-tree with additional parent pointers, the fact that it is stored in an array is a matter of representation but does not fund
by danbruc 3y ago
I would guess a G-tree is still a B-tree with additional parent pointers, the fact that it is stored in an array is a matter of representation but does not fundamentally change the structure. This still stores pointers, they are just in units of the node size instead of bytes and relative to the first array element instead of the beginning of the address space. A complete binary tree stored in a array without any explicit references, i.e. an implicit representation with the children of the node at index x stored at indices 2x + 1 and 2x + 2, is still referred to as a binary tree, just with an implicit representation.
- dgb23 3y agoIt’s useful to talk about representation though. Especially in a language that nudges you away from absolute references towards relative, self managed ones. A quite clever representation of a tree that I read about is to store nodes in DFS order in a flat array. Given that it’s read only and the readers want to traverse it depth first anyway, this can be quite efficient. S-expressions and HTML come to mind.
- danbruc 3y agoMy point was not that it might not be important, just that you probably do not want to assign a new name to a data structure just because you use a different representation. If the implementation would have been in a different language, then adding parent pointers into the B-tree would have been less of a concern and the representation with an array would maybe never have come up. It would be weird to say that this CRDT is based on a B-Tree with parent pointers, unless you implement it in Rust, then it is based on a G-tree.