급한 사람은 이 부분은 안읽어도 된다. 그냥 잡담이나 할 생각이다.
자료구조는 어렵다. 아니, 어렵다기 보다는 귀찮다. 일단 제대로 보면 이해 못할것도 아니거든. 하지만 현업이든 취미든 코딩에 딱히 필요도 없어 보이는 이론에다가, 하루종일 코딩하고 이걸 또 봐야돼? 마치 미적분이나 삼차방정식 같은 실제로는 쓸 일도 없는 수학공식 느낌이 난다. 하지만 정말로? 정말로 쓸 일이 없을까? 자료구조는 자료를 저장하는 방식에 대한 개발자 당신의 선택권을 넓혀줄 수 있다. 단순히 배열에 데이터를 저장하는 것에서부터 DB에 저장하는 것 까지 말 그대로 자료를 저장하는 어떠한 구조에 대해서 할 수 있는 말이 많아진다는 것이다. 게다가 어떻게 보면 가장 중요한 부분일 수 있는데, 자료구조를 잘하면 코딩테스트를 잘 보고 좋은 회사에 들어갈 확율이 높아진다.
"저희 분야에서는 자료구조 전혀 필요 없는데요?" 그런 분야가 정말 있는지 모르겠지만, 만약 정말 필요가 없으시다면 나도 모르겠다. 그래도 알아서 나쁠것 없잖아요?
트리는 이러한 자료구조에서 어떻게 보면 가장 근본이 되는 것이라고 할 수 있다. 저장, 탐색, 삽입, 삭제 등등 자료에서 가장 중요한 동작을 트리를 통해 구현하고 생각해 볼 수 있다. 따라서 중요한 만큼 종류도 많고 봐야 할 것들도 많지만, 공부를 시작하면 코드를 작성하는 눈이 조금 달라질 것이다. 나도 뭐, 고수는 아니지만 공부를 진행하면서 점점 코드를 짜는 관점이 달라지는 느낌을 받는다. 서론이 너무 길었다, 본론으로 들어가 보자.
먼저, AVL트리에서 AVL이라는 이름에는 사실 큰 의미가 없다. 그냥 해당 트리에 대한 내용이 담긴 논문 작성자들의 이름에서 따와서 지어진 것이다. 개념 자체는 완전히 새로운 것은 아니었으며 Self-balancing binary search tree의 일종이라고 생각해도 좋을 것 같다. AVL트리 말고도 Red-black tree도 Self-balancing binary search tree의 일종인데, 이는 나중에 설명해볼 기회가 있을 것 같다. 다시 설명으로 돌아오면, AVL트리는 간단히 말해서 "특정 부모노드를 기준으로 그의 자식노드들의 높이(층 수라고 해야할지)차이가 1이하여야 한다"는 규척을 만족하는 트리이다. 이를 높이 균형 성질(height-balance property)을 만족한다고 하는데, 위의 설명은 조금 단순화 한 것이고, 조금 더 자세하게 설명을 하겠다. 우선 조건을 만족하는 트리를 보면서 확인해 보자
AVL 트리의 특징은
- 트리 T에서 특정 노드 N의 왼쪽 자식노드 L과 오른쪽 자식노드 R의 높이차이는 1이하여야 한다. 이는 T의 모든 노드에서 만족한다.
- 트리 T에서 특정 노드 N의 왼쪽에 있는 모든 자식노드들의 value는 N의 value보다 작아야 하며, 오른쪽에 있는 모든 자식노드들의 value는 N의 value보다 커야한다. 이는 T의 모든 노드에서 만족한다.
이렇게 정의할 수 있다. 이 두가지가 모두 만족해야 AVL 트리라고 할 수 있다. 예시로 든 트리의 이미지를 보면 알겠지만, 위의 특징 1,2를 전부 만족한다는 걸 알 수 있다. 반대로 만족하지 않는 트리를 예로 들자면
위 이미지의 트리는 2의 특징은 만족했지만 1의 특징인 높이차이가 1이하여야 한다는 조건을 만족하지 못한다. value가 8이나 12인 노드를 기준으로는 왼쪽 노드들의 높이와 오른쪽 노드들의 높이차이가 2가 되버리기 때문이다.
AVL트리를 만족하는 조건은 이해했다고 치자.
이는 BST(이진 탐색 트리)의 탐색, 삽입, 삭제 등의 트리의 동작에 필요한 시간복잡도가 트리의 높이에 비례하여 늘어나기 때문이다. Big O표기를 따르자면 BST 동작들의 시간복잡도는 O(h)이며 여기서 h는 height, 즉 트리의 높이가 된다. 결국 트리의 높이가 한쪽만 기형적으로 늘어나면, 노드의 수는 많지 않더라도 높이때문에 동작이 느려지게 된다. 따라서 AVL트리의 특징을 지키면서(높이차이를 유지하면서) 삽입이나 삭제를 실행할 수 있다면 시간복잡도를 O(log n)으로 유지할 수 있다는 것이다.
자, 이제 AVL트리가 무엇인지 대충 이해가 됐을 것으로 생각한다. 그리고 동시에, 눈치가 빠른 사람이라면 한가지 사실을 알아차렸을 것이다. 어라? AVL트리는 특정 조건을 만족해야 하기 때문에 일반적인 이진트리처럼 삽입과 삭제를 해서는 안되겠는걸? 그렇다. 트리에서 노드를 삭제하거나 삽입하면 당연히 기존의 트리 모양에 변화가 일어난다. 당연하게도, 그 과정에서 트리가 AVL의 조건을 만족하지 못하는 일이 생길수도 있다는 것이다.
위의 이미지는 오른쪽의 AVL트리에 value가 14인 노드를 삽입하는 것을 에로 든 것이다. 위와 같이 그냥 값을 넣기만 해도 AVL트리의 조건을 해치지 않는다면 좋겠지만 많은 경우가 그렇지 않을 것이라는 짐작은 자명한 것이다. 따라서 AVL트리에서의 삽입과 삭제에는 특별한 방법을 사용하는데, 이를 Rotation이라고 한다. rotation이란 "회전"이라는 뜻을 가지고 있으며, 이에 맞게 트리의 한 부분을 회전시키면서 AVL트리는 십입과 삭제동작을 실시한다. 이에 대한 예시를 보고 제대로 설명으로 들어가도록 하자.
자 위의 잘 설명된 이미지를 보면 value가 3인 노드가 삽입되면서 위에서 설명했던 1의 규칙이 위반되게 된다. 하지만 마지막 이미지에서 value가 5와 10인 노드를 기준으로 회전(위치를 변경)하면서 높이를 조정하고 있다. 물론 그냥 위치만 변경한 것은 아니고 조건에 맞게 value가 8인 노드의 부모노드를 변경했다. 어느정도 이해가 되었는가? 마치 오른쪽으로 회전하는 것 처럼 노드의 위치를 변경하여 AVL트리의 조건을 만족시켜줬다. 이는 그나마 간단한 rotation의 예로 더 복잡한 방식은 밑에서 알아보도록 하자.
자, Rotation에 대해서 제대로 알아볼 시간이다. 짐작이 가겠지만, 조금 헷갈릴 수도 있다.
- 삭제나 삽입 원하는 동작을 실행한다. 이러한 동작은 일반적인 BST(이진탐색트리)와 같은 방식이다.
- 동작 후 트리가 AVL의 조건을 만족하지 않는다면, 조건을 만족시키지 않게 된 트리의 가장 아래 노드를 찾고(노드 z로 칭한다) 그 노드로부터 거슬러 올라가서 가장 처음 조건이 만족하지 않게 된 노드(노드 w로 칭한다)를 찾는다.
- 노드 w에서 노드 z로 가는 경로에서 w의 부모노드를 x, 조부모노드를 y라고 칭하자.
- 노드 x와 y의 위치에 따라 노드 w의 자식 노드들을 이용하여 적절한 회전을 실행한다.
이를 실제로 그려서 확인해 보면 이런 경우가 나올 수 있다.
w
/ \
y n1
/ \
n2 x
/ \
n3 z
자, 예를 보고 4번 설명에서 햤던 얘기를 떠올려 보자. x와 y의 위치에 따라 적절한 회전을 실행한다고 했다. 그 위치와 적잘한 회전은 무엇일까? 여기에는 4가지 경우의 수가 나올 수 있다. 아래 설명은 모두 노드 w를 기준으로 한다.
- y와 x노드가 왼쪽, 왼쪽 순서의 경로에 있는 노드이다.
- y와 x노드가 왼쪽, 오른쪽 순서의 경로에 있는 노드이다.
- y와 x노드가 오른쪽, 오른쪽 순서의 경로에 있는 노드이다.
- y와 x노드가 오른쪽, 왼쪽 순서의 경로에 있는 노드이다.
참고로 위에서 예를 든 트리의 경우 y와 x가 w의 왼쪽, 오른쪽 순서의 경로에 있는 노드이므로 두번째 경우에 속한다. 위치를 알았다면 회전은 어떻게 해야 할까?
위의 이미지는 value가 10인 노드가 w, 5인 노드가 y 4인 노드가 x노드가 된다. x의 왼쪽자식으로 w노드를 삽입하면서 조건이 만족하지 않게 됐다. x와 y의 위치를 보면 알겠지만 왼쪽, 왼쪽 순서로 배치되어 있다. 이 경우에는 w노드와 y노드를 기준으로 오른쪽으로 회전시켜주면 된다. 그렇게 하면 트리는 다시 조건을 만족하게 되는 것이다. 하지만 단순한 회전은 아니고 value가 8인 노드의 경우에는 연결을 때어서 변경된 트리에 다시 연결해 주는 작업이 필요하다. 알고리즘을 구현할 때 참고하여야 할 것이다.
왼쪽 오른쪽의 경우에는 조금 복잡하다. 1번의 경우에서 예를 든 트리와 처음에는 같은 모습이지만 새로운 노드가 삽입되면서 경우가 달라졌다. 노드 w를 기준으로 y와 x노드가 왼쪽과 오른쪽에 위치하게 된다. 이 경우에는 총 두번의 회전이 필요한데, y와 x의 위치와 마찬가지로 왼쪽으로 한번 회전하고 오른쪽으로 한번 회전해야 한다. 방향이 같아서 외우기 쉬울것 같다. 처음 왼쪽 회전은 y와 x를 기준으로 회전시켜서 1번의 경우와 비슷한 모습을 만들어 준 후, 역시 1번과 같은 방식으로 w와 y노드를 기준으로 오른쪽으로 회전시켜 밸런스를 유지해 준다.
오른쪽 오른쪽의 경우는 왼쪽 왼쪽과 사실 방향만 다르지 같은 방식이다. value가 30인 w노드와 value가 35인 y노드를 기준으로 이번에는 왼쪽으로 회전시키면 된다. 왼쪽 왼쪽은 오른쪽, 오른쪽 오른쪽은 왼쪽으로 기억하면 좋을 듯 하다.
오른쪽 왼쪽의 경우 역시 왼쪽 오른쪽과 반대의 회전을 차례대로 실행해 주면 된다. 이젠 w, x, y노드를 찾는 건 문제도 아닐 것이다. 다만 이번 이미지는 x와 z에 해당하는 노드가 같은 위치에 있다. 삽입된 노드가 x의 위치를 한다는 얘기이다. 물론 달라질 건 없다. x와 y노드를 기준으로 오른쪽으로 회전시킨 후 y와 w를 기준으로 왼쪽으로 회전시키면 된다. 아마 이 타이밍에 알아차린 사람이 있을 것 같은데, 조건을 만족시키지 않는 노드를 트리의 오른쪽이나 왼쪽 끝으로 변경한 후 마지막 회전을 실행한다는 것이다. 그래서 왼왼, 오른오른의 경우에는 한번의 회전만으로 조건을 만족시키는게 가능하다. 이게 무슨 특별한 법칙인지는 모르겠으나 기억해두면 좋을 것 같다.
자, 이렇게 해서 AVL트리에 대한 내용을 한번 알아보았다. 하지만 한가지 하지 않은 것이 있는데, 코드로 구현하는 부분이다. 사실 이건 일부러 하지 않았다. 내가 여기에 코드를 올린다고 하면 Javascript일 텐데, 다른 언어를 주력으로 하는 사람들도 많을 것이고, 같다고 하더라도 스스로 해보는 편이 좋다. 원리만 이해하면 못할 것도 없다고 본다. AVL트리는 처음에 설명했던 것 처럼 트리의 높이를 밸런스있게 조정하면서 탐색이나 기타 동작에 들어가는 시간복잡도를 일정하게 유지할 수 있다. 따라서 그런 면에서는 다른 트리에 비해서 유리한 점이 있겠으나, 단점은 구현이 복잡해 진다는 것이다. 지금까지 알아본 것만 하더라도 이미 구현이 쉽지는 않겠다는 생각이 들 것이다. 실제로도 삽입, 삭제등의 동작을 구현하는 것이 꽤 어렵고 코드도 길어진다. 따라서 만약 트리를 활용해야 할 일이 있다면 구현의 어려움을 감안해서 사용해 볼 수 있을 것이다.