binary tree (1)
오랜만에 블로그에 글을 올린다. 오랫동안 공부를 안해서 까먹고 있었던 CS를 하나씩 복습해보려고 한다. 그중에서도 널리 쓰이고 있는 이진 트리(binary tree)에 대해서 알아보자.
트리
트리란 다음과 같은 조건을 만족하는 노드로 이루어진 자료 구조를 뜻한다.
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖는다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이것은 반복적으로 정의된다.
노드들과 그 노드들을 연결하는 것은 간선(edge)라고 부른다.
트리는 돌고 돌아서 이어지는 사이클이 존재하지 않는다.
비선형 자료구조로 계층적 관계를 표현한다.
리프 노드는 자식 노드가 없는 노드를 가리키는 말이다.
트리는 높이와 차수라는 용어가 있다.
높이는 루트 노드에서 가장 멀리 떨어진 노드의 깊이를 뜻한다.
차수는 특정 노드의 자식수를 차수라 하며, 트리의 차수는 루트 노드의 차수를 뜻한다. 리프 노드의 차수는 0이다.
지금까지 트리에 대해 살펴보았다. 직접 구현하는 것을 연습하는 것도 꽤 재밌다. 예전에 열혈자료구조를 보면서 연결리스트 기반으로 구현했던 것이 기억난다. 구조체안에 자식 노드를 찾을 수 있도록 포인터를 선언하고 해당 노드의 데이터를 저장해뒀었다. 노드의 삽입과 삭제에서 생각보다 생각할 부분이 있어서 까다로운 부분이 없지 않았다. 하지만 진정 어려운 부분은 트리에서 파생된 자료구조를 다루는 부분이다.
이진 트리
이진트리란 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 자료 구조중에 활용도가 높으므로 중요하다고 볼 수 있다. 이유는 구현이 매우 간단하고 탐색 속도가 빠르며, 다른 N링크를 이루는 트리에 비해 문제를 일으킬 상황이 적기 때문이다. 시간 복잡도 면에서 N링크에게 밀리지만, N링크는 활요하기 힘들다는 단점이 있다. 하지만 이진 트리는 자식 노드가 두 개로 고정되어 있어, 여러가지 기법을 쓰기도 편리하고 그 종류 자체도 다양하기 때문에 활용도가 무궁무진하다 볼 수 있다.
이진트리의 시간복잡도는 평균적인 경우 O(logN) 이다. 자식 노드가 두 개로 나뉘며 데이터가 위치하므로 일일이 비교할 필요가 없어진다. 하지만 해당하는 데이터가 맨 밑에 해당한다면? 그리고 트리의 구조가 왼쪽이나 오른쪽으로 편향되는 현상이 발생한다면? 이러한 경우를 알고리즘에선 최악의 경우라고 한다. 이 경우 시간복잡도는 O(N)이 된다. 데이터의 수가 많아질수록 O(logN) 과 O(N)은 천지차이다.
이러한 현상을 해결하기 위해 balanced binary tree가 나타났고, 주로 AVL 트리와 RedBlack 트리가 많이 쓰인다.
AVL 트리
AVL 트리 이름 자체는 만든 사람의 이름 Adelson-Velskii의 이름을 따온 것이다. AVL 트리 자체는 이진 트리이지만, 노드의 삽입과 삭제를 수행할 때, 균형치의 값에 따라 RR,LL,RL,LR의 네 가지 방식을 이용해 회전을 시킴으로써 트리의 균형을 유지한다는 것이다. 균형치란 각각의 노드마다 왼쪽 서브트리의 높이를 오른쪽 서브트리의 높이로 뺀 값을 뜻한다. 모든 균형치는 ±1 이하여야 하며, 이를 만족하지 못할 시 회전이 발생한다.
AVL 트리의 장점은 탐색속도가 빠른 이진 트리의 장점을 유지시키는 것과 트리 전체를 재배열시키지 않아도 트리의 균형이 유지된다는 점이다. AVL 트리는 균형치에 따라 트리가 변동되는데 균형치를 어떻게 따지는지 보자.
균형치는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이라고 했다. 혹은 그 반대일수도 있다. 위 그림을 보면 리프노드의 균형치는 모두 0 이다. 0인 이유는 왼쪽 서브트리나 오른쪽 서브트리가 없으므로 값이 높이를 뺀 값이 0이 되기 때문이다. 노드 33의 균형치는 1이다. 왼쪽 서브트리의 높이가 3이고 오른쪽 서브트리의 높이가 2이기 때문이다. 노드 9의 균형치는 -1이다. 왼쪽 서브트리의 높이가 1이고 오른쪽 서브트리의 높이가 2이기 때문이다. 균형치를 구하는 방법을 알아봤으니 균형치에 따라 수행되는 회전들에 대해 알아보자.
AVL 트리의 회전
- LL 회전
LL회전은 LL 상태일 때 발생한다. LL 상태는 새로운 노드를 삽입했을 때, 특정 노드에서 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이를 뺏을 때 2 이상이 나오는 경우다. 이 떄 새로운 노드는 특정 노드의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입된다.
LL 회전은 부모 노드 p의 왼쪽 자식 노드를, 자식 노드 c의 오른쪽 자식 노드로 바꾼다.
노드 c의 오른쪽 자식 노드는 null 이었으므로 부모 노드 p의 왼쪽 자식 노드는 null이 된다.
자식 노드 c의 오른쪽 자식 노드를 부모 노드였던 p로 한다. 이것이 바로 LL 회전이다.
- RR 회전
RR회전은 RR 상태일 때 발생한다. RR 상태는 새로운 노드를 삽입했을 때, 특정 노드에서 오른쪽 서브 트리 높이와 왼쪽 서브 트리 높이를 뺏을 때 2 이상이 나오는 경우다. 이 떄 새로운 노드는 특정 노드의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입된다.
RR 회전은 부모 노드 p의 오른쪽 자식 노드를, 자식 노드 c의 왼쪽 자식 노드로 바꾼다.
노드 c의 왼쪽 자식 노드는 null 이었으므로 부모 노드 p의 오른쪽 자식 노드는 null이 된다.
자식 노드 c의 왼쪽 자식 노드를 부모 노드였던 p로 한다. 이것이 바로 RR 회전이다.
- LR 회전
LR 회전은 LR 상태일 때 발생한다. LR 상태는 새로운 노드를 삽입했을 때, 특정 노드에서 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이를 뺏을 때 2 이상이 나오는 경우다. 여기까지는 LL회전과 비슷하지만, 다른 점은 특정 노드의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입된다는 점이다.
LR 회전은 자식 노드 c에 대해서 RR 회전을 진행한다.
RR 회전을 진행하면 위 그림과 같아진다.
그 후 부모 노드 p에 대해서 LL 회전을 수행한다.
결과는 위 그림과 같다.
- RL 회전
RL 회전은 RL 상태일 때 발생한다. RL 상태는 새로운 노드를 삽입했을 때, 특정 노드에서 오른쪽 서브 트리 높이와 왼쪽 서브 트리 높이를 뺏을 때 2 이상이 나오는 경우다. 여기까지는 RR회전과 비슷하지만, 다른 점은 특정 노드의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입된다는 점이다.
RL 회전은 자식 노드 c에 대해서 LL 회전을 진행한다.
LL 회전을 진행하면 위 그림과 같아진다.
그 후 부모 노드 p에 대해서 RR 회전을 수행한다.
결과는 위 그림과 같다.
사진 및 내용 출처 - https://gurumee92.tistory.com/146