CITS2200 - Lecture 15

← Back to Home

CITS2200 - Lecture 14
Trees - Slides

Trees

• A tree is an abstract model of a hierarchial structure
• Consists of nodes connected by a parent-child relationship
• Applications in file systems, organisation charts, decision trees, etc.

Key idea: Unlike arrays/lists which are linear, trees are hierarchical $-$ one root, branching downward

Tree Terminology

Term	Definition
Root	Node without a parent (only one)
Internal node	Node with at least one child
External node (leaf)	Node with no children
Depth of a node	Number of ancestors it has
Height of a tree	Maximum depth of any node
Subtree	A node and all of its descendants
Ancestor	Parent, grandparent, etc.
Descendant	Child, grandchild, etc.

Tree ADT

• Positions are used to abstract nodes
  • The actual file data = node
  • The file path or file handle (reference to node) = position
• With positions, you are just accessing data and can’t accidentally break the tree structure
  • Essentially, while you are using your ‘nodes’ you aren’t modifying the tree structure and are just using references

Generic methods:

• len() — number of elements
• is_empty() — True if tree is empty
• positions() — iterate all positions
• iter() — iterate all elements

Accessor methods:

• root() — return position of root
• parent(p) — return parent of position p
• children(p) — iterate children of p
• num_children(p) — count children of p

Query methods:

• is_leaf(p) → num_children(p) == 0
• is_root(p) → root() == p

Update method:

• replace(p, o) — replace element at position p with object o

---

Tree Traversal

• A traversal visits every node in a tree in a systematic order

Preorder Traversal

• Visit node before its descendants
• Algorithm: visit(v) → for each child w: preorder(w)
• Use case: Print a structured document (e.g. table of contents)

Postorder Traversal

• Visit node after its descendants
• Algorithm: for each child w: postorder(w) → visit(v)
• Use case: Compute disk space used by files in a directory (need children sizes

---

Binary Trees

• A binary tree is a tree with these properties:
  • Each internal node has at most two children
  • Children are an ordered pair → called left child and right child
• A proper binary tree has exactly two children per internal node

Binary Tree ADT extends Tree ADT with:

• left(p) — return left child of p
• right(p) — return right child of p
• sibling(p) — return the sibling of p

Applications:

• Arithmetic expressions → internal = operators, external = operands

  

• Decision processes → internal = yes/no questions, external = decisions

  

• Searching

Inorder Traversal (Binary Trees only)

• Visit node after left subtree and before right subtree
• Algorithm:
  1. if v has left child: inOrder(left(v))
  2. visit(v)
  3. if v has right child: inOrder(right(v))
• Use case: Draw a binary tree
  • x-position = inorder rank, y-position = depth

---

Properties of Proper Binary Trees

Notation	Meaning
n	total number of nodes
e	number of external nodes (leaves)
i	number of internal nodes
h	height of tree

Key properties:
$e=i+1\text{(one more external than internal nodes)}$
$n=2e-1$
$h\le i\text{and}h\le \frac{n-1}{2}$
$e\le 2^h\text{and}h\ge {\log }_{2}e\text{and}h\ge {\log }_2(n+1)-1$

Height constraint: $h\ge log{}_2(n+1)-1$ → height grow slowly, binary search trees highly efficient

---

CITS2200 - Lecture 16