Introduction to Algorithms - Lecture 6: Binary Trees, Part 1

This post is a derivative from Introduction to Algorithms of MIT OpenCourseWare, used under CC BY-NC-SA 4.0.

You can watch this lecture on Youtube and see PDF.

Previously and New Goal

---

How? Binary Trees!

What is a binary tree?

• Pointer-based data structures (like Linked List) can achieve worst-case performance
• Binary tree is pointer-based data structure with three pointers per node
• Node representation: node.{item, parent, left, right}

Terminology

• root—has no parent
• leaf—has no child
• subtree
• depth—# ancestors = # edges in path up to root
• height—# edges in longest downward path = max depth in subtree
• traversal order (in order)

---

Tree Navigation

• subtree_first(node)
  • among all the nodes in the subtree, which comes first in traversal order within subtree - the leftmost leaf
  • Go left (node = node.left) until would fall off tree (node = None) and return node
• successor
  • next after node in the overall tree’s traversal order
  • if node.right: return subtree_first(node.right)
  • else walk up tree (node = node.parent) until we go up a left branch (node == node.parent.left) and return node

How long do these operations take? — O(h). These are fast if h is small like log n. Whereas if I had to update the explicit traversal order say as an array, I would have to spend linear time every time I make a change.

Dynamic Operations

• subtree_insert_affter(node_new)
  • if no node.right, put new there
  • else put new as successor(node).left
  • O(h)
• subtree_delete(node)
  • if node is leaf, detach from parent
  • if node.left
    • swap node.item <-> predecessor(node).item
    • subtree_delete(predecessor)
  • if node.right
    • swap node.item <-> successor(node).item
    • subtree_delete(predecessor)

---

Sequence and Set

How we take these trees and implement a set or sequence?

Sequence

• traversal order = sequence order

Set (Binary Seach Tree / BST)

• traversal order = increasing item.key
• find(k)