The rope data structure, redundancy on wikipedia or am I missing something?
-
24-06-2021 - |
Question
Why are there duplicate nodes like 9
, 1
and 6
in the wikipedia article on rope?
Am I missing something, or those nodes are fully redundant?
Solution
they (the non-leaf nodes with single children) seem completely pointless. there doesn't seem to be anything in the linked to paper from boehm et al that is equivalent (there they use "normal" balanced trees).
they make no sense to me.
OTHER TIPS
From the article:
Each node has a "weight" equal to the length of its string plus the sum of all the weights in its left subtree.
Those numbers appear to represent a weight of the node, based on the size of its children. So two nodes with value 6
do not have to have the same values. There is a Hello_
of weight 6 and a _Simon
of weight 6.
Edit
For non-leaf values, the duplicates appear to be there to make the leaves at the same depth.
Those nodes could come about after a delete. Eventually you would want to rebalance so every node has two children (or a leaf) and the depth of each branch would be the same.