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