API reference

• API reference
  • Tree
    • class Tree([iterable])
    • len(t)
    • x in t
    • add(item)
    • update(*iterables)
    • remove(key)
    • discard(key)
    • clear()
    • copy()
    • left_bound(key)
    • right_bound(key)
  • SortedSet
  • SortedDict

Tree

The Tree type implements a binary tree with auto-balancing logic (red-black tree algorithm).

All methods of Tree, unless stated otherwise, use __lt__ and __gt__ operators to determine the position of a value in the tree:

if lhs < rhs:
    # go left
elif lhs > rhs:
    # go right
else:
    # value found

The term key is broadly used to refer to the property(s) of the item that determines its position in the tree.

class Tree([iterable])

Returns a new tree instance. The items of the tree are taken from the iterable object, if given.

len(t)

Returns the number of items in the tree.

x in t

Returns True if the tree contains one or more items matching the given key, False otherwise.

add(item)

Add item to the tree.

update(*iterables)

Insert items in the tree taken from zero or more iterables.

remove(key)

Remove the first item that matches the given key from the tree. If no item matches the key, raises a KeyError.

discard(key)

Like remove(), but does not raise a KeyError if no item matches the key.

clear()

Removes all items from the tree.

copy()

Creates a shallow copy of the tree.

left_bound(key)

Returns the item that partitions the tree in such a way that all previous items are smaller and all next items are larger or equal. The item, if it exists, is unique (though it may depend on the order in which the items were inserted in the tree, if there are multiple items with the same key).

right_bound(key)

Returns the item that partitions the tree in such a way that all previous items are smaller or equal and all next items are larger. See left_bound(key) for additional info.

SortedSet

WIP

SortedDict

TODO