Binary trees

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)

Returns True if a node with the given key exists in the tree, and False otherwise.

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)

Removes a the node corresponding to key, and returns 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)

Returns 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]]))
sage: t.insert(0,1)
sage: t.get(0)
[0 0]
[1 1]
get_max()

Returns the value of the node with the maximal key value.

get_min()

Returns the value of the node with the minimal key value.

insert(key, value=None)

Inserts 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()

Returns True if 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')

Returns the keys sorted according to “order” parameter, which can be one of “inorder”, “preorder”, or “postorder”

pop_max()

Returns the value of the node with the maximal key value, and removes 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()

Returns the value of the node with the minimal key value, and removes 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')

Returns the keys sorted according to “order” parameter, which can be one of “inorder”, “preorder”, or “postorder”

class sage.misc.binary_tree.Test

Bases: object

binary_tree(values=100, cycles=100000)

Performs 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()