Binary Search Trees
From 6.006 Introduction to Algorithms
(Difference between revisions)
(start) |
(add testing) |
||
Line 9: | Line 9: | ||
** Imports and extends [http://courses.csail.mit.edu/6.006/fall07/source/bst.py bst.py] | ** Imports and extends [http://courses.csail.mit.edu/6.006/fall07/source/bst.py bst.py] | ||
** Features: insert, find, delete_min, ASCII art | ** Features: insert, find, delete_min, ASCII art | ||
+ | |||
+ | ==Testing== | ||
+ | |||
+ | Both bst.py and avl.py can be tested interactively from a UNIX shell as follows: | ||
+ | |||
+ | * <code>python bst.py 10</code> — do 10 random insertions, printing BST at each step | ||
+ | * <code>python avl.py 10</code> — do 10 random insertions, printing AVL tree at each step | ||
+ | |||
+ | Alternatively, you can use them from a Python shell as follows: | ||
+ | |||
+ | <pre> | ||
+ | >>> import bst | ||
+ | >>> t = bst.BST() | ||
+ | >>> print t | ||
+ | <empty tree> | ||
+ | >>> for i in range(4): | ||
+ | ... t.insert(i); | ||
+ | ... | ||
+ | >>> print t | ||
+ | 0 | ||
+ | /\ | ||
+ | 1 | ||
+ | /\ | ||
+ | 2 | ||
+ | /\ | ||
+ | 3 | ||
+ | /\ | ||
+ | >>> t.delete_min() | ||
+ | >>> print t | ||
+ | 1 | ||
+ | /\ | ||
+ | 2 | ||
+ | /\ | ||
+ | 3 | ||
+ | /\ | ||
+ | </pre> | ||
+ | |||
+ | <pre> | ||
+ | >>> import avl | ||
+ | >>> t = avl.AVL() | ||
+ | >>> print t | ||
+ | <empty tree> | ||
+ | >>> for i in range(4): | ||
+ | ... t.insert(i); | ||
+ | ... | ||
+ | >>> print t | ||
+ | 1 | ||
+ | / \ | ||
+ | 0 2 | ||
+ | /\ /\ | ||
+ | 3 | ||
+ | /\ | ||
+ | >>> t.delete_min() | ||
+ | >>> print t | ||
+ | 2 | ||
+ | / \ | ||
+ | 1 3 | ||
+ | /\ /\ | ||
+ | </pre> |
Revision as of 17:43, 14 February 2008
Simple BST (no balancing)
- bst.py
- Features: insert, find, delete_min, ASCII art
AVL tree
Testing
Both bst.py and avl.py can be tested interactively from a UNIX shell as follows:
-
python bst.py 10
— do 10 random insertions, printing BST at each step -
python avl.py 10
— do 10 random insertions, printing AVL tree at each step
Alternatively, you can use them from a Python shell as follows:
>>> import bst >>> t = bst.BST() >>> print t <empty tree> >>> for i in range(4): ... t.insert(i); ... >>> print t 0 /\ 1 /\ 2 /\ 3 /\ >>> t.delete_min() >>> print t 1 /\ 2 /\ 3 /\
>>> import avl >>> t = avl.AVL() >>> print t <empty tree> >>> for i in range(4): ... t.insert(i); ... >>> print t 1 / \ 0 2 /\ /\ 3 /\ >>> t.delete_min() >>> print t 2 / \ 1 3 /\ /\