CS61B: Lecture 16

Extends

• When we use extends, we inherit all public members of a class into our child class. However, private attributes and methods are not inherited.
• Constructors are not inherited. However, the superclass constructor is called within the child class constructor.
• Super class methods can still be involved using super.

public class VengefulSLList<Item> extends SLList<Item> {
    private List<Item> deletedItems;

    public VengefulSList() {
        // super() is implicitly called.
        deletedItems = new ArrayList<>();
    }

    @Override
    public Item removeLast() {
        Item removedItem = super.removeLast(); // This will call the SList removeLast method
        deletedItems.add(removedItem);
        return removeditem;
    }

    private void printLostItems() {
        System.out.println(deletedItems);
    }
}

Set, Map, and ADT

• An Abstract Data Type (ADT) is defined only by operations, not by its implementation.

  TreeSet and TreeMap

• A traditional linked list structure is too slow to check if an element exists within the set.
  • We have to traverse through all the elements of the Linked list to find the element.
  • It is a slow search even if the list was in order.
• To add efficiency, we are going to use a binary search tree to represent a set.
• A tree contains a set of nodes and edges that connect its nodes.
  • There is exactly one path between any two nodes
• A Rooted Tree has one node called the root.
  • Every node except for the root has exactly one parent.
  • A node with no child is called a leaf.
• In a rooted binary tree, every node has either 0, 1, or 2 children (subtrees).

Binary Search Trees

• A Binary Search Tree is a tree that satisfies the BST Property.
  • For every node X in the tree:
    • Every key in the left subtree is less than X’s key.
    • Every key in the right subtree is greater than X’s key.
• The ordering in a BST must be complete, transitive, and antisymmetric. Given keys p and q:
  • Exactly one of $p<q$ and $q>p$ are true.
  • $p<q$ and $q<r$ imples $p<r$.

Searching BST

• If searchKey equals T.key, we return T.key.
  • If searchkey < T.key, we search T.left
  • If searchkey > T.key, we search T.right
• Bushy BSTs are extrememly fast for searching.

Inserting BST

• We search for the key
  • If the key is found, no nothing,
  • If the key is not found, we create a new node and set an appropriate link.

Deleting BST

• Three cases:
• If we delete a node with 0 children, we may just simply remove it.
• If we delete a node with 1 children, we may just set the parent of the child of the removed node to the parent of the removed node.
• If we delete a node with 2 children, we use hibbard deletion.
  • We want a new node to replace the deleted node. This node muts be greater than all nodes in the left subtree, and less than all nodes in the right subtree.
  • We just either pick the greatest node in the left subtree or the least node in the right subtree.