Computer-Science

Trees

An abstract model of a hierarchical structure

• 1. Tree
• 2. Binary Tree
• 3. Traversal
  • (1) Preorder Traversal
  • (2) Postorder Traversal
  • (3) Inorder Traversal
  • (4) Euler Tour Traversal
• 4. Arithmetic Expression Tree

1. Tree

Terminology

Terminology	Explain	Example
Root	node without parent	A
Child	if node u is the parent of node v, v is a child of u	except A
Internal node	node with at least one child	A, B, C, F
External node (=Leaf)	node without children	E, I, J, K, G, H, D
Ancestors of a node	parent, grandparent, great-grandparent, etc.
Siblings of a node	Any node which shares a parent
Depth of a node	number of ancestors (노드의 속성)	K의 경우, A, B, F이므로 3
Height of a tree	maximum depth of any node (트리의 속성)	3
Descendant of a node	child, grandchild, great-grandchild, etc.
Subtree	tree consisting of a node and its descendants (부분집합 같은 개념)
Degree	number of children of a node (트리의 속성)	F의 경우, I, J, K이므로 3
Edge	a pair of node (u, v) such that u is a parent of v((C, H))
Path	A sequence of nodes such that any two consecutive nodes form an edge	A, B, F, J
Ordered tree	a tree with a linear ordering defined for the children of each node

Tree ADT

We use positions to abstract nodes

• Generic functions:
  • integer size()
  • boolean empty()
• Accessor functions:
  • position root()
  • list<position> positions()
• Position-based functions:
  • position p.parent()
  • list<position> p.children()
• Query functions:
  • boolean p.isRoot()
  • boolean p.isExternal()
• Additional update functions may be defined by data structures implementing the Tree ADT

Linked Structure for Trees

• A node is represented by an object storing
  • Element
  • Parent node
  • Sequence of children nodes
• Node objects implement the Position ADT
• The time complexities of the functions of an n-node linked tree structure
  • isRoot(): O(1)
  • isExternal(): O(1)
  • parent(): O(1)
  • p.children(): O(c_p)
  • size(): O(1)
  • empty(): O(1)
  • root(): O(1)
  • positions(): O(n)
• The space complexity: O(n)

Depth and Height

• Depth of a node: number of ancestors
  • Time complexity: O(dp) where dp ≤ n

Algorithm depth(T, p)
  if p.isRoot()
    return 0
  else
    return 1+depth(T,p.parent())

• Height of a tree: maximum depth of any node
  • Time complexity: O(n)

Algorithm height(T, p)
  if p.isExternal()
    return 0
  else
    h=0
    for each q ∈ p.children()
      h = max(h,height(T,q))
    return 1+h

2. Binary Trees

• A binary tree is a tree with the following properties:
  • Each internal node has at most two children (exactly two for proper binary trees)
  • The children of a node are an ordered pair
• We call the children of an internal node left child and right child
• Are cursive definition
  • A binary tree is either empty or consists of:
    • A node r,called the root of T and storing an element
    • A binary tree, called the left subtree of T
    • A binary tree, called the right subtree of T
• Applications:
  • arithmetic expressions
  • decision processes
  • searching

Properties of Binary Trees

• Notation
  • n: number of nodes
  • n_E: number of external nodes
  • n_I: number of internal nodes
  • h: height
• Properties for a non empty binary tree T:
  • 

Binary Tree ADT

• The Binary Tree ADT extends the Tree ADT
• Inherits all the methods of the Tree ADT
  • isRoot() isExternal() p.parent() p.children() size() empty() root() positions()
• Additional position methods:
  • position p.left()
  • position p.right()
• Update methods may also be defined by data structures implementing the Binary Tree ADT
• Proper binary tree: Each node has either 0 or 2 children (otherwise improper)

Linked Structure for Binary Trees

• Assuming a proper binary tree
• A node is represented by an object storing
  • Element
  • Parent node
  • Left child node
  • Right child node
• Node objects implement the Position ADT

Binary Tree Update Functions

• Provide the means to build and modify trees

  • addRoot(): Add a root to an empty tree
  • expandExternal(p): Create two new external nodes and making them the left and right children of p
  • removeAboveExternal(p): Remove the external node p together with its parent q, then replace q with the sibling of p

• An example operation of removeAboveExternal(w)

  • 

Vector-Based Structure of Binary Trees

• Level numbering of nodes in a binary tree T
  • If v is the root of T, then f(v)=1
  • If v is the left child of node u, then f(v)=2f(u)
  • If v is the right child of node u, then f(v)=2f(u)+1
  • This numbering may skip some numbers
    • ex> 8, 9는 없다. 나중에 들어올 값을 위해, 자리를 비워두는 의도도 있다.

• A vector-based representation of a binary tree T
  • Node v is associated with the element of a vector S at f(v)
  • The vector S has size (N=f_M+1<=2^n-1)
    • f_M: the maximum value of f(v)
    • +1의 이유: 0번 index도 포함되기 때문
    • n은 노드의 개수
  • Implement using an extendable array
  • h와 n의 관계: height가 node가 됨

Performance of Binary Tree Implementations

• Linked structure vs. vector
  • Both have the same time complexity
  • Space complexity
    • Linked structure: O(n)
    • Vector: O(2^n)

3. Traversal

• A traversal visits the nodes of a tree in a systematic manner
• search 랑은 다르다. (모든 node들을 찾아가는 규칙)

(1) Preorder Traversal

• In a preorder traversal, a node is visited before its descendants
• Application: print a structured document

Algorithm preOrder(T,p)
  visit(p)
  for each child q of p
    preOrder(T,q)

Exercise

Result :

A B E F I J K C G H D

(2) Postorder Traversal

• In a post order traversal, a node is visited after its descendants
• Application: compute space used by files in a directory and its subdirectories

Algorithm postOrder(T,p)
  for each child q of p
    postOrder(T,q)
  visit(p)

Exercise: Postorder Traversal

• In a post order traversal, a node is visited after its descendants
• List the nodes of this tree inpost order traversal order.

Result :

E, I, J, K, F, B, G, H, C, D, A

(3) Inorder Traversal

• In an inorder traversal, a node is visited after its left subtree and before its right subtree
• Application: draw a binary tree
  • x(v) = inorder rank of v
  • y(v) = depth of v

Algorithm inOrder(T,p)
  if not p.isExternal()
    inOrder(T,p.left())
  visit(p)

  if not p.isExternal()
    inOrder(T,p.right())

Exercise: Inorder Traversal

• In an inorder traversal a node is visited after its left subtree and before its right subtree
• List the nodes of this tree in inorder traversal order.

Result :

D, B, H, E, I, A, F, C, G

(4) Euler Tour Traversal

• Generic traversal of a binary tree
• Includes as special cases the preorder, postorder and inorder traversals
• Walk around the tree and visit each node three times:
  • on the left (preorder)
  • from below (inorder)
  • on the right (postorder)
• 한붓그리기 느낌

Algorithm eulerTour(T,p)
  visit(p) on the left // preOrder
  if not p.isExternal()
    eulerTour(T,p.left())
  visit(p) from below // inOrder
  if not p.isExternal()
    eulerTour(T,p.right())
  visit(p) on the right // postOrder

Exercise

Result :

+ X 2 2 2 X - 5 5 5 - 1 1 1 - X + X 3 3 3 X 2 2 2 X +

4. Arithmetic Expression Tree

• Binary tree associated with an arithmetic expression
• Internal nodes: operators
• Leaves: operands

Exercise

Result :

(2X(a-1))+(3Xb)

Print Arithmetic Expressions

1) Inorder traversal

• Specialization of an inorder traversal (수식작성에 효과적)
  • print operand or operator when visiting node
  • print ( before traversing left subtree
  • print ) after traversing right subtree

Algorithm printExpression(T,p)
  if not p.isExternal()
    print("(")
    inOrder(T,p.left())
  print(p.element())
  if not p.isExternal()
    inOrder(p.right())
    print (")")

Exercise

Result :

((2X(a-1))+(3Xb))

2) Euler Tour traversal

• Specialization of an Euler Tour traversal (inorder와 기능적으로 크게 차이는 없음)
  • Left-visit: if node is internal, print (
  • Bottom-visit: print value or operator stored at node
  • Right-visit: if node is internal, print )

Algorithm printExpEuler(T,p)
  if not p.isExternal()
    print(p.element())
  else
    print("(")
    printExpEuler(T,p.left())
    print(p.element())
    printExpEuler(T,p.right())
    print (")")

Evaluate Arithmetic Expressions

• Specialization of a postorder traversal (계산 수행에 효과적)
  • recursive method returning the value of a subtree
  • when visiting an internal node, combine the values of the subtrees

Algorithm evalExpr(T,p)
  if p.isExternal()
    return p.element()
  else
    x ← evalExpr(T, p.left())
    y ← evalExpr(T, p.right())
    ♢ ← operator stored at p
    return x ♢ y

Exercise

• Draw an expression tree that has
  • Four leaves, storing the values 1,5,6, and 7
  • 3 internal nodes, storing operations +,-,*,/
    • operators can be used more than once, but each internal node stores only one
  • The value of the root is 21

Result :

This site is open source. Improve this page.