CS 2114 Lecture Notes - Lecture 26: Binary Search Tree, Mobile Suit Gundam, Object Copying
29 Apr 2018
School
Department
Course
Professor
Daniel T. Eisert CS-2114
1
Lecture 26 – Binary Search Trees
April 23, 2018 (Week 14)
Class Business
Project V final submission is due Thursday, April 26. The contribution report
and ethics discussion are both due Sunday, April 29.
Last lab session is Wednesday, April 25.
OpenDSA Homework on Trees is due Monday, April 30.
Individual Design Homework is due Monday, April 30 (review Vending UML).
More Trees
Recall ~ trees have left and right child references, not next and previous
references.
Stack Implementation:
- The root is at the bottom of the stack.
- Recursion is significantly easier to do.
- Can use post-order, pre-order, or inorder traversals.
• EXAMPLE: See the BinaryTree class in ExTreeIntroduction in Eclipse ~
review this for the final exam!
- If leftTree and rightTree are referencing the same spot on the tree,
deleting a subtree or subnode on one side deletes the same thing on the
other side.
- Instead, use cloning and make a deep copy.
Binary Search
- Good for arrays, not good for linked chains.
- Construct in a specific way to make it suitable for trees.
- To make it in order, follow an inorder traversal.
Binary Search
Trees
- Organize the middle as the root, then the quarters as its children, the
eighths as its grandchildren, etc…
- Left subtree contains only smaller values, while the right subtree
contains only larger values.
- Every node in a binary search tree is the root of a binary search tree.
- What to do with duplicates? define as you will.
- Use recursive algorithm (M, Week 14 Slideshow).
- Methods will use return values instead of exceptions to determine
whether the operation has been successfully executed.
- 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.
Efficiency
- Searching a binary search tree of height h is which is less than
. It is closer to .
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Project v final submission is due thursday, april 26. The contribution report and ethics discussion are both due sunday, april 29. Opendsa homework on trees is due monday, april 30. Individual design homework is due monday, april 30 (review vending uml). Recall ~ trees have left and right child references, not next and previous references. The root is at the bottom of the stack. Can use post-order, pre-order, or inorder traversals: example: see the binarytree class in extreeintroduction in eclipse ~ review this for the final exam! If lefttree and righttree are referencing the same spot on the tree, deleting a subtree or subnode on one side deletes the same thing on the other side. Instead, use cloning and make a deep copy. Good for arrays, not good for linked chains. Construct in a specific way to make it suitable for trees. To make it in order, follow an inorder traversal.
