검색트리(Search Tree)

검색트리(Search Tree)

트리(Tree)란?

-계층적인 구조를 표현

(조직도,디렉토리와 서브디렉토리 구조, 가계도)

트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨.

부모(parent)-자식(child) 관계

형제관계 :부 모가 동일한 노드들

리프(leaf) 노드 : 자식이 없는 노드들

내부(internal)노드 : 리프노드가 아닌것

조상-자손관계 : 부모-자식 관계를 확장한 것

부트리(subtree)

레벨(level)

트리의 높이는 : 서로다른 노드의 갯수

트리의 기본적인 성질

-노드의 n개일때 링크의 갯수는 n-1이다.

-트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두노드간의 경로도 유일하다.

이진트리(binary tree)

-이진트리에서 각 노드는 최대 2개의 자식을 가진다.

-각각의 자식 노드는 자신이 부모 왼쪽 자식인지 오른쪽 자식인지가 지정된다.

ex)Huffman code

Full and Complete Binary Trees

높이가 h인 full binary tree는 2^h-1개의 노드를 가진다.

노드가 N개인 full 혹은 complete 이진트리의 높이는 o(lonN)이다.

이진트리의 표현

-연결구조(Linked Structure) 표현

:각 노드에 하나의 데이터필드와 왼쪽자식(left),오른쪽자식(right) 그리고 부모노드(p)의 주소를 저장

left

data

p

right

이진트리의 순회(traversal)

-순회 : 이진 트리의 모든 노드를 방문하는 일

-중순위(inorder) 순회

-선순위(preeorder) 순회

-후순위(postorder) 순회

-레벨오더(level-order) 순회 : 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로 / 큐를 이용하여 구현