박종훈 기술블로그

트리 알아보기 - 이진 트리, 이진 탐색 트리, AVL 트리, B-트리, B+트리, Red Black 트리

트리 알아보기 썸네일

지난 2월 17일 K-DEVCON 대전 스터디에서 공유한 내용을 블로그에도 정리해본다.

최근에 알고리즘 문제를 하루에 한 개 이상씩 풀려고 하는 중인데, 마침 B 트리와 관련된 내용을 다루게 되어서 트리 종류들을 간단하게 정리해서 스터디에서 공유하였다.

이 자료는 다양한 트리에 대해 개략적으로 정리한 것이다. 또한 시간순으로 정렬해두었다.

더 구체적인 부분들이 궁금하다면 함께 달아놓은 링크나 검색을 통해 찾아보면 된다.

대부분의 내용/이미지는 위키피디아를 참조하였다.

Binary 트리 (이진 트리)

설명

이미지

binary-tree

Binary Search 트리 (이진 검색 트리)

설명

이미지

binary-search-tree

삽입 과정

visualization

binary-search-tree visualization 1 binary-search-tree visualization 2 binary-search-tree visualization 3 binary-search-tree visualization 4 binary-search-tree visualization 5

삭제 과정

성능

worst-binary-search-tree

 평균최악
조회O(logN)O(N)
삽입O(logN)O(N)
삭제O(logN)O(N)
공간복잡도O(N)O(N)

정리

AVL 트리

설명

회전

회전이 발생하는 주요 모양

rotate-shape

visualization

avl-tree visualization 1 avl-tree visualization 2 avl-tree visualization 3 avl-tree visualization 4 avl-tree visualization 5

삭제과정

삽입 과정과 마찬가지로 이진 탐색 트리와 동이랗게 진행한 후 높이 차이가 발생되었을 때 회전을 진행해주면 된다.

B-Tree

어떻게 불러야 하는거지?

설명

정의

Knuth 라는 사람이 세운 정의는 다음과 같다.

m 차의 B-트리는 (m은 3이상의 정수)

참고로 ⌈ ⌉ 는 올림이라는 뜻이다.

visualization

b-tree visualization 1 b-tree visualization 2 b-tree visualization 3 b-tree visualization 4 b-tree visualization 5 b-tree visualization 6 b-tree visualization 7 b-tree visualization 8

성능

 평균최악
조회O(logN)O(logN)
삽입O(logN)O(logN)
삭제O(logN)O(logN)
공간복잡도O(N)O(N)

B+Tree

설명

이미지

B+tree

visualization

b+tree visualization 1 b+tree visualization 2 b+tree visualization 3 b+tree visualization 4 b+tree visualization 5 b+tree visualization 6 b+tree visualization 7 b+tree visualization 8 b+tree visualization 9 b+tree visualization 10

성능

 평균최악
조회O(logN)O(logN)
삽입O(logN)O(logN)
삭제O(logN)O(logN)
공간복잡도O(N)O(N)

Red Black 트리

설명

이미지

red-black-tree

트리의 속성

4번, 5번 속성이 중요하다.

visualization

red black visualization 1 red black visualization 2 red black visualization 3 red black visualization 4 red black visualization 5 red black visualization 6 red black visualization 7 red black visualization 8 red black visualization 9 red black visualization 10 red black visualization 11 red black visualization 12 red black visualization 13 red black visualization 14 red black visualization 15 red black visualization 16 red black visualization 17

성능

 amortized최악
조회O(logN)O(logN)
삽입O(1)O(logN)
삭제O(1)O(logN)
공간복잡도O(N)O(N)