트리란?
- 노드(정점)과 간선을 이용해 사이클을 이루지 않도록 구성한, 그래프의 특수한 형태
- 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조
- 계층 관계를 갖는 데이터를 표현하기에 적합한 구조
트리의 특징
- 트리는 하나의 루트 노드를 가짐
- 루트 노드는 0개 이상의 자식 노드를 가짐
- 자식 노드는 0개 이상의 자식 노드를 가짐
- 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성
- N개의 노드를 갖는 트리는 항상 N-1 개의 간선(edge)을 가짐
- 모든 자식 노드는 한 개의 부모 노드만을 갖는다.
- 트리에는 사이클(cycle)이 존재할 수 없다.
- 사이클 :시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다.
- 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
- 트리의 노드는 self-loop가 존재 해서는 안된다.
트리 관련 용어
- 노드의 명칭
- 루트 노드(root node)
- 부모가 없는 노드로 트리는 단 하나의 루트 노드를 가진다. (ex : A- 루트노드)
- 단말 노드(leaf node)
- 자식이 없는 노드로 terminal 노드라고도 부른다. (ex : C, D, E - 단말 노드)
- 내부 노드(internal node)
- 단말 노드가 아닌 노드(ex : A, B - 내부 노드)
- 노드간의 관계
- 부모-자식(parent-child) 관계
- 루트노드를 제외한 모든 노드는 하나의 부모를 갖는다. 링크로 이어진 2개의 노드 중, 위의 노드가 부모이고 아래 노드가 자식이 된다.
- 형제(sibling) 관계
- 같은 부모 노드를 갖는 노드들 (ex : D-E, B-C : 형제)
- 조상-자손(ancestor-descendant) 관계
- 부모-자식 관계를 확장한 관계이다.
- 서브트리(sub-tree)
- 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리를 부트리(sub-tree)라고 부른다.
- 간선/엣지/링크/브랜치
- 노드와 노드를 연결하는 선
- 레벨(level)
- 0이나 1부터 시작
- 노드의 깊이(depth)
- 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수(ex : D의 depth : 2)
- 노드의 레벨(level)
- 트리의 특정 깊이를 가지는 노드의 집합 ( ex : level 1- {B, C} )
- 노드의 차수(degree)
- 자식 노드의 개수 ( ex : B의 degree - 2, C의 degree - 0)
- 트리의 차수(degree of tree)
- 트리의 최대 차수 ( ex : 위 트리의 차수는 2이다)
이진트리(Binary Tree)
- 각 노드가 최대 두 개의 자식을 갖는 트리
- 각 노드는 자식이 없거나 한 개 이거나 두 개만을 가짐
- 전위 순회, 중위 순회, 후위 순회를 통해 탐색 가능
1-1. 완전 이진트리(Complete Binary Tree)
- 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.
- 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
- 마지막 레벨 h에서 1~2h-1 개의 노드를 가질 수 있다.
- 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.
1-2. 전 이진트리(Full Binary Tree)
- 전 이진트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
1-3. 포화 이진트리(Perfect Binary Tree)
- 포화 이진트리는 모든 레벨이 노드로 꽉 차 있는 트리를 뜻한다.
- 전 이진트리의 성질도 만족해야 한다. 즉 모든 노드가 0개 혹은 2개의 자식 노드를 갖는다.
- 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
- 트리의 노드 개수가 정확히 2^k-1 개여야 한다. 여기서 k는 트리의 높이다.
1-4. 균형이진트리(Balanded binaty tree)
- 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 최대 1만큼 차이가 날 수 있는 이진 트리다
이진트리 종류
완전이진트리(Complete binary tree): 마지막 레벨을 제외한 모든 레벨에서 순서대로 node가 꽉 채워진 트리
정이진트리(Full binary tree): 트리의 모든 node가 0개 혹은 2개의 자식을 가지는 트리
포화이진트리(Perfect binary tree): leaf node가 끝까지 정말 꽉 찬 트리
균형이진트리(Balanded binaty tree): leaf node들의 레벨차이가 최대 1레벨까지만 나는 트리
2. 이진 탐색(검색) 트리(Binary Search Tree)
이진 탐색 트리는 이진트리이면서 아래와 같은 속성을 갖는 트리를 뜻한다.
- 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
- 부모의 키가 왼쪽 자식 노드의 키보다 크다.
- 부모의 키가 오른쪽 자식 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
이진 탐색 트리는 효율적인 탐색을 위해 고안된 트리이다.
레드-블랙 트리
RBT (Red-Black Tree)
- BST를 기반으로 하는 트리 형식 자료구조
- BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어짐
- BST를 기반으로 하기 때문에 당연히 BST의 특징을 모두 가짐
- 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장,
이러한 NIL들을 leaf node로 간주함 - 모든 노드를 빨간색 또는 검은색으로 색칠하며, 연결된 노드들은 색이 중복되지 않음
AVL 트리(AVL tree)
- 스스로 균형을 잡는 이진 탐색 트리
- 트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)
- 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에
이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용
- 특징
- 이진 탐색 트리의 속성을 가짐
- 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1
- 어떤 시점에서 높이 차이가 1보다 커지면
회전(rotation)을 통해 균형을 잡아 높이 차이를 줄임 - 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)
B-TREE
- 모든 리프 노드들이 같은 레벨이 있어야 하는 트리 구조
- self-balancing tree → 스스로 균형을 맞추는 트리 → 같은 레벨에 있도록
- 노드는 2개보다 많은 자식을 가질 수 있음
- 데이터 삽입, 삭제 시 스스로 균형을 맞춰야 하므로 일반 이진 트리보다 복잡한 연산이 필요함
- 하지만 탐색 시에는 어떤 값에 대해서도 최대 시간이 같으므로 빠름
- 높이는 가능한한 낮게 유지해야 함
b + tree
- B트리의 변형된 형태로 데이터의 효율적인 삽입, 검색, 삭제를 추구하는 자료구조
- B-트리와 달리
삽입, 삭제 연산이 단말 노드에서만 이루어지며 단말 노드끼리 연결리스트로 연결되어 있음 - 단말 노드가 순차집합 연결되어 있기 때문에 순차적인 탐색에 유리
참고
- 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리
- [Data Structure] Java 이진트리(Binary Tree) 구현
- 🛸[Java] 트리 자료구조의 개념과 구현
- [JAVA] Tree 이진트리 구현
- [Java] 자바로 이진 검색 트리(BST) 구현하기
- 코딩 테스트를 위한 트리(Tree) 자료구조 10분 핵심 요약
- [CS 스터디: Java] (7) B Tree & B+ Tree
- 신입 개발자 기술면접 질문 정리 - 자료구조
- [자료구조] 트리(Tree)
- 🛸[Java] HashSet, HashMap, TreeSet, TreeMap 정리
- 🛸TreeSet / TreeMap
- Balanced Tree - B-tree, Red-black tree, AVL tree
- [자료구조] AVL 트리(Tree)
- AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터