KECE208

Data Structures and Algorithms

- Tree -

담당교수: 황 인준

School of Electrical Engineering

Korea University

2020-09-23 Weiss, Data Structures & Alg's 1

 Trees (Chap. 4)

Weeks 5-6
Fall 2016

School of Electrical Engineering

Korea University

2020-09-23 Weiss, Data Struct's & Alg's 2

 Chap 4: Trees
• Access time is O(N) for linked lists.
• If N >> 1, faster access method is needed.

• We can get O(log N) access time for trees.

• Non-linear structure.

2020-09-23 Weiss, Data Struct's & Alg's 3

 Recursive definition
• A tree is a collection of nodes.
• The collection can be empty.
• Otherwise, a tree consists of a distinguished
node r, called the root, and zero or more
nonempty (sub)trees T1, T2, …, Tk, each of
whose roots are connected by a directed
edge from r.
• The root of each subtree is said to be a
child of r, and r is the parent of each
subtree root.
2020-09-23 Weiss, Data Structures & Alg's 4
 Generic tree and example

2020-09-23 Weiss, Data Structures & Alg's 5

 Terms of Trees
• Root, leaf, parent, children, grand-*, sibling
• Path from n1 to nk: a sequence of nodes n1, n2,
…, nk such that ni is the parent of ni+1
• Length of a path: the number of edges on the
path
• The depth(level) of a node: the length of the
path from the root to the node.
• The height of a node: the length of the longest
path from the node to a leaf
• The height of a tree: the height of the root

2020-09-23 Weiss, Data Struct's & Alg's 6

 Properties of Trees
• No loops
• Unique path between two nodes
• Every node except the root has one parent
• N-1 edges for an N node tree. How?

2020-09-23 Weiss, Data Struct's & Alg's 7

 Tree ADT
• Operations
– Parent(n) A

– Leftmost-child(n)
– Right-sibling(n) B C D

– Depth(), Height()
E F G
– makeEmpty()
– isEmpty() J
H I
– Preorder( )
– Postorder( )
– Inorder( )
8
 Example

• The length of path AEJQ is 3

• E is at depth 1 and height 2
• F is at depth 1 and height 1
• The height of the tree is 3

2020-09-23 Weiss, Data Structures & Alg's 9

 Implementation 1
typedef struct TreeNode *PtrToNode;
struct TreeNode
{
ElementType Element;
PtrToNode Child1;
PtrToNode Child2;
…
} Any problem?

2020-09-23 Weiss, Data Structures & Alg's 10

 Implementation 2
typedef struct TreeNode *PtrToNode;
struct TreeNode
{
ElementType Element;
PtrToNode FirstChild;
PtrToNode NextSibling;
}

2020-09-23 Weiss, Data Structures & Alg's 11

 Two implementations together!

2020-09-23 Weiss, Data Structures & Alg's 12

 Tree Traversal Application

- Unix directory -

2020-09-23 Weiss, Data Structures & Alg's 13

 Routine to list a directory

2020-09-23 Weiss, Data Structures & Alg's 14

 Preorder directory listing

2020-09-23 Weiss, Data Structures & Alg's 15

 Preorder directory listing

2020-09-23 Weiss, Data Structures & Alg's 16

 Unix directory with file sizes

2020-09-23 Weiss, Data Structures & Alg's 17

 Routine to calculate the dir size

2020-09-23 Weiss, Data Structures & Alg's 18

 Trace of SizeDirectory

2020-09-23 Weiss, Data Structures & Alg's 19

 BTs: Binary Trees
• At most two children: left_child, right_child
• Full BT
• Complete BT
• height = log N  for N node full BT
min = log N  ,
max = N-1

2020-09-23 Weiss, Data Struct's & Alg's 20

 Binary Tree

Generic binary tree Skewed tree

2020-09-23 Weiss, Data Structures & Alg's 21

 Properties of Full BTs
h

• N=      
k 1 2 3 h
2 1 2 2 2 ... 2 (height=h)
k 0
h 1
2 1
  2 h 1  1
2 1

• No. of non-leaf nodes = 2h 1

No. of leaf nodes = 2h

• N + 1 = 2h1 h  log N 

2020-09-23 Weiss, Data Struct's & Alg's 22

 Full binary tree

2 3

4 5 6 7

8 9 10 11 612 13
16 14 15

2020-09-23 Weiss, Data Structures & Alg's 23

 BT implementation
typedef struct TreeNode *PtrToNode;
typedef PtrToNode BinaryTree;

struct TreeNode
{ ElementType Element;
Tree Left;
Tree Right;
};

2020-09-23 Weiss, Data Struct's & Alg's 24

 Recursions for Binary Trees
void PrintTree(BinaryTree T)
{ //Inorder traversal
if (T != NULL) {
PrintTree(T-> Left);
PrintElement(T-> Element);
PrintTree(T-> Right);
}
}

2020-09-23 Weiss, Data Struct's & Alg's 25

 Recursions for Binary Trees
int Height(BinaryTree T) {
if (T == NULL)
return –1;
else
return 1 + Max(Height(T-> Left), Height(T->
Right));
}

2020-09-23 Weiss, Data Struct's & Alg's 26

 Inorder Binary Tree traversals

void INORDER(T)
{ 1

if(T is null)
2 3
return;

4
INORDER(T-> Left); 5 6
print(T-> Element);
INORDER(T-> Right); 7
}

2020-09-23 Weiss, Data Struct's & Alg's 27

 Binary Tree traversals

void PREORDER(T)
{ 1
if(T is null)
return; 2 3

print(T-> Element); 4
5 6
PREORDER(T-> Left);
PREORDER(T-> Right);
7
}

2020-09-23 Weiss, Data Struct's & Alg's 28

 Binary Tree traversals

void POSTORDER(T)
{ 1
if(T is null)
return; 2 3

POSTORDER(T-> Left); 4
5 6
POSTORDER(T-> Right);
print(T-> Element);
7
}

2020-09-23 Weiss, Data Struct's & Alg's 29

 Tree Traversal: Preorder
Preorder(1)
print 1
Preorder(2)
1 print 2
Preorder (5)
2 3 print 5
Preorder (6)
print 6
5 6 4 Preorder(3)
print 3
Preorder (4)
7 print 4
Preorder (7)
print 7

30
 Tree Traversal: Postorder
Postorder(1)
Postorder(2)
Postorder (5)
1 print 5
Postorder (6)
3 print 6
2
print 2
Postorder (3)
5 6 4 Postorder (4)
Postorder (7)
print 7
7 print 4
print 3
print 1

31
 Tree Traversal
1 Postorder traversal

2 3 start start
POST(2) POST (2)
4
POST(5) POST (5)
5 6 print 5 print 5
POST(6) POST (6)
print 6 print 6
7 print 2 print 2
indent
void POST(T){ POST(3) POST (3)
POST(4) POST (4)
if(T is null) POST(7) POST (7)
return; print 7 print 7
POSTORDER(T-> Left); print 4 print 4
POSTORDER(T-> Right); print 3 print 3
print(T-> Element); print 1 print 1
end end
}
32
 Tree Traversal
1

2 3

6 4
5

Inorder traversal => 5 2 6 1 3 7 4

Preorder traversal => 1 2 5 6 3 4 7
Postorder traversal => 5 6 2 7 4 3 1

33
 Expression Trees
Expression tree for
(a + b * c) + ((d * e + f) * g)

2020-09-23 Weiss, Data Structures & Alg's 34

 Postfix to expression tree
a b c d

+ +
ab+cd-*
a b a b

+ - *
+ -
a b c d
a b c d

35
 Expression Trees
(a + b * c) + ( ( d * e + f ) * g)
Postfix
=> a b c * + d e * f + g * +

2020-09-23 Weiss, Data Structures & Alg's 36

 Binary Search Trees
• Keys – stored data in the node
• Key order(larger, smaller)
• For any node v in T,
values in the left subtree – smaller
values in the right subtree – larger
• Used to store and retrieve data efficiently &
dynamically (sort, matching, …)
• Need fast access? Make it balanced!

2020-09-23 Weiss, Data Struct's & Alg's 37

 Two binary trees – which one is BST?

6 6

8 2 8
2

1 4 1 4

3 3 7

2020-09-23 Weiss, Data Structures & Alg's 38

 Binary search tree declaration
typedef int ElementType;

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty( SearchTree T );

Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );
ElementType Retrieve( Position P );

2020-09-23 Weiss, Data Struct's & Alg's 39

 To make an empty tree
struct TreeNode {
ElementType Element;
SearchTree Left;
SearchTree Right;
};

Element

2020-09-23 Weiss, Data Struct's & Alg's 40

 To make an empty tree
SearchTree MakeEmpty(SearchTree T) {
if(T != NULL) {
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free( T );
}
return NULL;
}

2020-09-23 Weiss, Data Struct's & Alg's 41

 Functions in BSTs
• Find (X,T) returns the pointer of node that has X.

• Insert (X,T) does nothing if X is already there.

Otherwise, add X at the right place.

• FindMin(T) / FindMax(T) return the minimum /

maximum in the BST T (leftmost/rightmost).

• Delete(X,T) deletes X and reconstructs the tree

if necessary (hard).

2020-09-23 Weiss, Data Struct's & Alg's 42

 Find on binary search tree
Position Find(ElementType X, SearchTree T)
{
if(T == NULL)
return NULL;
if(X < T->Element)
return Find(X, T->Left);
else if(X > T->Element)
return Find(X, T->Right);
else
return T;
}

2020-09-23 Weiss, Data Struct's & Alg's 43

 FindMin (recursive)
Position
FindMin(SearchTree T) 7
{
if(T == NULL) 1 13
return NULL;
else
4 9 20
if(T-> Left == NULL)
return T;
else 16
return FindMin(T->Left);
}

2020-09-23 Weiss, Data Struct's & Alg's 44

 FindMax (nonrecursive)
Position
7
FindMax(SearchTree T)
{ 1 13
if(T != NULL)
while(T->Right!=NULL)
T = T->Right; 4 9 20

return T; 16
}

2020-09-23 Weiss, Data Struct's & Alg's 45

 Insert in BST
• Insert(X,T) – Find(X,T)를 6, 14
실행했을 때, X가 자리잡고 7
있어야 할 지점을 찾은 후
그 위치에 새로 노드를 생 1 13
성해 삽입함.

4 9 20

16

2020-09-23 Weiss, Data Structures & Alg's 46

 Insert in BST

1 13
Where to insert 6?
4 9 20 Where to insert 14?

16

2020-09-23 Weiss, Data Structures & Alg's 47

 Insert in BST

7 7

1 13 1 13
6, 14
4 9 20 삽입 4 9 20

16 6 16

14

2020-09-23 Weiss, Data Structures & Alg's 48

 More example

Insert 5

2020-09-23 Weiss, Data Structures & Alg's 49

 More example

Insert 5

2020-09-23 Weiss, Data Structures & Alg's 50

 SearchTree Insert(ElementType X, SearchTree T) {
/* 1*/ if(T == NULL) {
/* Create and return a one-node tree */
/* 2*/ T = malloc(sizeof(struct TreeNode));
/* 3*/ if(T == NULL)
/* 4*/ FatalError("Out of space!!!");
else {
/* 5*/ T->Element = X;
/* 6*/ T->Left = T->Right = NULL; }
} else
/* 7*/ if(X < T->Element)
/* 8*/ T->Left = Insert(X, T->Left);
else
/* 9*/ if(X > T->Element)
/*10*/ T->Right = Insert(X, T->Right);
/* Else X is in the tree already; we'll do nothing */
/*11*/ return T; /* Do not forget this line!! */
}

2020-09-23 Weiss, Data Struct's & Alg's 51

 Delete in BST
• Delete(X,T) : 재귀함수(recursion)를 써서 구현함.
/* recursion 결과를 assign 하는 경우 매번 return
되는 값이 무엇인지 정확히 추적하여야 함 */

1 13

3 9 20

4 8 16

2020-09-23 Weiss, Data Struct's & Alg's 52

 Delete in BST
SearchTree Delete( ElementType X, SearchTree T ) {
if ( T == NULL) Error(“Element not found”);
else if ( X < TElement )
T->Left = Delete( X, TLeft);
else if (X > TElement )
T->Right= Delete( X, TRight);
else if ( TLeft && TRight ) /* Two children */
{ TElement = findMin( TRight )Element;
T Right = Delete(TElement, TRight ); }
else
{ old = T;
T = (Tleft != NULL)? TLeft : TRight;
free(old);
}
return T; }
2020-09-23 Weiss, Data Struct's & Alg's 53
 Delete Example

Delete 4

2020-09-23 Weiss, Data Structures & Alg's 54

 More Delete Example

Delete 3

2020-09-23 Weiss, Data Structures & Alg's 55

 More Delete Example
T A T A

6 6
B C B C

2 8 3 8
D E D E
Delete 2
1 5 1 5
F F
3 4
G

2020-09-23 Weiss, Data Structures & Alg's 56

 Delete Tracing
DL(2,A)
T A
A->Left = DL(2,B)
6 Tmp=FindMin(E) // F
B C B->Element = Tmp->Element
2 8
B->Right = DL(3,E)
D E E->Left = DL(3,F)
Tmp = F;
1 5 F = G;
F free(Tmp);
3 return G;
G return E;
return B
4
return A
2020-09-23 Weiss, Data Structures & Alg's 57
 Quiz
1. Give 3 traversal results for the tree below.
2. Write a function CntNodes(T) to count the number of
nodes in T

3. Insert 15, 12, 22, 9, 10, 13, 17, 25, 19 and 18 into an
initially empty binary search tree.
4. Delete 12 and 15 from the tree in (3)

2020-09-23 Weiss, Data Structures & Alg's 59

2020-09-23 Weiss, Data Struct's & Alg's 61
 Dynamic Properties
• 데이터(random)를 여러 차례 insert/delete 한 후
전체 트리의 형태 – unbalanced
- 바람직한 속성: depth = O(log N)

• Average-case analysis:
Average depth for N-node BST with random-data
insertion & deletion = O(log N)

2020-09-23 Weiss, Data Struct's & Alg's 62

 Balanced Trees
• 어느 위치에서도 좌우 균형을 항상 유지하는 경우
- depth = O(log N)

• 강제적인 균형유지 구조
- AVL(Adelson Valskii Landis) tree
- Splay tree: self adjusting tree

2020-09-23 Weiss, Data Struct's & Alg's 63