CS 2114 Lecture Notes - Lecture 27: Binary Search Tree, Object Copying, Mobile Suit Gundam
29 Apr 2018
School
Department
Course
Professor
Daniel T. Eisert CS-2114
1
Lecture 27 – Binary Search Trees & Cloning
April 25, 2018 (Week 14)
Class Business
Project V final submission is due Thursday, April 26.
Last lab session is Wednesday, April 25.
Individual Design Homework is due Monday, April 30 (review Vending UML).
Binary Search
Trees
- Duplicate Entries: if any entry e has a duplicate entry d, we arbitrarily
require that d occur in the right subtree of e’s node such that data in a
node that is less than or equal to data in the node’s right subtree. Given
that, data in a node is greater than data in the node’s left subtree.
- Regular trees…just set values, but for a BST, throw an
UnsupportedOperationException so the client can’t mess up the order.
- Searching: use compareTo and find its value: -1, 0, 1.
- Adding: the structure of the tree depends on the order in which they
were added (greater than or less than the root) implement
recursively (call again when a subtree exists).
- Removing: slide the data up for nodes with a subtree. Suppose there are
two children, move the largest value in the left subtree of the node
being removed. This preserves the integrity of the binary search tree.
Efficiency
- Searching a binary search tree of height h is which is less than
.
- Long Very Tall Tree / Worst Case: .
- Need balance – shortest tree is full: .
Cloning
- Shallow clone: copies referencing the same thing (aliases); changes to
one data field change the other.
- Deep clone: copies reference a clone of the data (takes new space in
memory).
- Clonable interface: need to have a clone method for the object. All
objects inherit this method. Use a try catch.
- Clone any mutable data fields.
• EXAMPLE: fullName is a field that was cloned.
public Object clone() {
Name theCopy = null;
try {
theCopy = (name)super.clone(); //makes shallow copy
}
catch (CloneNotSUpportedException e) {
throw new Error(e.toString()); }
theCopy.fullName = (Name)fullName.clone();
return theCopy;
}
- Strings are a special case since they are immutable. If you change the
student’s ID, it won’t change the clone’s ID. Therefore, when you change
a String field, it will get new memory anyway when you change it (not
right away since they are immutable).
- Cloning an Array, list, or any collection is slightly more involved, but
easily doable. Need to loop through everything and clone each piece.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Lecture 27 binary search trees & cloning. Project v final submission is due thursday, april 26. Individual design homework is due monday, april 30 (review vending uml). Given that, data in a node is greater than data in the node"s left subtree. Regular trees just set values, but for a bst, throw an. Unsupportedoperationexception so the client can"t mess up the order. Searching: use compareto and find its value: -1, 0, 1. Adding: the structure of the tree depends on the order in which they were added (greater than or less than the root) implement recursively (call again when a subtree exists). Removing: slide the data up for nodes with a subtree. Suppose there are two children, move the largest value in the left subtree of the node being removed. This preserves the integrity of the binary search tree. Searching a binary search tree of height h is (cid:4666)(cid:4667) which is less than (cid:4666)(cid:4667).
.jpg)