Tree 1

Concept

• Consist of nodes and linkes denoting parent-child relation.
• Special case of graphs with a hierarchical structure but without loops.
• Each elemept except root has a parent and zero or more children.

Terminology

• Root : Node without a parent.
• Leaf : Node without children.
• Internal Node : Node with at least one child.
• Depth (of a node) : Number of ancestors.
• Height (of a node) : Number of edges to the node from a leaf.
• Subtree : A part of trees consisting of a node and its descendants.

Tree implementation

• Typically done with linked-lists.
• With arrays in some special cases.

---

Tree Abstract Data Type

Data Structure

• Node : Data element and link to children.
• Root : A special Node.

List of Methods

• root() : return tree's root, error if tree is empty.
• parent(v) : return v's parent; error if v is a root.
• children(v) : return v's children (an iterable collections of nodes).
• isRoot(v) : Test whether v is a root.
• isExternal(v) : Test whether v is an external node.
• isInternal(v) : Test whether v is an internal node.
• isEmpty() : Test whether the tree has any nodes or not.
• size() : return the # of nodes in the tree.

---

Binary trees

Definition

• A tree in which each node has at most two children.
• Each child is either the left child or the right child of its parent.

• Arithmetic Expression Tree
  • Internal nodes : operators
  • External nodes : operands
• Decision Tree : Binary tree associated with a decision process
  • Internal nodes : questions with yes/no answer
  • External nodes : decisions

A Linked Structure for Binary Trees

A node is represented by an object storing

• Element, Parent node, Left child node, Right child node

  tree에서는

  element, parent node, sequence of children nodes를 갖고 있었다면

  binary tree에서는

  element, 'parent node, left child node, 'right child node를 갖고 있다.

An array-based representation

• Basic idea : Each node has up to 2 children and can be mapped with a particular location in an array.

rank(root) = 1
left in even -> rank(node) = 2 * rank(parent(node))
right in odd -> rank(node) = 2 * rank(parent(node)) + 1

!!! A[0] is always empty !!!
!!! A[i] is empty if there's no node in the i-th position !!!

---

Tree balance

• Perfect Binary Tree

  • A binary tree of height h is perfect if every node has exactly two children and all leaf nodes have the same level(depth), which leads to 'full binary tree'.

• Complete Binary Tree

  • A binary tree is complete if it is full to level h-1 and level h is filled from the left with contiguous nodes.
  • The full binary tree is a special case of complete binary tree.

• Proper Binary Tree

  • A binary tree in which each node has exactly zero or two children.
  • The full binary tree is a special special case of proper binary tree.

---

Proper Binary Trees

• By def, each internal node has exactly two children.
• Properties

e = i + 1
n = 2e - 1
h <= i
h <= (n-1)/2
e <= 2^h
h >= log_2(e)
h >= log_2(n+1) - 1