Red Black Tree implementation?
duncan smith
buzzard at invalid.invalid
Sat May 11 21:34:32 EDT 2013
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
More information about the Python-list
mailing list