[알고리즘] 4-1. 검색 트리

트리와 이진 트리

 

1. 트리

: 계층적 구조를 표현 [조직도, 디렉토리와 서브 디렉토리, 가계도]

 

루트 노드 : 맨 위의 노드

리프 노드 : 자식이 없는 노드

내부 노드 : 리프노드가 아닌 노드

노드 연결 선 : link, edge, branch

부 트리 : 노드와 그 노드의 자손으로 이루어진 트리

 

루트 노드를 제외한 모든 노드는 유일한 부모 노드를 갖는다.

부모-자식 관계와 조상-자손 관계

-> 부모 자식은 1촌, 조상 자손은 n촌

 

트리의 성질

1. 레벨은 1부터 시작한다.

2. 노드가 N개인 트리는 항상 N-1개의 링크를 갖는다.

3. 루트에서 어떤 노드로 가는 경로는 유일

4. 임의의 두 노드간의 경로도 유일

 

이진 트리의 성질

1. 각 노드가 최대 2개의 자식을 갖는다.

2. 각각의 자식 노드는 부모의 왼쪽 자식인지 오른쪽 자식인지 지정되어 구분된다.

[자식이 하나인 경우에도 적용]

 

전이진 트리와 완전 이진트리

전이진 트리 : 모든 노드가 꽉 차있는 형태

완전 이진 트리 : 마지막 레벨의 노드가 하나 비어 있는 형태

 

1.높이가 h인 전이진 트리는 2^h-1개의 노드를 갖는다.

2. 노드가 N개인 전이진트리와 완전이진트리의 이진트리 높이는 O(logN)이다. [최악의 경우 N]

 

이진트리의 표현

: 연결구조 표현이 가능하다.

-> 각 노드에 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식 그리고 부모 노드의 주소를 저장한다.

[부모노드의 주소는 반드시 필요한 경우가 아니면 생략하는 경우가 많다.]

 

이진트리의 순회 [왼쪽 노드 부터 방문이 원칙]

순회 : 이진 트리의 모든 노드를 방문

중순위 / 선순위 / 후순위 / 레벨오더

 

1. 중순위

: Tl -> r -> Tr

 

INORDER-TREE-WALK (x)
 IF x != NIL
  then INORDER-TREE-WALK (left[x])
   print key[x]
   INORDER-TREE-WALK (right[x])

 

 

2. 선순위와 후순위

PREORDER-TREE-WALK (x)
 IF x != NIL
  then 
   print key[x]
   PREORDER-TREE-WALK (left[x])
   PREORDER-TREE-WALK (right[x])
   
POSTORDER-TREE-WALK (x)
 IF x != NIL
  then 
   POSTORDER-TREE-WALK (left[x])
   POSTORDER-TREE-WALK (right[x])
   print key[x]

 

3. 레벨오더

: 레벨 순으로 방문하며 [1레벨부터], 동일 레벨에서는 왼쪽에서 오른쪽 순서로 순회

: 큐를 이용해 구현

 

LEVEL-ORDER-TREE-TRAVELSAL()
 visit the root;
 Q <- root;
 while Q is not empty do
  v <- dequeue(Q);
  visit children of v;
  enqueue children of v into Q;
 end.
end.