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
--
http://mail.python.org/mailman/listinfo/python-list
