Tree Data Structure

Table of Contents

Trees

  1. Collection of nodes
    1. One specialized node is the root.
    2. A node has one parent (unless it is the root)
    3. A node has zero or more children. Each node can have any number of children.
  2. Real-world “trees”:
    1. Organizational hierarchies
    2. Some family trees
  3. Some uses:
    1. Directory structure on a hard drive
    2. Sorted collections
Operations Provided Efficiency (only if the tree is balanced)
Find O(log n)
Add/remove O(log n)

TODO

  1. depth first searches
  2. breadth first searches

Links to this note