빽 투더 기본기 [알고&자구 3편]. 균형 트리

트리의 구조 특성상 탐색의 시간 복잡도가 '대체로' O(log n) 만에 가능하다. 따라서, 파일 시스템 등, 자료를 저장하거나 관리하는 시스템에서 많이 사용되곤 한다.

아무튼 트리를 사용한다는 것의 핵심은, 빠르게 접근 하기 위함이고, 이를 위해 '그냥 트리' 에서 여러 형태로 변모된다.

2편에서, 트리와 바이너리 서치 트리를 살펴보았다.
하지만 '지금까지의 트리'의 문제점은, 트리가 한 쪽으로 치우쳐져 있는 경우, 탐색의 시간 복잡도가 O(n) 이 된다는 것이다. 따라서, 치우쳐지지 않게, 즉 균형있게 트리를 만드는 것이 트리 구성에 핵심 이슈가 된다.

균형있는 트리. 이를 Balnaced Tree 라고 하며, 기존 트리에서 더 발전된 (균형을 잡아주는) 트리 종류는 다음과 같다.

• AVL Tree
• B Tree
• 2-3 Tree
• 2-3-4 Tree
• Red-Black Tree

위 트리들은 발전된 형태의 트리들로, 최악의 경우에도 접근 및 탐색의 시간복잡도가 O(log n) 이다.

각 자료구조 구현은 꽤 복잡하고 설명할게 많으므로, 이 글에서는 이런게 있다~ 수준에으로, 각 자료구조의 모양과 용어 정도를 알아보자.

 

AVL Tree

AVL Tree 를 한 마디로 표현하면, 이진 탐색 트리 (feat. 균형) 이다.
말 그대로, 기존 이진 탐색 트리에서, 치우쳐짐을 방지해 균형을 맞게하는 일종의 트릭을 넣은 구조이다.

자세한 내용은 유투브에 올라온 [열혈강의] 자료구조를 참고하고, 기억해둬야할 포인트는 다음과 같다.

• 이진 탐색 트리의 균형판 버전이다.

• BF(Balance Factor) 를 유저가 설정해두어, 트리 내 서브 트리 간의 높이 차이가 BF를 안 넘게 수시로 조정한다.

• 삽입의 경우 4가지 케이스 (LL, RR, LR, RL) 로 나누어, '회전' 이라는 개념으로 트리 균형을 유지한다.

 

B Tree

B Tree 는 한 노드에 여러개의 데이터를 담을 수 있으면서도, 이진 탐색 트리의 느낌을 가지고 있는, 좀 더 일반화된 모양이다.
기존 트리는 한 노드에 하나의 값만 담았는데, 여기는 여러 개의 데이터를 담으므로, 트리에 리스트를 섞어 넣은 듯한 느낌도 든다.

자세한 내용은 역시 유튜브에 올라온 GRIT A님의 강의를 참고하고, 기억해둬야할 포인트는 다음과 같다.

• 노드에 담길 수 있는 최대 데이터 수를 N개라고 두면, N차 B tree 라고 한다.
• N이 홀수냐 짝수냐에 따라 알고리즘이 많이 다르다.
• 각 노드 내 데이터는 정렬되어 있어야 한다.
• 루트 노드를 제외한 모든 노드는 적어도 M/2 개의 데이터를 갖고 있어야 한다.
• 리프 노드는 모두 같은 레벨에 있어야 한다.
• B Tree의 경우, 모든 노드를 순회하려면, 항상 루트노드에서 시작하여 순회한다.
  이러한 순차 탐색의 성능을 높이기 위해, 마지막 리프 노드간 연결 리스트를 구성하여, 순차 탐색에 좀 더 용이하게 한 것이 B+ Tree 이다.

다음 링크에 매우 자세히 설명되어 있다.

B Tree 개념 정리
https://hyungjoon6876.github.io/jlog/2018/07/20/btree.html

 

2-3 Tree, 2-3-4 Tree

2-3 Tree는, 2개 또는 3개의 child를 가지는 트리다. 즉, 한 노드에 들어갈 수 있는 데이터 수가 최대 2개다.

2-3-4 Tree는 한 노드에 최대 세 개의 데이터를 가질 수 있다.

즉, 한 노드에 데이터가 최대 N개 들어갈 수 있으면, 자식 노드로 N+1 개를 갖는 B Tree 중 하나다.

자세한 내용은 아래 링크 참조

2-3 Tree
https://tubuk.tistory.com/8

2-3-4 Tree
http://egloos.zum.com/itsmywar/v/837217

Difference between B-Trees and 2-3-4 Trees
https://stackoverflow.com/questions/2574249/difference-between-b-trees-and-2-3-4-trees