트리
정의
- 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있습니다.
용어
Root: 가장 상위의 정점Node: 각 정정Leaf Node: 더 이상 자식이 없는 정점Level: 루트로부터 몇 번째 깊이인지 표현합니다.Degree: 한 정점으로 부터 뻗어 나간 간선의 수
사용예시
- 조직도
- 디렉토리 구조
특징
- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 저점을 가집니다.
- 정점이 N 개인 트리는 반드시 N - 1 개의 간선을 가집니다.
- 루트에서 특정 정점으로 가는 경로는 유일합니다.
종류
이진 트리
- 개요
- 이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미합니다.
- 이진 트리, 완전 이진 트리, 포화 이진 트리, 편향 트리
- 탐색을 위한 알고리즘에서 많이 사용됩니다.
- 특징
- 정점이 N 개인 이진 트리는 최악의 경우 높이가 N 이 될 수 있습니다.
- 정점이 N 개인 포화 또는 완전 이진 트리의 높이는 log N 입니다.
- 높이가 h 인 포화 이진 트리는 2^h - 1 개의 정점을 가집니다.
- 일반적인 이진 트리를 사용하는 경우는 많지 않습니다.
- 이진 탐색 트리
- 힙
- AVL 트리
- 레드 블랙 트리
구현 방법
일반적인 트리
- 그래프와 마찬가지로 인접 행렬, 인접 리스트 두 가지 방식으로 트리를 표현할 수 있습니다.
이진 트리
- 배열 혹은 요소에 링크가 2 개 존재하는 연결 리스트로 구현할 수 있습니다.
JS의 이진 트리 구현
깃허브: https://github.com/HyeonWooGa/algorhithm-code-snippet
Aim for the TOP, Developer