hyeonwooga.log
로그인
hyeonwooga.log
로그인
알고리듬 #12 | 트리 (Tree)
HyeonWooGa
·
2022년 8월 30일
팔로우
0
알고리듬
트리
0
알고리듬
목록 보기
12/18
트리
정의
방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있습니다.
용어
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
HyeonWooGa
Aim for the TOP, Developer
팔로우
이전 포스트
알고리듬 #11 | 그래프
다음 포스트
알고리듬 #13 | 힙 (Heap)
0개의 댓글
댓글 작성