자료구조 & 알고리즘 (트리)

트리

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다.

트리의 특징

▶ 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.

▶ 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.

▶ 루트에서 특정 정점으로 가는 경로는 유일하다.

이진트리

이진트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다

이진 트리의 특징

▶ 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될수 있다.

▶ 정점이 N개인 포화 또는 이진 트리의 높이는 log N이다.

▶ 높이가 h인 포화 이진 트리는 2h-1개의 정점을 가진다.

▶ 일반적인 이진 트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용한다

     ▶ 이진 탐색 트리

     ▶ 힙

     ▶ AVL 트리

     ▶ 레드 블랙 트리

트리의 구현 방법

그래프와 마찬가지로 인접 행렬, 인접 리스트 두가지 방식으로 트리를 표현할 수 있다.

이진 트리의 구현 방법

배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현할 수 있다.

JavaScript에서 사용법

이진 트리(Array)

이진 트리(Linked List)