CS/자료구조

[자료구조] 헷갈리는 트리 종류 정리

Joonfluence 2023. 10. 30. 14:32

이진 트리 (Binary Tree)

이진트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다. 이진트리에는 여러 종류가 있습니다. 정이진트리(Full binary tree), 포화이진트리(Perfect binary tree), 완전이진트리(Complete binary tree), 균형이진트리(Balanced binary tree), 이진 탐색 트리 (Binary Search Tree), 균형 이진 트리, AVL Tree 등이 있습니다. 이 중에서도 이진 탐색 트리, 균형 이진 트리, 균형 이진 탐색 트리, AVL Tree에 관해 알아보도록 하겠습니다.

이진 탐색 트리 (Binary Search Tree)

이진 트리 기반의 탐색을 위한 자료구조입니다. 특성으로는 모든 원소의 키는 유일한 키를 가지며, 왼쪽 서브 트리 키들은 루트 키보다 작다는 특성이 있습니다. 또한 오른쪽 서브 트리의 키들은 루트의 키보다 큽니다.

균형 이진 트리 (Balanced Binary Tree)

균형이진트리란 leaf node들의 레벨차이가 최대 1레벨까지만 나는 트리를 뜻합니다. 균형이진트리는 한 쪽으로 쏠릴 수 있는 데이터로 구성되더라도, 트리의 높이를 균형적으로 유지시켜줍니다. 따라서 검색할 때 최악의 경우에도 O(logN)의 안정성을 유지합니다. 균형 이진 트리는 자체 균형이 아니며 노드가 삽입되거나 삭제될 때 불균형해질 수 있습니다.

AVL Tree (Self-balancing Binary Search Tree)

AVL 트리(발명가 Adelson-Velsky와 Landis의 이름을 따서 명명됨)는 이진 탐색 트리에 속하며, 자체 균형 이진 탐색 트리입니다. AVL 트리에서 노드의 두 자식 하위 트리의 높이는 최대 1만큼 다릅니다. 언제든지 1 이상 다를 경우 이 속성을 복원하기 위해 재조정이 수행됩니다. 조회, 삽입 및 삭제에는 평균 및 최악의 경우 모두 O(log n) 시간이 소요되며 여기서 O(n)은 작업 전 트리의 노드 수이다. 삽입 및 삭제 시 하나 이상의 트리 회전에 의해 트리의 균형을 다시 맞춰야 할 수 있습니다.

B-Tree (Balanced Tree)

B-Tree는 노드당 2개 이상의 자식을 가질 수 있는 자체 균형 트리 데이터 구조이며, 데이터는 특정 순서로 정렬됩니다. B-Tree는 최소 정도 t라는 매개 변수로 정의되며, 각 노드의 최소 및 최대 키 수와 자식 수를 결정합니다. B-Tree는 데이터베이스 또는 파일 시스템과 같은 대규모 데이터 세트에서 키를 검색하는 데 필요한 디스크 액세스 수를 줄이도록 설계되었습니다. B-Tree의 높이는 O(log M*N)이며, 여기서 M은 트리의 순서이고 N은 노드 2의 개수입니다.

B+Tree

B+Tree는 B-Tree의 단점을 개선하기 위한 자료구조입니다. B-Tree는 범위 탐색 혹은 전체 값 탐색을 해야 할 때, 값 탐색을 위해 매번 트리 순회를 거쳐야 합니다. 이러한 단점을 해소하고자 B+Tree는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Sibiling node는 연결리스트 형태로 이어져 있습니다. leaf node에 모든 자료들이 존재하고, 그 자료들이 연결리스트로 연결되어 있으므로 매번 트리 순회를 거쳐야 하는 B-Tree에 비해, 탐색에 횔씬 유리합니다.

leaf node가 아닌 자료는 인덱스 노드라고 부르고, leaf node 자료는 데이터 노드라고 부릅니다. 인덱스 노드의 Value값에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재합니다. 데이터 노드의 Value 값에 데이터가 존재하는 것이죠. 따라서 키값은 중복될 수 있고 , 데이터 검색을 위해서는 반드시 leaf node까지 내려가야 한다는 특징을 가지고 있습니다.

오늘날 데이터베이스에서 가장 중요한 것은 검색속도이기 때문에 대부분의 데이터베이스 시스템은 B+Tree구조를 채택하고 있습니다.

정리하면

  1. AVL Tree는 균형 이진 트리이지만, 균형 이진 트리는 AVL 트리가 아닙니다.
  2. B-Tree는 Self-balanced 트리이지만, AVL 트리가 아닙니다.
  3. B-Tree는 자식으로 2개 이상 노드를 가질 수 있으므로, 이진 트리가 아닙니다.
  4. 균형 이진 트리는 self-balancing 기능을 포함하지 않습니다.
  5. B+Tree는 leaf 노드에만 데이터를 보관하고 리프노드 간 연결되어 있다는 특성이 있습니다.

참고한 사이트

https://en.wikipedia.org/wiki/B-tree
https://en.wikipedia.org/wiki/B%2B_tree

반응형
저작자표시 비영리