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[source]

Bases: object

A simple binary tree with integer keys.

contains(key)[source]

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

>>> from sage.all import *
>>> from sage.misc.binary_tree import BinaryTree
>>> t = BinaryTree()
>>> t.contains(Integer(1))
False
>>> t.insert(Integer(1), Integer(1))
>>> t.contains(Integer(1))
True

from sage.misc.binary_tree import BinaryTree
t = BinaryTree()
t.contains(1)
t.insert(1, 1)
t.contains(1)
delete(key)[source]

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

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

from sage.misc.binary_tree import BinaryTree
t = BinaryTree()
t.insert(3,3)
t.insert(1,1)
t.insert(2,2)
t.insert(0,0)
t.insert(5,5)
t.insert(6,6)
t.insert(4,4)
t.delete(0)
t.delete(3)
t.delete(5)
t.delete(2)
t.delete(6)
t.delete(1)
t.delete(0)
t.get_max()
t.get_min()
get(key)[source]

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]

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

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

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

get_min()[source]

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

insert(key, value=None)[source]

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

>>> from sage.all import *
>>> from sage.misc.binary_tree import BinaryTree
>>> t = BinaryTree()
>>> t.insert(Integer(1))
>>> t.insert(Integer(0))
>>> t.insert(Integer(2))
>>> t.insert(Integer(0),Integer(1))
>>> t.get(Integer(0))
0

from sage.misc.binary_tree import BinaryTree
t = BinaryTree()
t.insert(1)
t.insert(0)
t.insert(2)
t.insert(0,1)
t.get(0)
is_empty()[source]

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

>>> from sage.all import *
>>> from sage.misc.binary_tree import BinaryTree
>>> t = BinaryTree()
>>> t.is_empty()
True
>>> t.insert(Integer(0),Integer(0))
>>> t.is_empty()
False

from sage.misc.binary_tree import BinaryTree
t = BinaryTree()
t.is_empty()
t.insert(0,0)
t.is_empty()
keys(order='inorder')[source]

Return the keys sorted according to “order” parameter.

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

pop_max()[source]

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

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

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

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

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

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

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)[source]

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()[source]