Mapping Type -- Tree

The avltree module provides a Tree class. A tree object is much like a dictionary objects, it maps keys to values. But instead of the keys having to be hashable they have to be comparable to each other. Care must be taken not to mutate objects that are currently used as a key in a tree. Use of immutable objects as keys is recommended.

class Tree( [iterable])

Constructs a new empty Tree object. If the optional iterable parameter is supplied, updates the tree with elements obtained from iteration. This has the same effect as t=Tree(); t.update(iterable)

The following operations are defined on trees (where a and b are trees, k is a key, and v and x are arbitrary objects):

Operation	Result	Notes
`len(a)`	the number of items in `a`
`a[k]`	the value of `a` with key `k`	(1)
`a[k1:k2:step]`	returns an iterator over the tree's keys	(3)
`a[k] = v`	set `a[k]` to `v`
`del a[k]`	remove `a[k]` from `a`	(1)
`a.clear()`	remove all items from `a`
`a.copy()`	a (shallow) copy of `a`
`a.has_key(k)`	`True` if `a` has a key `k`, else `False`
`k in a`	Equivalent to `a`.has_key(`k`)
`k not in a`	Equivalent to `not` `a`.has_key(`k`)
`a.items(k1,k2,step)`	a copy of `a`'s list of (`key`, `value`) pairs	(3)
`a.keys(k1,k2,step)`	a copy of `a`'s list of keys	(3)
`a.update([b])`	updates (and overwrites) key/value pairs from `b`	(9)
`a.fromkeys(seq[, value])`	Creates a new tree with keys from `seq` and values set to `value`	(7)
`a.values(k1,k2,step)`	a copy of `a`'s list of values	(3)
`a.get(k[, x])`	`a[k]` if `k in a`, else `x`	(4)
`a.setdefault(k[, x])`	`a[k]` if `k in a`, else `x` (also setting it)	(5)
`a.pop(k[, x])`	`a[k]` if `k in a`, else `x` (and remove k)	(8)
`a.popitem()`	remove and return the (`key`, `value`) pair with the smallest key	(6)
`a.iteritems(k1,k2,step)`	return an iterator over (`key`, `value`) pairs	(3)
`a.iterkeys(k1,k2,step)`	return an iterator over the tree's keys	(3)
`a.itervalues(k1,k2,step)`	return an iterator over the tree's values	(3)

Notes:

(1)

Raises a KeyError exception if k is not in the tree.

(2)

There is no note (2) This was done so the notes here correspond with the notes in the python dictionary documentation

(3)

Keys and values are listed in key order. If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called from equal trees the lists will directly correspond. This allows the creation of (value, key) pairs using zip(): "pairs = zip(a.values(), a.keys())". The same relationship holds for the iterkeys() and itervalues() methods: "pairs = zip(a.itervalues(), a.iterkeys())" provides the same value for pairs. Another way to create the same list is "pairs = [(v, k) for (k, v) in a.iteritems()]".

The parameters in these functions are start, stop and step. All produces values will correspond with keys that are between start (included) and stop (not included). They will be produced in order except if the step is negative when they will be produced in reverse order.

(4)

Never raises an exception if k is not in the tree, instead it returns x. x is optional; when x is not provided and k is not in the tree, None is returned.

(5)

setdefault() is like get(), except that if k is missing, x is both returned and inserted into the tree as the value of k. x defaults to None.

(6)

popitem() is useful to destructively iterate over a tree, as often used in set algorithms. If the tree is empty, calling popitem() raises a KeyError.

(7)

fromkeys() is a class method that returns a new tree. value defaults to None.

(8)

pop() raises a KeyError when no default value is given and the key is not found.

(9)

update() accepts either another mapping object or an iterable of key/value pairs (as a tuple or other iterable of length two). If keyword arguments are specified, the mapping is then updated with those key/value pairs: "t.update(red=1, blue=2)".