Rope data structure explanation?

Question

I was reading about the rope data structure on wikipedia and I was a little confused about the description.

Wiki link: http://en.wikipedia.org/wiki/Rope_(data_structure)

Description

A rope is a binary tree having leaf nodes that contain a short string.

Each node has a weight value equal to the length of its string plus the sum of all leaf nodes' weight in its left subtree, namely the weight of a node is the total string length in its left subtree for a non-leaf node, or the string length of itself for a leaf node.

Thus a node with two children divides the whole string into two parts: the left subtree stores the first part of the string. The right subtree stores the second part and its weight is the sum of the left child's weight and the length of its contained string.

The picture below is one of the examples from wikipedia.

.

I'm having trouble seeing where the numbers in the picture above are coming from.

Each node has a weight value equal to the length of its string plus the sum of all leaf nodes' weight in its left subtree

• C = 6 + 0 (E + C's empty string's length )?
• B = 6 + 3 + 0 + 0 (E + F + C's empty string's length + B's empty String length )?
• That can't be right, Why is A 22? (6+6+9 = 21? 6+6+3+9 = 24?)

I'm pretty sure I've missed something. Can someone help clear it up for me?

Thanks.

Answer 1

Each node has a weight value equal to the length of its string plus the sum of all leaf nodes' weight in its left subtree...

A has no right subtree so its value is the sum of the weights of all the leaf nodes (even if A had a right subtree its value would be the same): 6+3+2+4+1+6=22

B has two leaves in its left subtree: 6+3=9

C has one leaf in its left subtree: 6