Binary trees#

This implements a binary tree in Cython.

AUTHORS:

Tom Boothby (2007-02-15). Initial version free for any use (public domain).

class sage.misc.binary_tree.BinaryTree#

Bases: object

A simple binary tree with integer keys.

contains(key)#

Return whether a node with the given key exists in the tree.

EXAMPLES:

sage: from sage.misc.binary_tree import BinaryTree
sage: t = BinaryTree()
sage: t.contains(1)
False
sage: t.insert(1,1)
sage: t.contains(1)
True

delete(key)#

Remove a the node corresponding to key, and return the value associated with it.

EXAMPLES:

sage: from sage.misc.binary_tree import BinaryTree
sage: t = BinaryTree()
sage: t.insert(3,3)
sage: t.insert(1,1)
sage: t.insert(2,2)
sage: t.insert(0,0)
sage: t.insert(5,5)
sage: t.insert(6,6)
sage: t.insert(4,4)
sage: t.delete(0)
0
sage: t.delete(3)
3
sage: t.delete(5)
5
sage: t.delete(2)
2
sage: t.delete(6)
6
sage: t.delete(1)
1
sage: t.delete(0)
sage: t.get_max()
4
sage: t.get_min()
4

get(key)#

Return the value associated with the key given.

EXAMPLES:

sage: from sage.misc.binary_tree import BinaryTree
sage: t = BinaryTree()
sage: t.insert(0, Matrix([[0,0], [1,1]]))                                   # needs sage.modules
sage: t.insert(0, 1)
sage: t.get(0)                                                              # needs sage.modules
[0 0]
[1 1]

get_max()#: Return the value of the node with the maximal key value.

get_min()#: Return the value of the node with the minimal key value.

insert(key, value=None)#

Insert a key-value pair into the BinaryTree.

Duplicate keys are ignored.

The first parameter, key, should be an int, or coercible (one-to-one) into an int.

EXAMPLES:

sage: from sage.misc.binary_tree import BinaryTree
sage: t = BinaryTree()
sage: t.insert(1)
sage: t.insert(0)
sage: t.insert(2)
sage: t.insert(0,1)
sage: t.get(0)
0

is_empty()#

Return whether the tree has no nodes.

EXAMPLES:

sage: from sage.misc.binary_tree import BinaryTree
sage: t = BinaryTree()
sage: t.is_empty()
True
sage: t.insert(0,0)
sage: t.is_empty()
False

keys(order='inorder')#

Return the keys sorted according to “order” parameter.

The order can be one of “inorder”, “preorder”, or “postorder”

pop_max()#

Return the value of the node with the maximal key value, and remove that node from the tree.

EXAMPLES:

sage: from sage.misc.binary_tree import BinaryTree
sage: t = BinaryTree()
sage: t.insert(4,'e')
sage: t.insert(2,'c')
sage: t.insert(0,'a')
sage: t.insert(1,'b')
sage: t.insert(3,'d')
sage: t.insert(5,'f')
sage: while not t.is_empty():
....:     print(t.pop_max())
f
e
d
c
b
a

pop_min()#

Return the value of the node with the minimal key value, and remove that node from the tree.

EXAMPLES:

sage: from sage.misc.binary_tree import BinaryTree
sage: t = BinaryTree()
sage: t.insert(4,'e')
sage: t.insert(2,'c')
sage: t.insert(0,'a')
sage: t.insert(1,'b')
sage: t.insert(3,'d')
sage: t.insert(5,'f')
sage: while not t.is_empty():
....:     print(t.pop_min())
a
b
c
d
e
f

values(order='inorder')#

Return the keys sorted according to “order” parameter.

The order can be one of “inorder”, “preorder”, or “postorder”

class sage.misc.binary_tree.Test#

Bases: object

binary_tree(values=100, cycles=100000)#

Perform a sequence of random operations, given random inputs to stress test the binary tree structure.

This was useful during development to find memory leaks / segfaults. Cycles should be at least 100 times as large as values, or the delete, contains, and get methods won’t hit very often.

INPUT:

values – number of possible values to use
cycles – number of operations to perform

random()#