요약
트리
단방향 그래프의 한 종류로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태의 비선형 자료구조입니다. 트리는 대상 정보를 계층적으로 구조화할 때 사용하며, 주로 데이터를 효과적으로 탐색하기 위해 활용됩니다
이진트리
자식 노드가 최대 두 개인 트리로, 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 부모보다 작고, 모든 오른쪽 자식의 값이 부모보다 큰 값을 가지는 트리입니다. 이진 트리에서는 주로 중위 순회, 전위 순회, 후위 순회, 레벨 순회와 같은 순회 방법을 사용하여 노드를 방문합니다.
레드 블랙 트리(RB 트리)
검색 효율을 높이기 위한 자료구조로, 노드들을 레드 또는 블랙으로 표시하며 특정 규칙을 따릅니다.
다원 탐색 트리(MST)
각 노드가 여러 개의 자료를 가질 수 있는 트리로, 하위 트리의 수를 설정할 수 있습니다.
- B- 트리 : 대량의 데이터를 처리하는데 사용되는 검색 구조로, 노드 내 데이터 수와 노드의 차수에 관한 규칙이 있습니다.
- B+ 트리 : B-트리와 유사하지만 리프 노드에만 데이터가 저장되며, 더 많은 데이터를 담을 수 있고 순차 접근이 용이한 구조입니다.
- B* 트리 : B-트리의 성능을 향상시키기 위한 변형으로, 노드 분리를 최소화하여 높은 효율을 유지합니다.
트리
- 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태입니다.
- 하나의 방향으로만 연결된 계층적 자료구조입니다.
- 하나의 데이터 아래에 여러 개의 데이터가 존재하는 비선형 구조입니다.
- 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터(Node)를 간선(edge)으로 연결합니다.
트리 특징
- 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료구조다.
- 그래프의 한 종류로, 최소 연결 트리라고도 불린다.
- 트리의 구조는 데이터의 저장의 의미보다는 저장된 데이터를 더 효과적으로 탐색하기 위해서 사용된다.
- 리스트와 다르게 데이터가 단순히 나열되는 구조 X --> 트리는 부모(parent)와 자식(child)의 계층적인 관계로 표현된다.
- 트리는 사이클이 없다.
- 트리에서 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다.
트리 용어
- 노드(Node) 종류
- 루트 노드(Root Node) : 트리의 최상위에 있는 노드
- 리프 노드(Leaf Node, 외부 노드, 단말 노드) : 트리가 더 뻗어 나갈 수 없는 가장 마지막에 있는 노드
- 부모 노드(Parent Node) : 자식노드를 갖고 있는 상대적으로 루트노드에 가까운 상위노드
- 자식 노드(Child Node) : 부모 노드에 달려 있는 상대적으로 루트노드에서 먼 하위노드
- 형제 노드(Sibling Node) : 같은 부모를 가지는 노드
- 간선(Edge) : 노드와 노드 간의 연결선
- 서브트리 : 트리 안에 있는 특정 노드를 루트노드로 하는 트리
- 깊이(Depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이
- 너비(Width) : 같은 레벨에 있는 노드 수
- 높이(Height) : 리프 노드를 기준으로 루트까지의 높이
- 레벨 : 루트에서 노드까지의 간선의 수
- 노드의 차수(Degree) : 노드의 자식 수
- Path Length : 해당 경로에 있는 총 노드의 수
이진트리
자식 노드가 최대 두 개인 노드로 구성된 트리입니다. 이진트리는 자료의 삽입, 삭제 방법에 따라 정 이진트리, 완전 이진트리, 포화 이진트리로 나뉩니다.
- 정 이진트리 : 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.
- 완전 이진트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
- 포화 이진트리 : 정 이진트리면서 완전 이진트리인 경우입니다.
이진 탐색
오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘 입니다.
- 배열의 중간값이 내가 찾고자 하는 값인지 확인합니다.
- 중간값이 원하는 값이 아닌 경우
- 원하는 값이 중간값보다 큰 경우, 중간값의 다음 값부터 탐색 범위 마지막까지를 범위로 잡고 탐색을 반복 수행합니다.
- 원하는 값이 중간값보다 작은 경우, 탐색 범위 처음부터 중간값의 이전 값까지를 범위로 잡고, 탐색을 반복 수행합니다.
- 중간값이 원하는 값일 경우 탐색을 종료합니다.
이진 탐색 트리(Binary Search Tree)
모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있습니다.
- 루트 노드의 키와 찾고자 하는 값을 비교합니다. 만약 찾고자 하는 값이면 탐색을 종료합니다.
- 찾고자 하는 값이 루트 노드의 키보다 작으면 왼쪽 서브 트리로 탐색을 진행합니다.
- 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행합니다.
트리 순회
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 합니다.
순회 종류
- 전위 순회
- 가장 먼저 루트 노드를 방문합니다.
- 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 후, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색합니다.
- 10(root) > 7 > 5 >3 > 6 > 9 > 12 > 11 > 14 > 15 (중간>왼쪽>오른쪽)
- 전위 순회는 주로 트리를 복사할 때 사용합니다.
- 중위 순회
- 가장 먼저 제일 왼쪽 끝에 있는 노드를 방문합니다.
- 제일 왼쪽 끝에 있는 노드에서 시작해 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색합니다.
- 3 > 5 > 6 > 7 > 9 > 10(root) > 11 > 12 > 14 > 15 (왼쪽 >중간>오른쪽)
- 중위 순회는 오름차순으로 값을 가져올 때 사용합니다.
- 후위 순회
- 가장 먼저 제일 왼쪽 끝에 있는 노드를 방문합니다.
- 제일 왼쪽 끝에 있는 노드에서 시작해 루트를 거치지 않고, 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문합니다.
- 3 > 6 > 5 > 9 > 7 > 11 > 14 > 15 > 12 > 10(root) (왼쪽>오른쪽>중간)
- 후위 순회는 트리를 삭제할 때 사용합니다.
- 레벨 순회
- 트리의 레벨 기준으로 노드들을 방문하는 순회 방법입니다.
- 루드 노드를 시작으로 아래로 뻗어나가며 노드들을 방문합니다.
- 동일한 레벨에 여러 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 방문합니다,
- 10(root) > 7 > 12 > 5 > 9 > 11 > 15 > 3 > 6 > 14
AVL Tree
- 스스로 균형을 잡는 Self-Balancing 이 적용된 이진 탐색 트리다.
- 이진 탐색 트리의 경우 뷸균형 상태에서는 O(N)이라는 성능을 띄므로 성능이 떨어지지 않게 균형을 유지하게 한 것이다
레드 블랙 트리(RB Tree : Red-Black Tree)
- 불균형한 트리의 검색 효율을 늘리기 위한 자료 구조
- 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장
- 실시간 처리와 같은 실행 시간이 중요한 경우에 유용
특징
- 노드는 레드 혹은 블랙 중의 하나이다.
- 루트 노드는 블랙이다.
- 모든 리프 노드들(NIL)은 블랙이다.
- 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
- 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
다원 탐색 트리(MST: M-way Search Tree)
- 균형을 유지하는 트리 구조입니다.
- 트리의 각 노드가 여러 개의 자료를 가질 수 있다.
- 하위 트리의 수를 임의로 설정 가능하다.
특징
- 각 노드의 0에서 최대 M개의 서브 트리를 가진다.
- K개의 서브 트리를 가지는 노드는 (K-1)개의 자료를 가진다(단, K≤M)
- 각 노드 안에서 자료들은 검색 키에 의해 정렬
B-트리
- 이진 트리를 확장해, 하나의 노드가 여러 개의 데이터를 가질 수 있는 트리이다.
- 대량의 데이터를 처리해야 하는 검색 구조 주로 데이터베이스, 파일시스템에서 인덱스 저장 방법으로 사용하는 자료구조이다.
- 노드 내 데이터 수가 N개라면 자식 노드의 수는 N+1개 이며, 노드의 데이터는 항상 정렬된 상태여야 한다.
- 노드 내 최대 데이터 수에 따라 2차 B-Tree(2개), 3차 B-Tree(3개) 등등
특징
- 노드의 데이터 개수가 n개라면 자식 노드의 수는 n+1개다.
- 각 노드 안의 데이터들은 정렬된 상태여야 한다.
- 데이터의 왼쪽 서브트리는 데이터보다 작은 값들이고, 오른쪽 서브트리는 큰 값들이다.
- 루트 노드는 적어도 2개 이상의 자식을 가져야 한다.
- n차 B-tree는 루트 노드를 제외한 모든 노드가 적어도 n개 이상의 데이터를 가져야 한다.
- leaf 노드는 같은 레벨에 있어야 한다.
- 입력된 데이터는 중복될 수 없다.
B+ 트리
- B트리의 특징을 가지고 있지만 모든 키 값들이 Leaf 노드에 정렬되어 있는 트리 구조.
- Leaf 노드들은 연결 리스트 형태로 서로 연결되어 있고 이를 순차집합(sequence set)이라고 하며 오름차순으로 정렬이 되어 있다
- 리프 노드에만 데이터가 저장되어 있어 빠른 순차 접근이 가능합니다.
- B+ 트리의 비단말 노드(not leaf)들은 데이터의 빠른 접근을 위한 인덱스 역할 수행(Index Set)
- 오직 리프노드에만 데이터 저장 가능하고 리프 노드에 모든 데이터가 있기 때문에 키 중복이 있다
- 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용 가능
- 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.
- B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다
B* 트리
- 노드가 꽉 차면 분리하지 않고 키와 포인터를 재배치하여 다른 형제 노드로 옮김
- 리프를 제외한 모든 노드는 m개의 서브트리 이상을 가질 수 없다
- 루트와 리프를 제외한 모든 노드는 적어도 [(2m-2)/3]+1개의 서브트리를 갖는다
- 루트는 리프가 아닌 이상 최소 2개, 적어도 2[(2m-2)/3]+1개의 서브트리를 갖는다.
- 모든 단말노드는 같은 레벨을 가진다
- 각 리프노드는 최소[(2m-2)/3]개, 최대 m-1개의 키 값을 갖는다
- 노드에 저장되는 자료가 넘치는 경우(Overflow), 일단 형제 노드들로 재분배하는 과정 수행. 모든 형제 노드들이 가득 찬 경우에만 B-트리의 분할 연산을 수행(보조 연산 최소화)