트리
하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조이다.
노드의 깊이(영어: depth)는 루트 노드에서 자신까지 가는 경로의 길이이다. 특히, 루트 노드의 깊이는 0이다.
노드의 레벨(영어: level)는 루트 노드에서 자신까지 가는 경로의 길이 더하기 1이다. 특히, 루트 노드의 레벨은 1이다. 간혹 트리의 특정 깊이를 가지는 노드의 집합을 레벨이라고 하기도 한다.
노드의 높이(영어: height)는 그 노드와 단말 노드 사이의 경로의 최대 길이이다.
노드의 크기(영어: size)는 자기 자신 및 모든 자손 노드의 수이다.
이미지 출처: https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c
이진 트리
그 중, 자식 노드가 최대 2개까지만 붙는 트리를 이진트리(Binary tree)라고 한다.
이 두 개의 노드는 왼쪽 자식과 오른쪽 자식으로 분류한다.
*모든 트리가 이진 트리는 아니다. 자식이 3개붙은 트리는 Ternary tree가 되며, 4개씩 붙는 경우도 있다.
이진 트리는 자료의 삽입, 삭제 방법에 따라
- 정 이진 트리(Full binary tree)
- 완전 이진 트리(Complete binary tree)
- 포화 이진 트리(Perfect binary tree)
등으로 나뉜다.
이진 트리의 종류와 특징
이미지 출처: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
정 이진트리(Full binary tree)
각 내부 노드가 두 개의 자식 노드를 갖는 순서화된 트리이다.
홀수 개의 자식 노드를 가질 수 없다. (자식이 없거나 2개)
완전 이진 트리(Complete binary tree)
부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 트리를 말한다.
마지막 레벨을 제외하고 모든 노드가 가득 차 있어야 하며, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
포화 이진 트리(Perfect binary tree)
정 이진 트리이면서 완전 이진 트리인 경우를 말한다.
모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리.
균형 이진 트리(Balanced binary tree)
왼쪽 자식, 오른쪽 자식 노드의 갯수가 정확하게 일치해야 할 필요는 없지만 지나치게 한쪽으로 치우치지 않은 트리 구조를 말한다. 트리가 한 쪽으로 치우쳐져 있는 경우, 시간 복잡도가 악화되므로 균형잡힌 트리를 만드는 것이 주안점이다.
변질 이진 트리(Degenerate binary tree)
각 부모 노드가 오직 한 개의 연관 자식 노드를 갖는 트리. 이는 성능 면에서 트리가 연결 리스트 데이터 구조처럼 동작하는 것을 의미한다.
Binary Search Tree 이진 탐색 트리
이미지 출처: https://www.gatevidyalay.com/binary-search-trees-data-structures/
모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리라고 한다.
References
https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC
https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c
코드스테이츠 - Immersive course_3. Data Structure_Tree & Binary Search Tree
https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
https://soldonii.tistory.com/75
https://www.youtube.com/watch?v=LnxEBW29DOw&list=RDCMUCWMAh9cSkEn8v42YRO90BHA&index=1
[자료구조 알고리즘] Tree의 종류
https://www.gatevidyalay.com/binary-search-trees-data-structures/
