[자료구조] 트리, 이진 트리

그래프 이론

트리

[자료구조 소개]

정점이 V개일 때 모든 정점이 연결되어 있고 간선이 V - 1개인 그래프.

 

[자료구조 특징]

순환하지 않는 그래프.

 

[코딩 방법]

일반 양방향 그래프와 동일

 

[응용]

트리 동적 계획법

트라이

변형된 트리들 (이진 트리 등)

이진 트리

[자료구조 소개]

트리와 같으나, 하나의 루트 노드가 있고 자식 노드가 최대 두 개인 트리.

 

[자료구조 특징]

일반 트리와 동일. 자식 노드가 최대 두 개.

 

[코딩 방법]

자식 노드가 최대 두 개이므로 일반 그래프처럼 코딩할 이유가 없음.

보통 이진 트리를 사용하는 경우에는 루트 노드가 핵심이고 재귀를 사용하는 경우.

크기가 V이고 원소로 크기가 2인 배열을 갖는 2차원 배열을 생성하여 좌우 자식 노드를 저장하면 됨.

 

[응용]

변형된 이진 트리들 (BST, 레드 블랙 트리, 세그먼트 트리 등)