- A binary search tree is a binary tree T such that
- each internal node stores an item (k,e) of a dictionary,
- keys stored at nodes in the left subtree of node v are less than or equal to k(v), the key stored at node v,
- keys stored at nodes in the right subtree of v are greater than or equal to k(v), and
- external nodes do not store elements but rather serve as placeholders.
Search
- The binary search tree T is a decision tree where the question asked at an internal node v is whether the search key k is less than, equal to, or greater than the key stored at v.
- Pseudocode:
Output: A node w of the subtree T(v) of T rooted at v, such that either w is an internal node storing key k or w is the external node encountered in the inorder traversal of T(v) after all the internal nodes with keys smaller than k and before all the internal nodes with keys greater than k.
if v is an external node then
return v
if k = key(v) then
return v
else if k < key(v) then
return TreeSearch(k, T.leftChild(v))
else // k > key(v)
return TreeSearch(k, T.rightChild(v))
Search (cont.)
- Two search examples, one successful, the other unsuccessful.
Insertion into a Binary Search Tree
- To perform the Dictionary operation insertItem(k,e) on a Dictionary implemented with a binary search tree,
- Start by calling TreeSearch(k, T.root()) on T. Let w be the node returned by TreeSearch.
- If w is external, we know that no item with key k is stored in T. We then call expandExternal(w) on T and have w store the item (k,e).
- If w is internal, we know that another item with key k is stored at w. We call TreeSearch(k, T.rightChild(w)) iteratively, until an external node is returned.
- The above algorithm eventually traces a path from the root of T down to an external node which gets replaced by an internal node that stores the new item.
- Insertion of an element with key 78:
Insertion into a Binary Search Tree (cont.)
- Insertion of an element with key 80:
Removal from a Binary Search Tree
- Execute algorithm TreeSearch(k, T.root()) on T to find a node storing k in T.
- if TreeSearch(k,T.root()) returns an external node, return the special object NO_SUCH_KEY.
- else if w¬TreeSearch(k,T.root()) returns an internal node and one of the children of the internal node w storing the key is external:
- z ¬ external child of w
- replace w with the sibling of z (call removeAboveExternal(z))
- else
- Find the first internal node y that follows w in the inorder traversal of T. The left child x of y is the external node that immediately follows node w in the inorder traversal of T.
- t ¬ element(w)
- swap(y,w) {move element of y into w}
- removeAboveExternal(x)
- return t
Removal from a Binary Search Tree (cont.)
- Removal where the key the remove is stored at a node (w) with an external child.
Removal from a Binary Search Tree (cont.)
Removal from a Binary Search Tree (cont.)
- Removal where the key to remove is stored at a node whose children are both internal:
Removal from a Binary Search Tree (cont.)
Time Complexity
- Searching, insertion, and removal in a binary search tree are all O(h), where h is the height of the tree.
- On average, a binary search tree with n keys generated from a random series of insertions and deletions has expected height O(log n). This statement, however, requires precise mathematical language in the definition of "a random series of insertions and deletions."
- However, in the worst case, the costs of searching, insertion, and removal are O(n) if the height of the tree is equal to n. Thus in some cases, searching, insertion, and removal is no better than in a sequence.
- Thus, to prevent the worst case, we need to develop a rebalancing scheme to bound the height of the tree to O(log n).
Lafore Binary Search Tree Applet (not available on public version)
public class SimpleBinarySearchTree implements SimpleDictionary {
Comparator C; // comparator
BinaryTree T; // binary tree
protected Position actionPos; // insertion position or parent of removed position
public SimpleBinarySearchTree(Comparator c) {
C = c;
T = (BinaryTree) new BTNodeBinaryTree();
} // auxiliary methods:
protected Object key(Position position) {
return ((Item) position.element()).key();
}
protected Object element(Position position) {
return ((Item) position.element()).element();
}
protected void checkKey(Object key) throws InvalidKeyException {
if(!C.isComparable(key))
throw new InvalidKeyException("Key "+key+" is not comparable");
} protected Position findPosition(Object key, Position pos) {
if (T.isExternal(pos))
return pos; // key not found and external node reached returned
else {
Object curKey = key(pos);
if(C.isLessThan(key, curKey))
return findPosition(key, T.leftChild(pos)); // search in left subtree
else if(C.isGreaterThan(key, curKey))
return findPosition(key, T.rightChild(pos)); // search in right subtree
else
return pos; // return internal node where key is found
}
}
Class SimpleBinarySearchTree (cont.)
// method findAllVectorEnum omitted // methods of the dictionary ADT
publicint size() { return (T.size()-1)/2; }
publicboolean isEmpty() { return T.size() == 1; }
public Object findElement(Object key) throws InvalidKeyException {
checkKey(key); // may throw an InvalidKeyException
Position curPos = findPosition(key, T.root());
actionPos = curPos;
if (T.isInternal(curPos))
return element(curPos);
else
return NO_SUCH_KEY;
}
// Method findAllElements omitted
Class SimpleBinarySearchTree (cont.)
publicvoid insertItem(Object key, Object element)
throws InvalidKeyException {
checkKey(key); // may throw an InvalidKeyException
Position insPos = T.root();
// if the insertion key already exists, insert the new
//item to the right of all the existing items with the same key
do {
insPos = findPosition(key, insPos);
if (T.isExternal(insPos))
break;
else
insPos = T.rightChild(insPos);
} while (true);
T.expandExternal(insPos);
Item newItem = new Item(key, element);
T.replace(insPos, newItem);
actionPos = insPos;
}
Class BTNodeBinaryTreepublic Object remove(Object key) throws InvalidKeyException {// Methods omitted: removeAll, keys, elements, swap
Object toReturn;
checkKey(key); // may throw an InvalidKeyException
Position remPos = findPosition(key, T.root());
if(T.isExternal(remPos)) {
actionPos =remPos;
return NO_SUCH_KEY;
}
else{
toReturn = element(remPos); // element to be returned
if (T.isExternal(T.leftChild(remPos)))
remPos = T.leftChild(remPos);
else if (T.isExternal(T.rightChild(remPos)))\
remPos = T.rightChild(remPos);
else { // key is at a node with internal children
// find node for swapping items
Position swapPos = remPos;
remPos = T.rightChild(swapPos);
do
remPos = T.leftChild(remPos);
while (T.isInternal(remPos));
swap(swapPos, T.parent(remPos));
}
actionPos = T.sibling(remPos);
T.removeAboveExternal(remPos);
return toReturn;
}
}
// Also omitted: private methods
}
AVL Trees
- An AVL tree is a binary search tree that satisfies the height-balance property: for every internal node v of T, the heights of the children of v can differ by at most 1.
- The height-balance property requires additional rules on the structure of the binary search tree to guarantee O(log n) height.
- An immediate consequence of the height-balance property is that any subtree of an AVL tree is itself an AVL tree.
- AVL stands for Adel’son, Vel’skii and Landis.
- An example of an AVL tree where the heights are shown next to the nodes:
Height of an AVL Tree
- Proposition: The height of an AVL tree T storing n keys is O(log n).
- Justification: The easiest way to approach this problem is to try to find the minimum number n(h) of internal nodes of an AVL tree of height h.
- Two base cases:
- n(1) = 1.
- n(2) = 2.
- For n ³ 3, an AVL tree of height h minimally contains the root node, one AVL subtree of height h-1 and the other AVL subtree of height h-2.
(1)
Height of an AVL Tree (cont.)
(2)
.
Height of an AVL Tree (cont.)
,
.
Insertion into an AVL Tree
- A binary search tree T is considered balanced if for every node v in T, the heights of v’s children differ by at most 1.
- Since an AVL tree is a binary search tree, inserting a node into an AVL tree involves performing an expandExternal(w) operation on T, which changes the heights of some of the nodes in T, including w.
- If an insertion causes T to become unbalanced, we travel up the tree from the newly created node until we find the first node x such that its grandparent z is an unbalanced node. Only nodes on the path from w to the root node are candidates for becoming unbalanced.
- Since z became unbalanced by an insertion in the subtree rooted at its child y,
- To rebalance the subtree rooted at z, we must perform a restructuring …
- In pseudo-code:
Output: Tree T restructures by a rotation (either single or double) involving nodes x, y, and z.
- Let (a,b,c) be an inorder listing of the nodes x, y, and z, and let (T0, T1, T2, T3) be an inorder listing of the four subtrees of x, y, and z not rooted at x, y, or z.
- Replace the subtree rooted at z with a new subtree rooted at b.
- Let a be the left child of b and let T0 and T1 be the left and right subtrees of a, respectively.
- Let c be the right child of b and let T2 and T3 be the left and right subtrees of c, respectively.
Restructuring Illustrated
- There are four ways to rotate nodes in an AVL tree. Each is graphically represented here.
- Single rotations (when b = y):
- rotating y over z.
Restructuring Illustrated (cont.)
- double rotations (when b = x):
- Rotating x over y and then over z.
Removal from an AVL Tree
- Start by executing the remove method on a generic binary search tree. This requires a call to removeAboveExternal.
- We can easily see that performing a removeAboveExternal(w) can cause T to become unbalanced.
- Let z be the first unbalanced node encountered while traveling up the tree from w. Also, let y be the child of z with the larger height, and let x be the child of y with the larger height.
- We perform the operation restructure(x) to restore balance at the subtree rooted at x.
- As this restructuring may upset the balance of another node higher up in the tree, we must continue checking for balance until the root of T is reached.
- Each restructure operation is O(1). Therefore removal is O(log n).
- Example of deletion from an AVL tree:
Removal (cont.)
- Another example of deletion from an AVL tree:
int height;
public AVLItem(Object k, Object e, int h) {
super(k, e);
height = h;
}
public int height() {
return height;
}
public int setHeight(int h) {
int oldHeight = height;
height = h;
return oldHeight;
}
}
public SimpleAVLTree(Comparator c) {
super(c);
T = new RestructurableNodeBinaryTree();
}
private int height(Position p) {
if(T.isExternal(p))
return 0;
else
return ((AVLItem) p.element()).height();
}
private void setHeight(Position p) { // called only if p is internal
((AVLItem)p.element()).setHeight(1+ Math.max(height(T.leftChild(p)),
height(T.rightChild(p))));
}
Class SimpleAVLTree (cont.)
privateboolean isBalanced(Position p) {
// test whether node p has balance factor between - // 1 and 1
int bf = height(T.leftChild(p)) –
height(T.rightChild(p));
return ((-1 <= bf) && (bf <= 1));
} private Position tallerChild(Position p) {
// return a child of p with height no smaller than that
// of the other child
if(height(T.leftChild(p)) >= height(T.rightChild(p)))
return T.leftChild(p);
else
return T.rightChild(p);
}
Class SimpleAVLTree (cont.)
// dictionary methods
publicvoid insertItem(Object key, Object element) throws InvalidKeyException {
super.insertItem(key, element);// may throw an
// InvalidKeyException
Position zPos = actionPos; // start at the insertion position
T.replace(zPos, new AVLItem(key, element, 1));
rebalance(zPos);
} public Object remove(Object key) throws InvalidKeyException {
Object toReturn = super.remove(key); // may throw
// an InvalidKeyException
if(toReturn != NO_SUCH_KEY) {
Position zPos = actionPos; // start at the removal position
rebalance(zPos);
}
return toReturn;
}
Class SimpleAVLTree (cont.)
privatevoid rebalance(Position zPos) {} Class RestructurableBinaryTree
// traverse the path of T from zPos to the root; for each node encountered,
//recompute its height and perform a rotation if it is unbalanced
while (!T.isRoot(zPos)) {
zPos = T.parent(zPos);
setHeight(zPos);
if (!isBalanced(zPos)) { // perform a rotation
Position xPos = tallerChild(tallerChild(zPos));
zPos = ((RestructurableNodeBinaryTree)T).restructure(xPos);
setHeight(T.leftChild(zPos));
setHeight(T.rightChild(zPos));
setHeight(zPos);
}
}
}
Interface java.util.SortedMap
Class java.util.TreeMap
No comments:
Post a Comment