程序代写代做代考 algorithm B tree C Binary Search Tree

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{ public int compareTo(String anotherString){
… }
}
• 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 left;
private Node right;
public Node(T key) {
this.key = key;
this.right = null;
this.left = null;
}
public class BST>{
Node root;
}
}
This restricts the type parameter T to be a type that implements the interface Comparable, guaranteeing that the call to compareTo()is valid, meaning support comparison with other instances of its own type
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