이진 트리와 B-Tree

이진 트리 Binary Tree

 

트리란 탐색을 위한 자료구조로, Node와 Edge로 구분되며 (그래프 이론에서 쓰던 그 용어들의 의미와 동일) 그래프와 다른 점은, 위계가 존재하기 때문에 depth가 존재한다는 것이다. 여기서 뿌리 노드의 depth를 0이라 보는 곳도 있고 1이라고 보는 곳도 있다. 

 

여기서 자식 노드의 갯수를 차수라고 한다. A 노드의 차수는 2, C 노드의 차수는 3이다.

 

이 중 자식 노드가 최대 2개인 노드들로 구성된 트리를 '이진 트리'라고 부른다. 따라서 다음과 같은 특징을 가진다.

 

• 이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0)
• 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1)
• 하나의 노드가 가질 수 있는 키는 1개다 (예를 들어 뿌리노드는 A라는 키만 가지고 있다. 여러 개의 키를 가질 수 있다면 이진트리가 아니다)

 

이진 트리는 포화 이진 트리(Perfect Binary Tree)와 완전 이진 트리(Complete Binary Tree)로 나뉩니다.

 

포화 이진 트리는 모든 레벨이 꽉 차 있는 트리입니다. 

완전 이진 트리는 트리의 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 채워지는 트리입니다. 더 자세한 특징으로는 다음과 같은 것들이 있습니다.

 

CBT

• 트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1이하이고,
• 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며,
• 왼쪽에서 오른쪽으로 채워집니다
• heap

따라서 정의상 모든 PBT는 CBT에 속합니다.

포화 이진 트리

완전 이진 트리

 

 

그 외에도 트리의 속성 등에 의해 구분되는 다양한 이진 트리가 존재합니다.

 

이진 탐색 트리

 

이진 트리 중 탐색을 쉽게 하기 위해 노드의 키값에 대소 관계를 정렬한 이진 트리이다. 

 

 

레드 블랙 트리

 

불균형한 트리의 검색 효율을 늘리기 위한 자료 구조

 

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

 

 

 

이진 트리의 순회 방법

 

크게 3가지로 나뉩니다. 전위 순회, 중위 순회, 후위 순회.

층별 순회는 그냥 차례대로 방문하는거라서 ㅎ;;

 

 

전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문

중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문

후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문

층별 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문

 

https://m.blog.naver.com/rlakk11/60159303809

 

 

위와 같은 트리가 있다고 한다면 각각 순회방법은 다음과 같습니다.

 

전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6

중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6

후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0

층별 순회 : 0->1->2->3->4->5->6->7->8->9->10->11

 

전위 순회는 뿌리->왼쪽 자식->오른쪽 자식 순 (뿌리부터 시작해서 왼쪽부터)

중위 순회는 왼쪽자식-> 뿌리-> 오른쪽 자식 (왼쪽부터 읽어나가자)

후위 순회는 왼쪽자식->오른쪽 자식-> 뿌리 (아래부터 자식 트리를 전부 돌 때까지 상위 트리를 돌지 않음)

층별 순회는 그냥 노드의 순서대로 

 

 

DFS(Depth First Search 깊이 우선 탐색)와 BFS(Breadth First Search 너비 우선 탐색)가 있습니다.

 

B-Tree 

 

과거 MongoDB의 indexing에 대해서 공부할 때 B-Tree를 잠깐 다룬 적이 있다.(darrengwon.tistory.com/671) 해당 게시물의 글을 가져와 보았다. 앞서 다룬 이진 트리와 비교하며 참고하면 더 잘 기억할 수 있을 것이다.

 

mongoDB에서 인덱스는 어떤 필드에 대한 값을 검색하기 쉽도록 해당 필드의 값들을 B-Tree 구조로 만들어서 저장한다. B-Tree 자료구조란 하나의 노드가 가질 수 있는 키의 최대 갯수가 2보다 큰 트리 구조를 말한다.

 

첨부한 이미지를 보면 무엇을 말하는지 알 수 있을 것이다. Binary Tree(이진 트리)는 노드가 하나의 키를 가지고 있지만 B-Tree는 하나의 노드에 키들을 가질 수 있다. 아래 이미지에서 어떤 노드는 6, 8 이라는 두 개의 키를 가지고 있고, 9, 10, 11이라는 세개의 키를 가진 것도 볼 수 있다.

 

B-Tree에는 몇 가지 규칙이 있는데

 

1️⃣ 각 노드에 있는 키들은 전부 정렬 되어 있어야 한다. 노드 내부의 키가 6, 8 이어야지 8, 6이면 안된다는 것이다.

 

2️⃣ 이렇게 정렬된 키 사이 사이에 자식 노드들이 연결되어 있는데, 해당 키 사이에 연결된 자식 노드를 키 사이의 값만 가져야 한다.

 

말이 어려운데, 노드 (6, 8) 에서

6 왼쪽에 연결된 노드는 6보다 작아야 하므로 5가 올 수 있다.

6, 8 사이에 연결된 노드는 6보다 크고 8보다 작은 키를 가져야 하므로 7이 왔다.

8 오른쪽에 연결된 노드는 8보다 커야 하므로, 9, 10, 11 등이 올 수 있다.

 

이러한 특성 때문 mongoDB가 특정 값을 찾을 수 있게 된다.

에를 들어 아래 B-Tree에서 7을 찾아야 한다고 가정하자.

 

1. 그렇다면 루트 노드(4)가 7보다 작으므로 7은 4의 오른쪽에 연결되어 있을터이고

2. 오른쪽 노드의 6, 8을 보니 7은 그 사이에 연결된 노드일 것이다.

3. 그 사이 노드의 키값을 살펴보니 7이다. 찾았다.

그런데 B-Tree 뿐만 아니라 트리 구조는 자식 노드가 많아지게 되거나 하나의 노드에 키값이 적게 들어 있다면 검색 효율이 떨어 지게 된다. 또, 새로운 정보를 추가하거나, 삭제하게 되면 새롭게 노드를 쪼개거나 합치는 등의 '균형 맞춤' 과정을 다시 해야 하기 때문에 생성/삭제 작업이 자주 이뤄지는 필드라면 인덱스를 함부로 생성하지 않는 것이 좋다.

 

 

 

 

 

 

참고한 글 및 이미지 출처)

 

[자료구조]Tree🎄🌲🌳🌴

인덱스 (1) 인덱싱의 이해, 종류, B-Tree 자료구조

[자료구조] 트리(Tree)의 개념 및 전위순회, 중위순회, 후위순회, 층별순회