WEEK 10

Trees cont.

• Binary trees cont.
  • Review
    • Binary trees
    • Define classes for node and tree
    • Inorder, postorder, preorder traversals
  • Deleting a node
    • Draw pictures
    • Four cases to consider

1.      root is null

2.      deleting root

o       with no left node

o       with

3.      deleting a node with no left node

4.      deleting node (want to move up rightmost of left side or leftmost of right side to take this place)

• Do algorithms for delete 4 cases

o       Need to have a pointer to the parent node

o       Deleting once we’ve found the node:

1.      return true

2.      root = root.right
or replace with left rightmost

3.      if (ptr == parentptr.left)

parentptr.left = ptr.right;

                                                else

                                                            parentptr.right = ptr.right;

4.      ptr.data = ptr.left.getrightmostdata();

ptr.left = ptr.left.removerightmost();

·        Performance

• Objects are expensive (new and constructors)
  • Show how to store and allocate data
  • Doubly linked lists for auditing
• Methods are expensive
• Recursion is expensive
• Do tree insertion without recursion
• Do tree find without recursion
• Do remove rightmost without recursion
• Tree traversal without recursion
  • Put in pointers to parent
  • Threaded trees

·        Time analysis

• Review why O(log n)
• Review what happens to run time for O(1), O(n), O(n²), O(log n) if n doubles, quadruples, etc.