Red Black Tree implementation?

[duncan smith]

On 12/05/13 00:24, Dan Stromberg wrote:
>
> I'm afraid I'm having some trouble with the module.  I've checked it
> into my SVN at
> http://stromberg.dnsalias.org/svn/red-black-tree-mod/trunk/duncan
>
> I have two versions of your tests in there now - "t" is minimally
> changed, and test-red_black_tree_mod is pretty restructured to
> facilitate adding more tests later.  I get the same problem with either
> version of the tests.
>
> The problem I'm seeing is that the tree, when built from items, isn't
> looking quite right.  I inserted a print(tree) into the for loop, and
> I'm getting the following, where I expected the tree to grow by one
> element on each iteration:
>
> $ python t
> 6 False None None
> 6 False 3 None
> 6 False 3 15
> 6 False 3 15
> 6 False 3 11
> 6 False 3 11
> 6 False 3 11
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
> 11 False 6 15
>
> Thoughts?
>
> BTW, printing an empty tree seems to say "sentinel".  'not sure if that
> was intended.
>
> Thanks!
>

The leaf node has parent equal to None. All tree nodes have two 
children. One or both children may be sentinels, and a sentinel is 
signified by having both left and right (children) equal to None. So an 
empty tree is a sentinel node that is also root. So the string 
"sentinel" is expected (although possibly not the most sensible option).

For non-sentinel nodes the string is generated by,

return '%s %s %s' % (self.data, self.left.data, self.right.data)

for the BinaryTree class, and by

return '%s %s %s %s' % (self.data, self.is_red, self.left.data, 
self.right.data)

for the RedBlackTree class.


So what is being printed above is (in each case) the value contained in 
the root node, followed by its colour (True if red), and the values 
contained in the root node's left and right children.

The root node remains root, although it's value and its children (and 
their values) might change due to tree rotations.

It looks OK to me. The empty tree would print "sentinel". After adding 
the value 6 there is one tree node with sentinels as children (values 
equal to None). Adding 3 results in 3 being the value of the root's left 
child. It's right child is still a sentinel. Adding 15 results in that 
value being assigned to the right child. Adding 9 results in no change 
to the values in the root or its children. Adding 11 results in a tree 
rotation and 11 becomes the value in the right child of the root. At a 
later point a tree rotation results in the value of the root node being 
changed.

I haven't implemented a way of representing the structure of the whole 
red black tree. I would probably write some code to generate a dot file 
and use that to generate a png. But you could add something like,

print tree.height, tree.size, list(tree)

and get output like,

0 1 [6]
1 2 [3, 6]
1 3 [3, 6, 15]
2 4 [3, 6, 9, 15]
3 5 [3, 6, 9, 11, 15]
4 6 [3, 6, 9, 11, 12, 15]
4 7 [3, 6, 9, 11, 12, 15, 16]
5 8 [3, 6, 9, 11, 12, 14, 15, 16]
5 9 [3, 6, 9, 11, 12, 14, 15, 16, 17]
5 10 [3, 6, 7, 9, 11, 12, 14, 15, 16, 17]
5 11 [3, 6, 7, 9, 11, 12, 14, 15, 16, 17, 18]
5 12 [3, 5, 6, 7, 9, 11, 12, 14, 15, 16, 17, 18]
5 13 [3, 5, 6, 7, 8, 9, 11, 12, 14, 15, 16, 17, 18]
6 14 [3, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18]
6 15 [0, 3, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18]
6 16 [0, 2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18]
6 17 [0, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18]
6 18 [-1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18]
6 19 [-1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]


It doesn't give you the structure, but it does show that it seems to be 
growing reasonably. Cheers.

Duncan