자구 6-2주차. 트리

linked structure 로 트리 구현

트리 class를 구현시 노드 구조체가 어떻게 생겼는가?

Node 구조체 구성

• 데이터 필드

• parent필드 : parent 노드형 포인터 (부모의 position을 담을 멤버)

• childern 시퀀스 필드 : childern노드형 포인터(position)들을 저장하는 시퀀스에 대한 포인터

  • 시퀀스는 보통 링크드리스트로 구현됨
  • 자식들의 position(노드형 포인터)들을 저장하고 있는 시퀀스의 주소값을 저장
  • 해당 시퀀스에서 첫번째 노드형 포인터에 대한 시작주소를 저장
  • 시퀀스의 각각의 position(노드형 포인터)들은 해당 자식 노드를 가리킴(해당 자식 노드의 주소값을 저장)

시퀀스의 형태

• 자식들에 대한 position들을 저장하고 있는 시퀀스를 어떤 자료구조로 구현해야 효율적일까?

1. 배열

• 미리 사이즈를 지정해야함

2. 벡터

• 사이즈가 알아서 커짐. 공간 낭비x

3. 링크드리스트

상세 분석

그림 예시)
1. root노드 구성요소

• 데이터 필드에 B를 저장
• parent 노드는 NULL 저장
• childern 노드의 position(노드형 포인터) 3개를 저장한 시퀀스의 주소를 저장(시퀀스를 가리킴)

2. 링크드리스트 형태로 구현된 시퀀스에 저장된 각각의 childern position들은 각각의 childern 시퀀스 노드 객체를 가리킴
   • 내 자식들의 position(주소값) 들을 링크드리스트 형태로 저장

3. 노드 A (데이터 A를 저장하는 노드)

• 데이터 A를 저장
• parent 노드형 포인터(parent position)는 노드 B의 주소를 저장(노드 B를 가리킴)
• childern이 없으므로 childern 시퀀스는 NULL이 된다

4. 노드 D

• 데이터 D를 저장
• parent가 B이므로 parent position은 B를 가리킴(B의 주소를 저장)
• childern들의 position에 대한 시퀀스의 포인터 : 크기가 2인 시퀀스의 시작 노드의 주소값을 저장
  • 시퀀스에서 2번째 노드형 포인터(position)은 노드 E에 대한 주소값을 저장(노드 E를 가리킴)

4. 노드 E

• 데이터 E를 저장
• parent 필드 : D의 주소값 저장
• 시퀀스 포인터 : 자식이 없으므로 NULL 저장

이진트리 복습

이진트리

• 모든 internal 노드의 자식의 개수가 0또는 1또는 2
• child이 ordered pair. left child와 right child 의 순서가 구분된다

proper binary tree : 자식의 개수가 0또는 2인 트리

활용분야 : 수식표현

• internal 노드 : 연산자 저장
• external 노드 : 피연산자 저장
  

Decision Tree (결정 트리)

• internal 노드는 질문사항(yes/no 포함)
• external 노드가 결정사항
  ex) 식사매뉴결정 - internal노드는 패스트푸트 먹을래?, 비싼거 먹을래? / external 노드는 스타벅스, 홍콩반점

Properities of Proper Binary Trees

• proper binay tree 의 특성

n : 총 노드의 수( internal 과 external 노드의 수를 합친것)
e : external 노드의 수
i : internal 노드의 수
h : 트리의 높이

proper 이진트리의 높이h 의 범위

• log2n <= h <= X

  • X : 입력개수
  • 그 이진트리의 최댓값은 X개가 된다. (데이터를 internal 노드에만 저장했을때)
  • 최소는 log2X 정도가 된다.
    ( 입력 개수로 i를 주는 경우가 많다 )

1. e = i + 1

   • internal 와 external는 개수가 1개 차이난다
   • 하나의 internal을 추가하기 위해선 external 노드를 제거하거나, 새로운 external 노드를 추가해야 하기때문

2. n = e + i

3. n = 2e-1

   • i = e-1 이므로, n=e+i 에서 i에다 e-1을 대입한 결과

4. n = 2i+1

   • 3번을 i에 대해서 풀어쓴거임

5. h <= i

   • 트리를 가장 높게 만들면, 높이는 internal 노드의 개수이다.
   • 최대로 internal 노드의 개수(= 최대 조상의 개수) 로 만들 수 있다.
   • 만들 수 있는 다양한 조합의 트리중에서, 자기 조상중에 internal 노드가 가장 많은 트리

6. h <= (n-1) / 2

   • 4번을 변형시키면 i = (n-1)/2 이므로, h <= i 에 (n-1) /2 를 대입한 결과이다.

7. e <= 2^h

8. h >= log2e

   • complete binary tree 로 구현했을 때가 트리의 높이가 가장 낮다.
   • ex) interanl 노드가 15개일때(=external 노드가 16개일때) 만들 수 있는 트리의 최소 높이는 log2e = log216 으로, 높이 4가 된다.

9. h >= log2(n+1) - 1

• 3번에서 n=2e-1 를 변형시키면 e=(n+1)/ 2 이므로,
  8번식 h >= log2e 의 e의 값에다 e=(n+1)/ 2 를 대입시킨 결과

BinaryTree ADT

메소드

• 트리의 모든 메소드를 상속받음

• position p.left()

• position p.right()

  • 어떤 노드의 position(주소값)이 p라면, 왼쪽 자식과 오른쪽 자식를 리턴받을 수 있다.
  • 즉 이터레이터(position) 을 이용해서 왼쪽,오른쪽 자식의 positiond을 리턴받을 수 있다.
  • 노드형 포인터를 position으로 한다면 왼쪽과 오른쪽 자식의 주소값을 리턴 받을 수 있다는 것

• 트리에서 하던 update 메소드를 이진트리에서도 가능

이진트리 구현 - linked structure로 구현

필드

• 데이터 필드
• parent 필드 (parent 노드형 포인터)
• left child 필드 (left child 노드형 포인터)
• right child 필드 (right child 노드형 포인터)

그림 분석

노드C

• data = C
• parent = D (노드 D의 position, 즉 주소를 저장)
• left child = NULL;
• right child = NULL;

Inorder Traversal(중위 순회)

• 이진트리는 전위순회와 후위순회는 몰론, 중위 순회까지 가능하다.
• 중위순회 : 자신 노드의 작업을 "중간" 에 처리하는 것

  처리순서
  1) 왼쪽에 Sub tree가 있다면, 왼쪽에 대해서 다 작업하고
  2) 자신을 작업하고
  3) 오른쪽 Sub tree에 대해 작업을 한다.
  => 왼쪽으로 계속 파고들다가 더이상 subtree가 없다면 현재 자기 트리를 처리하고 리턴

Algorithm inOrder(v)
  if ㄱv.isExternal()    // v가 external 노드가 아니라면 == 왼쪽자식이나 오른쪽 자식이 존재한다는 뜻
    inOrder(v.left())     // 왼쪽 subtree 대해서 먼저 중위순회를 해라!
  visit(v)                // 그러고 나서 나를 작업해라!
  if ㄱv.isExternal()         // 그러고 오른쪽에 대해서 중위순회를 해라
    inOrder(v.right())        

• 활용분야 : 이진트리를 좌표 평면에 겹치지 않게 그리기

v의 좌표 ( x(v), y(v) ) 는 v의 inorder traversal 을 했을때 처리되는 순서가 x좌표가 되고, y좌표는 v의 깊이로 해주면 된다.

주의!) 좌표는 1부터 시작한다. 0부터가 아니다!!(감점요소)

x(v) = inorder rank of v
y(v) = depth of v

how 그리기?

• 각 노드는 (x좌표, y좌표) 값이 겹치는 것이 없도록 할것.
  (당연히 각 노드의 x좌표값이 중위순회의 처리 순서를 넣어주므로 겹치지 않는다.)