Welcome, guest | Sign In | My Account | Store | Cart

This is a module with pure Python implementations of binary and generalized (multi-node) trees.

Python, 749 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
"""
This module implements binary and generalized trees.

History of changes:
version 1.1:
 - Changed cargo, left/right props of InsertionBTree to be read-only.
 - find and delete methods for InsertionBTree.
 - Introduced empty trees (trees with no nodes).
 - Deleted not implemented's from abstract classes.
 - Deleted some if redundant checks.

ToDo:
 - Make empty tree a cached "static" value?
 - Move graft/ungraft to be methods of childs prop, now returning a
   set-like object?
"""


#Import generators.
from __future__ import generators


__version__ = 1.1
__author__ = "G. Rodrigues"


#Auxiliary class to tackle default args.
class _undef_arg(object):
    pass


#The abstract BTree class, where most of the methods reside.
class AbstractBTree(object):
    """The binary tree "interface" class.

    It has three properties: cargo, and the left and right subtrees.
    A terminal node (= atomic tree) is one where the left and right
    subtrees are the empty tree."""

    def IsAtom(self):
        """Returns 1 if the tree has no nonempty subtrees, 0 otherwise."""
        if self:
            if self.left or self.right:
                return 0
            else:
                return 1
        else:
            return 1

    #The simplest print possible.
    def __str__(self):
        if not self:
            return "()"
        else:
            return "(%s, %s, %s)" % (str(self.cargo), str(self.left), str(self.right))

    #The BTree iterators.
    def __iter__(self):
        """The standard preorder traversal of a binary tree."""
        if self:
            yield self.cargo
            for elem in self.left:
                yield elem
            for elem in self.right:
                yield elem

    def postorder(self):
        """Postorder traversal of a binary tree."""
        if self:
            for elem in self.left.postorder():
                yield elem
            for elem in self.right.postorder():
                yield elem
            yield self.cargo
        
    def inorder(self):
        """Inorder traversal of a binary tree."""
        if self:
            for elem in self.left.inorder():
                yield elem
            yield self.cargo
            for elem in self.right.inorder():
                yield elem

    #"Inplace" iterators.
    def subtree(self):
        """Preorder iterator over the (nonempty) subtrees.

        Warning: As always, do not use this iterator in a for loop while altering
        the structure of the tree."""

        if self:
            yield self
            for tree in self.left.subtree():
                yield tree
            for tree in self.right.subtree():
                yield tree

    def postsubtree(self):
        """Postorder iterator over the (nonempty) subtrees.

        Warning: As always, do not use this iterator in a for loop while altering
        the structure of the tree."""        

        if self:
            for tree in self.left.postsubtree():
                yield tree
            for tree in self.right.postsubtree():
                yield tree
            yield self

    def insubtree(self):
        """Inorder iterator over the (nonempty) subtrees.

        Warning: As always, do not use this iterator in a for loop while altering
        the structure of the tree."""        

        if self:
            for tree in self.left.postsubtree():
                yield tree
            yield self
            for tree in self.right.postsubtree():
                yield tree

    #Binary comparisons.
    def __eq__(self, other):
        """Checks for equality of two binary trees."""
        #Both trees not empty.
        if self and other:
            #Compare cargos.
            if self.cargo != other.cargo:
                return 0
            else:
                #Recursive calls.
                if self.left.__eq__(other.left):
                    return self.right.__eq__(other.right)
                else:
                    return 0
        #Both trees empty.
        elif not self and not other:
            return 1
        else:
            return 0

    def __ne__(self, other):
        return not self.__eq__(other)

    def __contains__(self, elem):
        """Returns 1 if elem is in some node of the tree, 0 otherwise."""
        for element in self:
            if elem == element:
                return 1
        return 0

    def __len__(self):
        """Returns the number of nodes (elements) in the tree."""
        ret = 0
        for elem in self:
            ret += 1
        return ret

    def copy(self):
        """Shallow copy of a BTree object."""
        if self:
            return self.__class__(self.cargo, self.left.copy(), self.right.copy())
        else:
            return self.__class__()


#The two implementations of BTree class.
class MutableBTree(AbstractBTree):
    """A mutable implementation of the binary tree BTree class."""

    def __init__(self, cargo = _undef_arg, left = None, right = None):
        """The initializer."""
        if cargo is not _undef_arg:
            self.__cargo = cargo

            if left is not None:
                if isinstance(left, MutableBTree):
                    self.__left = left
                else:
                    raise TypeError, "Object %s is not a MutableBTree binary tree." % repr(left)
            else:
                self.__left = MutableBTree()

            if right is not None:
                if isinstance(right, MutableBTree):
                    self.__right = right
                else:
                    raise TypeError, "Object %s is not a MutableBTree binary tree." % repr(right)
            else:
                self.__right = MutableBTree()

    def __nonzero__(self):
        """Returns 1 if the tree is nonempty, 0 otherwise."""
        try:
            self.__cargo
            return 1
        except AttributeError:
            return 0

    #Properties.
    def __get_cargo(self):
        if self:
            return self.__cargo
        else:
            raise AttributeError, "An empty tree has no cargo."

    def __set_cargo(self, cargo):
        if not self:
            self.__left = MutableBTree()
            self.__right = MutableBTree()            
        self.__cargo = cargo

    def __del_cargo(self):
        if self:
            #Turn tree into an empty tree => delete all attributes.
            del self.__cargo
            del self.__left
            del self.__right
        else:
            raise AttributeError, "Cannot delete the cargo of an empty tree."

    cargo = property(__get_cargo, __set_cargo, __del_cargo, "The root element of the tree.")

    def __get_left(self):
        if self:
            return self.__left
        else:
            raise AttributeError, "An empty tree has no left subtree."

    def __set_left(self, tree):
        if self:
            if isinstance(tree, MutableBTree):
                self.__left = tree
            else:
                raise TypeError, "Object %s is not a MutableBTree." % repr(tree)
        else:
            raise AttributeError, "Cannot set the left subtree of an empty tree."

    def __del_left(self):
        if self:
            self.__left = MutableBTree()
        else:
            raise AttributeError, "Cannot delete the left subtree of an empty tree."

    left = property(__get_left, __set_left, __del_left, "The left subtree.")

    def __get_right(self):
        if self:
            return self.__right
        else:
            raise AttributeError, "An empty tree has no right subtree."

    def __set_right(self, tree):
        if self:
            if isinstance(tree, MutableBTree):
                self.__right = tree
            else:
                raise TypeError, "Object %s is not a MutableBTree." % repr(tree)
        else:
            raise AttributeError, "Cannot set the right subtree of an empty tree."

    def __del_right(self):
        if self:
            self.__right = MutableBTree()
        else:
            raise AttributeError, "Cannot delete the right subtree of an empty tree."

    right = property(__get_right, __set_right, __del_right, "The right subtree.")

    #General inplace transformations of mutable binary trees.
    def map(self, func):
        """Inplace map transformation of a binary tree."""
        for tree in self.subtree():
            tree.cargo = func(tree.cargo)

    def ToImmutableBTree(self):
        """Returns an ImmutableBTree copy."""
        if self:
            return ImmutableBTree(self.cargo, self.left.ToImmutableBTree(), self.right.ToImmutableBTree())
        else:
            return ImmutableBTree()


class InsertionBTree(MutableBTree):
    """Class implementing insertion binary trees.

    The cargo, left and right properties are read-only. To add elements use the
    insert method.

    It is up to the client to ensure that the elements in the tree have meaningful
    order methods."""

    def __init__(self, cargo = _undef_arg):
        if cargo is _undef_arg:
            MutableBTree.__init__(self)
        else:
            MutableBTree.__init__(self, cargo)
            MutableBTree.left.__set__(self, InsertionBTree())
            MutableBTree.right.__set__(self, InsertionBTree())            

    #Redefinition of cargo, left/right properties to be read only.
    cargo = property(MutableBTree.cargo.__get__, None, None, "The root element of the tree.")
    left = property(MutableBTree.left.__get__, None, None, "The left subtree.")
    right = property(MutableBTree.right.__get__, None, None, "The right subtree.")

    #Redefinition of basic iterators.
    def __iter__(self):
        """Iterator over the tree elements in min-max order."""
        return MutableBTree.inorder(self)

    def subtree(self):
        """Traversal through the (nonempty) subtrees in min-max order.
        
        Warning: As always, do not use this iterator in a for loop while altering
        the structure of the tree."""

        return MutableBTree.insubtree(self)

    #Iterating in max-min order.
    def inrevorder(self):
        """Iterator over the tree elements in max-min order."""
        if self:
            for elem in self.right.inrevorder():
                yield elem
            yield self.cargo
            for elem in self.left.inrevorder():
                yield elem

    def inrevsubtree(self):
        """Traversal through the (nonempty) subtrees in max-min order.
        
        Warning: As always, do not use this iterator in a for loop while altering
        the structure of the tree."""

        if self:
            for tree in self.right.inrevsubtree():
                yield tree
            yield self
            for tree in self.left.inrevsubtree():
                yield tree

    #The in protocol.
    def __contains__(self, elem):
        if self:
            if elem == self.cargo:
                return 1
            elif elem > self.cargo:
                return self.right.__contains__(elem)
            else:
                return self.left.__contains__(elem)
        else:
            return 0

    def find(self, elem):
        """Returns the subtree which has elem as cargo.

        If elem is not in tree it raises an exception."""

        if self:
            if elem == self.cargo:
                return self
            elif elem > self.cargo:
                return self.right.find(elem)
            else:
                return self.left.find(elem)
        else:
            raise ValueError, "%s is not in tree." % str(elem)

    def insert(self, elem):
        """Inserts an element in the tree if it is not there already."""
        if not self:
            #Insert elem in empty tree.
            MutableBTree.cargo.__set__(self, elem)
            MutableBTree.left.__set__(self, InsertionBTree())
            MutableBTree.right.__set__(self, InsertionBTree())
        #Recursive calls.
        elif elem < self.cargo:
            self.left.insert(elem)
        elif elem > self.cargo:
            self.right.insert(elem)
            
    def delete(self, elem):
        """Deletes an elem from the tree.

        Raises an exception if elem is not in tree."""

        if self:
            if elem == self.cargo:
                if self.IsAtom():
                    MutableBTree.cargo.__del__(self)
                #Both trees not empty
                elif self.left and self.right:
                    #Get min element subtree and connect it to self.left.
                    minsubtree = self.right.subtree().next()
                    MutableBTree.left.__set__(minsubtree, self.left)
                    #root -> root.right.
                    MutableBTree.cargo.__set__(self, self.right.cargo)
                    MutableBTree.left.__set__(self, self.right.left)
                    MutableBTree.right.__set__(self, self.right.right)                    
                #Right subtree is empty.
                elif not self.right:
                    #root -> root.left
                    MutableBTree.cargo.__set__(self, self.left.cargo)
                    MutableBTree.left.__set__(self, self.left.left)
                    MutableBTree.right.__set__(self, self.left.right)
                #Left subtree is empty.
                else:
                    #root -> root.right
                    MutableBTree.cargo.__set__(self, self.right.cargo)
                    MutableBTree.left.__set__(self, self.right.left)
                    MutableBTree.right.__set__(self, self.right.right)
            #Recursive calls.
            elif elem < self.cargo:
                self.left.delete(elem)
            else:
                self.right.delete(elem)
        else:
            raise ValueError, "%s is not an element of the tree." % str(elem)


class ImmutableBTree(AbstractBTree):
    """An implementation of an immutable binary tree using tuples."""

    def __init__(self, cargo = _undef_arg, left = None, right = None):
        """The initializer."""
        if cargo is not _undef_arg:
            if left is not None:
                if not isinstance(left, ImmutableBTree):
                    raise TypeError, "Object %s is not an ImmutableBTree." % repr(left)
            else:
                left = ImmutableBTree()

            if right is not None:
                if not isinstance(right, ImmutableBTree):
                    raise TypeError, "Object %s is not an ImmutableBTree." % repr(right)
            else:
                right = ImmutableBTree()

            self.__head = (cargo, left, right)            
        else:
            self.__head = None

    def __nonzero__(self):
        """Returns 1 if the tree is nonempty, 0 otherwise."""
        return self.__head is not None

    #Properties.
    def __get_cargo(self):
        if self:
            return self.__head[0]
        else:
            raise AttributeError, "An empty tree has no cargo."

    cargo = property(__get_cargo, None, None, "The root element of the tree.")

    def __get_left(self):
        if self:
            return self.__head[1]
        else:
            raise AttributeError, "An empty tree has no left subtree."

    left = property(__get_left, None, None, "The left subtree.")

    def __get_right(self):
        if self:
            return self.__head[2]
        else:
            raise AttributeError, "An empty tree has no right subtree."

    right = property(__get_right, None, None, "The right subtree.")

    #Conversion method.
    def ToMutableBTree(self):
        """Returns a MutableBTree copy."""
        if self:
            return MutableBTree(self.cargo, self.left.ToMutableBTree(), self.right.ToMutableBTree())
        else:
            return MutableBTree()


#Making ImmutableBTree hashable.
class HashBTree(ImmutableBTree):
    """Class implementing a hashable immutable binary tree. It can contain only hashables."""

    def __init__(self, cargo = _undef_arg, left = None, right = None):
        try:
            if cargo is not _undef_arg:
                cargo.__hash__
            ImmutableBTree.__init__(self, cargo, left, right)
        except AttributeError:
            raise TypeError, "Object %s is not hashable." % repr(cargo)

    #HashBTrees can be keys in dictionaries (rhyme not intended).
    def __hash__(self):
        return hash(tuple(self))


#The abstract generalized tree class where most of the methods reside.
class AbstractTree(object):
    """The generalized "interface" tree class.

    It has two properties: the cargo and a childs iterator giving the child subtrees.

    The childs property returns a new (reset) iterator each time it is called.
    There is no order of iteration through the nodes (implementation is free to
    swap them around). """

    def IsAtom(self):
        """A tree is atomic if it has no subtrees."""
        try:
            self.childs.next()
        except StopIteration:
            return 1
        except AttributeError:
            return 1
        return 0

    #The simplest print possible.
    def __str__(self):
        if self:
            if self.IsAtom():
                return "(%s)" % str(self.cargo)
            else:
                temp = [str(subtree) for subtree in self.childs]
                return "(%s, %s)" % (str(self.cargo), ", ".join(temp))
        else:
            return "()"

    #The Tree iterators.
    def __iter__(self):
        """The standard preorder traversal iterator."""
        if self:
            yield self.cargo
            for subtree in self.childs:
                for elem in subtree:
                    yield elem

    def postorder(self):
        """Postorder traversal of a tree."""
        if self:
            for subtree in self.childs:
                for elem in subtree.postorder():
                    yield elem
            yield self.cargo

    #The "inplace" iterators.
    def subtree(self):
        """Preorder iterator over the subtrees.

        Warning: As always, do not use this iterator in a for loop while altering
        the structure of the tree."""

        if self:
            yield self
            for subtree in self.childs:
                for tree in subtree.subtree():
                    yield tree

    def postsubtree(self):
        """Postorder iterator over the subtrees.

        Warning: As always, do not use this iterator in a for loop while altering
        the structure of the tree."""

        if self:
            for subtree in self.childs:
                for tree in subtree.postsubtree():
                    yield tree
            yield self

    #The in protocol.
    def __contains__(self, elem):
        """Returns 1 if elem is in the tree, 0 otherwise."""
        for element in self:
            if elem == element:
                return 1
        return 0

    #Number of elements in the tree.
    def __len__(self):
        """Returns the number of elements (nodes) in the tree."""
        ret = 0
        for elem in self:
            ret += 1
        return ret

    def copy(self):
        """Shallow copy of a Tree object."""
        if self:
            if self.IsAtom():
                return self.__class__(self.cargo)
            else:
                temp = tuple([subtree.copy() for subtree in self.childs])
                return self.__class__(self.cargo, *temp)
        else:
            return self.__class__()


#Tree implementations.
class MutableTree(AbstractTree):
    """Class implementing a mutable tree type."""

    def __init__(self, cargo = _undef_arg, *trees):
        """The initializer."""
        if cargo is not _undef_arg:
            self.__head = [cargo]
            if trees:
                for tree in trees:
                    if not isinstance(tree, MutableTree):
                        raise TypeError, "%s is not a MutableTree instance." % repr(tree)
                self.__head.extend(list(trees))
        else:
            self.__head = None

    def __nonzero__(self):
        return self.__head is not None

    #Properties.
    def __get_cargo(self):
        if self:
            return self.__head[0]
        else:
            raise AttributeError, "An empty tree has no cargo."

    def __set_cargo(self, cargo):
        if self:
            self.__head[0] = cargo
        else:
            self.__head = [cargo]

    def __del_cargo(self):
        if self:
            self.__head = None
        else:
            raise ValueError, "Cannot delete the cargo of an empty tree."

    cargo = property(__get_cargo, __set_cargo, __del_cargo, "The root element of the tree.")

    def __get_childs(self):
        def it(lst):
            for i in xrange(1, len(lst)):
                yield lst[i]

        if self:
            return it(self.__head)
        #Return empty iterator.
        else:
            return iter([])

    childs = property(__get_childs, None, None, "The iterator over the child subtrees.")

    #Add or delete trees to the root of the tree.
    def graft(self, tree):
        """Graft a tree to the root node."""
        if self:
            if isinstance(tree, MutableTree):
                self.__head.append(tree)
            else:
                raise TypeError, "%s is not a Tree instance." % repr(tree)
        else:
            raise AttributeError, "Cannot graft a tree in an empty tree."

    def ungraft(self, tree):
        """Ungrafts a subtree from the current node.

        The argument is the subtree to ungraft itself."""

        if self:
            for pair in zip(self.childs, range(1, len(self.__head))):
                if tree is pair[0]:
                    del self.__head[pair[1]]
                    return None
            raise AttributeError, "Tree %s is not grafted to the root node of this tree." % repr(tree)
        else:
            raise AttributeError, "Cannot ungraft a tree from an empty tree."

    #General inplace transformations of trees.
    def map(self, func):
        """Inplace map transformation of a tree."""
        for tree in self.subtree():
            tree.cargo = func(tree.cargo)

    #Conversion methods.
    def ToImmutableTree(self):
        """Convert tree into an immutable tree."""
        if self:
            if self.IsAtom():
                return ImmutableTree(self.cargo)
            else:
                temp = tuple([subtree.ToImmutableTree() for subtree in self.childs])
                return ImmutableTree(self.cargo, *temp)
        else:
            return ImmutableTree()


class ImmutableTree(AbstractTree):
    """Class implementing an immutable generalized tree type."""

    def __init__(self, cargo = _undef_arg, *trees):
        """The initializer."""
        if cargo is not _undef_arg:
            if trees:
                for tree in trees:
                    if not isinstance(tree, ImmutableTree):
                        raise TypeError, "%s is not a ImmutableTree instance." % repr(tree)
                self.__head = (cargo,) + trees
            else:
                self.__head = (cargo,)
        else:
            self.__head = None

    def __nonzero__(self):
        return self.__head is not None

    #Properties.
    def __get_cargo(self):
        if self:
            return self.__head[0]
        else:
            raise AttributeError, "An empty tree has no cargo."

    cargo = property(__get_cargo, None, None, "The root element of the tree")

    def __get_childs(self):
        def it(lst):
            for i in xrange(1, len(lst)):
                yield lst[i]

        if self:
            return it(self.__head)
        else:
            #Return empty iterator.
            return iter(())

    childs = property(__get_childs, None, None, "The iterator over the child subtrees.")

    def ToMutableTree(self):
        """Convert tree into a mutable tree."""
        if self:
            if self.IsAtom():
                return MutableTree(self.cargo)
            else:
                temp = tuple([subtree.ToMutableTree() for subtree in self.childs])
                return MutableTree(self.cargo, *temp)
        else:
            return MutableTree()

The idea was to present just the bare structure and a minimal API. Further enhancements (balancing schemes, mapping syntax, ...) can be piled on up by further customization - the recipe, as it stands, is already too long. Even so, When I first coded it I needed hashable binary trees and that is the reason why, for both flavors, I give first an abstract class to avoid code duplication and then mutable and immutable implementations of it. In the binary tree case, insertion and hashable trees are also provided.

Needs Python >2.2 since properties and iterators/generators are heavily used.

Any suggestions for further improvement are greatly welcomed.

2 comments

Pierre Johnson 19 years, 4 months ago  # | flag

Good one! Algorithms are excellent. Thanks for the effort.

Grant Jenks 7 years, 2 months ago  # | flag

f you're looking for an API similar to that provided by a binary search tree, check out the sortedcontainers module. It implements sorted list, sorted dict, and sorted set data types in pure-Python and is fast-as-C implementations (even faster!). Learn more about sortedcontainers, available on PyPI and github.