Deprecated: (6.006) preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /afs/athena.mit.edu/course/6/6.006/web_scripts/spring08/wiki/includes/Sanitizer.php on line 1470

Deprecated: (6.006) preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /afs/athena.mit.edu/course/6/6.006/web_scripts/spring08/wiki/includes/Sanitizer.php on line 1470

Deprecated: (6.006) preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /afs/athena.mit.edu/course/6/6.006/web_scripts/spring08/wiki/includes/Sanitizer.php on line 1470

Deprecated: (6.006) preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /afs/athena.mit.edu/course/6/6.006/web_scripts/spring08/wiki/includes/Sanitizer.php on line 1470

Deprecated: (6.006) preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /afs/athena.mit.edu/course/6/6.006/web_scripts/spring08/wiki/includes/Sanitizer.php on line 1470

Deprecated: (6.006) preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /afs/athena.mit.edu/course/6/6.006/web_scripts/spring08/wiki/includes/Sanitizer.php on line 1470
Binary Search Trees - 6.006 Introduction to Algorithms

Binary Search Trees

From 6.006 Introduction to Algorithms

Jump to: navigation, search

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

  • avl.py
    • Imports and extends bst.py
    • Features: insert, find, delete_min, ASCII art

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
/\ /\
Personal tools