Outline

• binary search trees
• binary node class
• binary search tree algorithms: add, delete, traverse
• binary tree traversal
• heaps
• heap storage in arrays
• heap insertion and removal
• priority queues
• priority queues implementation

binary search trees

image by Derrick Coetzee and Booyabazooka, in entry " Binary search tree" in Wikipedia
• in-class exercise: how do we know this is a binary search tree?
• compared to binary search in an array, binary search in a binary search tree is easier. Algorithm to search for value x.
  • if the value in the root is x, we are done
  • otherwise, if x < the value in the root, search (recursively) in the left subtree
  • otherwise, x > the value in the root, so search in the right subtree
  • if the subtree we need to search is empty, x is not in the tree
• in-class exercise: what is the runtime of this algorithm?

Binary search tree properties

• adding, finding (get), or removing a node are all O(depth), which, if the tree is balanced, is O(log n), with n the number of nodes
• compare to a sorted array, where binary search means finding is always O(log n), but inserting is O(n)
• binary search trees are an efficient way to search data and to sort data, as long as the trees remain balanced
• an unbalanced binary tree might look like a linked list
• in-class exercise: what is the runtime of the get method when the tree is not balanced?
• data can be identified with a unique key
• in-class exercise: add everyone's name to a search tree (in groups of five-ten people)
• in-class exercise: is the resulting tree balanced?

Binary node class

• a singly-linked list node has (at most) one reference to another node
• a binary tree node has (at most) two references to other nodes
• for example, see here
• both types of nodes also need a reference to the locally stored value
• data fields are item, left, right
• methods include constructors, accessor methods, mutator methods, toString
• test program builds small tree, tests the methods
• in-class exercise: build the following tree using the methods from class BinaryNode
• binary nodes can be used for binary search trees, but also for other kinds of binary trees

Binary search tree add operation

• if key is less than the key of the current node, recursively add to the left subtree
• if key is greater than the key of the current node, recursively add to the right subtree
• otherwise, add at this node:
  • if there is no current node, create one and return it
  • if there is a current node, replace its contents with the new contents
• this assumes:
  • the method returns a new root for the new (sub)tree with the desired value inserted
  • the caller of this method knows what to do with the new root
• in-class exercise: create a new binary tree using as keys the following letters, in the order given: "hello world". These keys each carry the value 1, 2, 3, 4, 5, 6, 7 8, 9, 10, 11

Binary search tree delete operation

• find node with the given key
• if the node is a leaf node, just delete it, return null
• if the node only has a left subtree, return the left subtree
• if the node only has a right subtree, return the right subtree
• if the node has both subtrees, must replace it with another node that fits in the slot

Removing a node that has both subtrees

• the rightmost node in the left subtree can be put in place of the current node without altering the sorted property
• likewise, the leftmost node in the right subtree can be put in place of the current node
• that node might have a left (right) subtree, which can be used in its old position
• the rightmost node in the left subtree is the inorder predecessor of the current node
• the leftmost node in the right subtree is the inorder successor of the current node
• so either can be used
• in-class exercise: delete node 17 from this tree:
• in-class exercise (individually): delete node 14 from the original tree
• in-class exercise (individually): delete node 31 from the original tree

binary tree traversal

• binary tree traversal is easy using recursion:
  • preorder: visit the root node, then recursively visit the left subtree, then recursively visit the right subtree
  • inorder: recursively visit the left subtree, then visit the root node, then recursively visit the right subtree
  • postorder: recursively visit the left subtree then recursively visit the right subtree, then visit the root node
• this is hard using just loops
• a stack is needed to keep track of where we are in the tree
• for example, for preorder traversal, I would visit (print, etc) the current node, push onto the stack the right subtree, then visit the left subtree
• when I reach a leaf node, I pop the next subtree off the stack, and continue from that node
• inorder and postorder are more complex
• this can also be done without a stack if the nodes have parent references, and then it is similar to backtracking

Heaps

• a heap is a binary tree (but not a binary search tree)
• in which each node has a value less than its children (min heap)
• or a value greater than its children (max heap)
• this is the heap property
• so nodes in a heap are not sorted

heap requirements

• as well as the heap property of each node needing to be less (greater) than its children,
• in a heap, all leaves at maximum depth d_max are to the left of all the other leaves, which are at depth d_max - 1
• in-class exercise: is this a max or a min heap?
• such a binary tree (all leaves at max depth to the left of all other leaves, which are at depth d_max - 1) is called a complete binary tree
• a heap is always a complete binary tree
• a complete binary tree is always balanced, so that a complete binary tree of n nodes has depth O(log n)
• in-class exercise: in what sense can I say that a complete binary tree is balanced?

heap storage

• any complete binary tree, including any heap, can be conveniently stored in an array:
  • element 0 of the array stores the root
  • elements 1 and 2 of the array store the nodes at depth 1
  • elements 3, 4, 5, and 6 of the array store the nodes at depth 2
  • nodes at depth d are stored in array elements 2^d-1...2^d+1 - 2
• conveniently, there is no need to store any pointers: a node stored in array element i has:
  • its parent in array element (i - 1) / 2
  • its left child (if any) in array element 2i + 1
  • its right child (if any) in array element 2i + 2
• since a heap is a complete binary tree, the right child can only be present if the left child is also present (there may be one left child leaf node that does not have a right sibling)

in-class exercises

• store this heap into an array
• which of the following arrays store max heaps, min heaps, or neither?

  index     0   1   2   3   4   5   6   7   8   9
  array 1   0   1   2   0   4   5   6   7   8   9
  array 2   9   8   7   6   5   4   3   2   1   0
  array 3   5   5   5   6   6   6   6   7   7   1
  array 4   9   3   9   2   1   6   7   1   2   1
  array 5   8   7   6   1   2   3   4   2   1   2
  

Heap insertion

• the two heap requirements must be maintained when adding to a heap
• to maintain the complete binary tree property, the new node must be added to the right of all nodes at depth d_max
• or, if there already are 2^(d_max) nodes at that level, the new node should be inserted all the way to the left, making the tree deeper by one level
• either way, the new value is inserted in the array just after all elements already in the array
• now the tree is complete, but may not have the heap property
• to check, compare the node with the parent, and swap the two if needed to maintain the heap property
• continue with the parent's parent, all the way to the root if necessary
• now the complete binary tree also obeys the heap property

Max heap deletion

• the largest node is at the root of the heap
• that node is deleted, and replaced with the bottommost, rightmost node
• the remaining tree is complete, but may not have the tree property
• if the root node is less than either of its children, it is swapped with the largest of its children
• the operation continues with the new node
• now the complete binary tree also obeys the heap property
• similarly for min heaps

in-class exercises

• insert into a heap the following values:
  1 9 77 14 3 55 66 7 8
• remove from the heap each of the elements in turn

priority queues

• the queues studied so far were strictly FIFO
• that means objects were returned in the order inserted
• in the real world, often have priorities, e.g.:
  • at airport check-in, there is a special line for first-class passengers
  • if any first-class passengers are waiting, they are handled first
  • only if no first-class passengers are waiting, only then the other passengers can check-in
• likewise in the emergency room at a hospital or after a disaster
• the process of determining which patients should be seen first is called triage (a medical term, not a computer science term)

priority queue implementations

• linked list: objects are inserted in the proper place in the list (linear time), objects are returned from the front of the list (constant time)
• array: objects are inserted in the proper place in the array, with all other objects shifted to make room (linear time), objects are returned from the front of the array, with all other objects shifted down (linear time), or maintained as a circular array (constant time)
• binary search tree: objects are inserted into the binary search tree, using the priority as the key (log or linear), objects are removed from the rightmost node of the tree (log or linear)
• heap: objects are inserted into the heap using the priority as the key (log time), and removed from the top of the heap (log time)