Compare Cpu Scheduling of Linux and Unix.
Binary Search Trees basic implementations randomized BSTs deletion in BSTs
References: Algorithms in Java, Chapter 12 Intro to Programming, Section 4.4 http://www.cs.princeton.edu/introalgsds/43bst 1
Elementary implementations: summary
implementation
worst case search insert N N N N
average case search N/2 lg N N/2 N/2 insert N/2 N/2 N N/2
ordered iteration? no yes no yes
operations on keys equals() compareTo() equals() compareTo()
unordered array ordered array unordered list ordered list
N lg N N N
Challenge: Efficient implementations of get() and put() and ordered iteration.
2
basic implementations randomized BSTs deletion in BSTs
3
Binary Search Trees (BSTs) Def. A BINARY SEARCH TREE is a binary tree in symmetric order. it A binary tree is either: empty a key-value pair and two binary trees [neither of which contain that key]
• •
best of
the
was times
equal keys ruled out to facilitate associative array implementations
Symmetric order means that: every node has a key every node’s key is larger than all keys in its left subtree smaller than all keys in its right subtree
• •
node
x subtrees smaller
larger
4
BST representation A BST is a reference to a Node. A Node is comprised of four fields: A key and a value. A reference to the left and right subtree.
• •
smaller keys
larger keys
root private class Node { Key key; Value val; Node left, right; }
Key and Value are generic types; Key is Comparable
it
2
best
1
was
2
the
1
of
1
times
1
5
BST implementation (skeleton)
public class BST implements Iterable { instance variable private Node root; private class Node { Key key; Value val; Node left, right; Node(Key key, Value val) { this.key = key; this.val = val; } } inner class
public void put(Key key, Value val) // see next slides public Val get(Key key) // see next slides }
6
BST implementation (search)
public Value
References: Algorithms in Java, Chapter 12 Intro to Programming, Section 4.4 http://www.cs.princeton.edu/introalgsds/43bst 1
Elementary implementations: summary
implementation
worst case search insert N N N N
average case search N/2 lg N N/2 N/2 insert N/2 N/2 N N/2
ordered iteration? no yes no yes
operations on keys equals() compareTo() equals() compareTo()
unordered array ordered array unordered list ordered list
N lg N N N
Challenge: Efficient implementations of get() and put() and ordered iteration.
2
basic implementations randomized BSTs deletion in BSTs
3
Binary Search Trees (BSTs) Def. A BINARY SEARCH TREE is a binary tree in symmetric order. it A binary tree is either: empty a key-value pair and two binary trees [neither of which contain that key]
• •
best of
the
was times
equal keys ruled out to facilitate associative array implementations
Symmetric order means that: every node has a key every node’s key is larger than all keys in its left subtree smaller than all keys in its right subtree
• •
node
x subtrees smaller
larger
4
BST representation A BST is a reference to a Node. A Node is comprised of four fields: A key and a value. A reference to the left and right subtree.
• •
smaller keys
larger keys
root private class Node { Key key; Value val; Node left, right; }
Key and Value are generic types; Key is Comparable
it
2
best
1
was
2
the
1
of
1
times
1
5
BST implementation (skeleton)
public class BST implements Iterable { instance variable private Node root; private class Node { Key key; Value val; Node left, right; Node(Key key, Value val) { this.key = key; this.val = val; } } inner class
public void put(Key key, Value val) // see next slides public Val get(Key key) // see next slides }
6
BST implementation (search)
public Value