Binary Search Tree
Juan Zhai juan.zhai@rutgers.edu
Watch the videos first and then come back
• BST structure and search: https://www.youtube.com/watch?v=J3YY- Ef2xlE&ab_channel=SeshVenugopal
• BST insert: https://www.youtube.com/watch?v=BVeEmH 26PQ4&ab_channel=SeshVenugopal
• BST delete: https://www.youtube.com/watch?v=3TOl3Fv4 394&ab_channel=SeshVenugopal
Juan Zhai, juan.zhai@Rutgers.edu 2
/** This interface imposes a total ordering on the objects * of each class that implements it. */
public interface Comparable
/** Compares this object with the specified object for
* order. Returns a negative integer, zero, or a
* positive integer as this object is less than,
* equal to, or greater than the specified object. */
public int compareTo(T o); }
• An interface is a group of related methods with empty bodies.
• Interfaces form a contract. Implementing an interface requires a
class to have behaviors specified by the interface.
public class String implements Comparable
… }
}
• To implement this interface, use the implements keyword in the
class declaration.
Juan Zhai, juan.zhai@Rutgers.edu 3
Generic Binary Search Tree
public class Node
private T key;
private Node
private Node
public Node(T key) {
this.key = key;
this.right = null;
this.left = null;
}
public class BST
Node
}
}
This restricts the type parameter T to be a type that implements the interface Comparable
Refer to Sakai Code
Juan Zhai, juan.zhai@Rutgers.edu 4
Q: Why search returns T? A:Thesearchisbasedonkey,while GenericSearch what is returned is the entire object
public T search(T targetKey) {
Node current = root;
while(current != null){
int c = targetKey.compareTo(current.key);
if(c == 0)
return current.key;
if(c < 0)
current = current.left;
else
current = current.right;
}
return null;
conditional operator:? : (condition) ? a : b is an expression which returns a when condition is true and returns b when condition is false
}
current = (c<0) ? current.left : current.right; Juan Zhai, juan.zhai@Rutgers.edu 5
• Specific class decides how to compare two objects • Implements compareTo() in Comparable
• student-to-be-search is a student with id, and student-to-be-
returned has more information
Juan Zhai, juan.zhai@Rutgers.edu 6
Different shapes
• Forthesamesetofkeys,wecanhavebinarysearchtree in different shapes.
• Dependsonwhatsequenceoftheitemsareinserted into the tree
{5, 3, 1, 4, 6}
{1, 3, 4, 5, 6}
Juan Zhai, juan.zhai@Rutgers.edu 7
skewed tree: each node contains either only left or only right sub tree
Skewed Tree • Worst case running time
– search: O(n), even worse than binary search in a sorted array which has worst case O(log n)
– insertion/deletion: O(n)
• O(n) for search the position-to-insert-into/element-to-be-
deleted
• O(1) for insertion and deletion • O(n) + O(1)àO(n)
– Reshape
Juan Zhai, juan.zhai@Rutgers.edu 8
Search
Insert
Delete
Unordered List
Best
O(1)
O(1) [0]
O(1)
Worst
O(n)
O(1) [0]
O(n) [1]
Ordered Array
Best
O(1)
O(log n)
[2]
O(log n)
[2]
Worst
O(log n)
O(n) [3]
O(n) [3]
Binary Search Tree
Best
O(1)
O(log n) [4]
O(log n) [6]
Worst
O(n) [5]
O(n) [5]
O(n) [5]
Best case and worse case for the same algorithm with different situations. [0] Insertion algorithm always inserts at the front.
[1] Searchtoend,thendelete
[2] Insert/deleteatend,O(1),butsearchneedsO(logn)
[3] Insert/deletethemiddlekey,O(1),butmoven/2keys
[4] Insertionisalwaysdoneattheleaflevel,sotheinsertionprocesshas
to traverse O(log n) distance [5] Skewedtree
[6] Deletealeafnode,O(1),butsearchneedsO(logn).Deletingrootnode needs to find the minimum/maximum which takes O(log n)
Juan Zhai, juan.zhai@Rutgers.edu 9
Search
Insert
Delete
Unordered List
Best
O(1)
O(1) [0]
O(1)
Worst
O(n)
O(1) [0]
O(n) [1]
Ordered Array
Best
O(1)
O(log n)
[2]
O(log n)
[2]
Worst
O(log n
O(n) [3]
O(n) [3]
)
Juan Zhai, juan.zhai@Rutgers.edu 10
Binary Search Tree
Best
O(1)
Worst
O(n)
O(log n) [4]
O(log n) [6]
O(n) [5]
O(n) [5]
[5]
It seems that BST performs even worse than sorted array. Goal: Insertions and deletions should be faster than O(n),
and search time should not be slower than O(log n).
Solution: Keep the structure of BST balanced, meaning height never exceeds O(log n). Then the
search/insert/delete times would never exceeds O(log n).
àReshape a BST
Get help from CAVE
• The CAVE is available to students – no appointment necessary, help with concepts and assignments
• https://resources.cs.rutgers.edu/docs/rooms- equipment/cave/
• Monday through Thursday, 1-11PM
• Friday 1-6PM
• Sunday 3-11PM
https://rutgers.webex.com/meet/cs-the-cave
11
Learning Center
• Get help from https://rlc.rutgers.edu/node/95
12