Binary Search Trees
From 6.006 Introduction to Algorithms
(Difference between revisions)
(add bstsize) |
(fix urls!) |
||
(3 intermediate revisions not shown) | |||
Line 1: | Line 1: | ||
+ | This page contains various implementations of different Binary Search Trees (BSTs). | ||
+ | |||
==Simple BST (no balancing)== | ==Simple BST (no balancing)== | ||
- | * [http://courses.csail.mit.edu/6.006/ | + | * [http://courses.csail.mit.edu/6.006/spring08/source/bst.py bst.py] |
** Features: insert, find, delete_min, ASCII art | ** Features: insert, find, delete_min, ASCII art | ||
- | * [http://courses.csail.mit.edu/6.006/ | + | * [http://courses.csail.mit.edu/6.006/spring08/source/bstsize.py bstsize.py] |
+ | ** Imports and extends [http://courses.csail.mit.edu/6.006/fall07/source/bst.py bst.py] | ||
** Augmentation to compute subtree sizes | ** Augmentation to compute subtree sizes | ||
+ | * [http://courses.csail.mit.edu/6.006/spring08/keynotes/bstsize_r.py bstsize_r.py] | ||
+ | ** Recursive version from recitation for computing subtree sizes | ||
+ | ** Features: insert, find, rank, delete | ||
==AVL tree== | ==AVL tree== | ||
- | * [http://courses.csail.mit.edu/6.006/ | + | * [http://courses.csail.mit.edu/6.006/spring08/source/avl.py avl.py] |
** 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 |
Latest revision as of 18:10, 14 February 2008
This page contains various implementations of different Binary Search Trees (BSTs).
Simple BST (no balancing)
- bst.py
- Features: insert, find, delete_min, ASCII art
- bstsize.py
- Imports and extends bst.py
- Augmentation to compute subtree sizes
- bstsize_r.py
- Recursive version from recitation for computing subtree sizes
- Features: insert, find, rank, delete
AVL tree
Testing
Both bst.py and avl.py (as well as bstsize.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 /\ /\