Red Black Tree vs Heap vs AVL Tree

계획

학습한 내용

Red Black Tree vs Heap vs AVL Tree

알고리즘 문제를 풀면서 TreeMap을 사용한 일이 있었다. 내가 알기로 TreeMap은 Heap 꼴의 형태를 취하고 있고, 값을 넣으면 그때마다 element을 채워나가는 식이라고 알고 있었다.

 

그런데 내가 짜려는 알고리즘은 element를 모두 채운 후에 sort하는 작업이 들어가도 되는 것이라, 매번 값을 넣으면 그때마다 트리를 찾아 가는게 비효율적이라 생각했다. 따라서 HashMap으로 만든 다음에, putAll로 넣으면 한 번에 값을 넣고 sort하는게 아닐까? 하는 생각이 들어 메서드를 확인해 보았다.

 

    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }

위 코드는 TreeMap이 사용하는 putAll의 일부이다. 정확히는 TreeMap이 상속하는 AbstractMap의 putAll이다. 값을 한 번에 sort하는게 아니라 element들을 하나하나 넣는 식으로 동작한다.

 

따라서 이번 기회에 왜 이렇게 동작하는지 공부 해보았다.

 

우선, TreeMap이 사용하는 자료구조는 Red-Black Tree이다. HashMap에서 특정 bucket에 hash collision이 자주 발생하면 Linked List가 아니라 Red-Black Tree가 되는데 이때 많이 들어본 것 같다.

 

Red-Black Tree의 특징은 Binary Tree(이진 트리)의 노드가 편향될 경우, 시간 복잡도가 O(N^2)에 가까워지는 것을 보완해서 트리의 밸런스를 맞춰준다. (여기서 그럼 AVL이랑 뭐가 다르지? 하는 생각이 들었다)

 

Red-Black Tree의 경우 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치해서 밸런스를 맞춘다. (여기서 Heap과 유사성을 느꼈다)

 

탐색 연산은 BST랑 똑같으나, 삽입 / 삭제의 경우 균형을 맞추는 추가 연산을 필요로 한다. 그렇다면 AVL Tree와는 무엇이 다른 걸까? 바로 balance를 맞추는 방식이다. balance를 맞추는 방식을 굳이 달달 외우고 있어야 할 필요는 못느끼기 때문에 내용을 보고싶다면 다음 자료를 참고하기 바란다.

• https://velog.io/@agugu95/%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B7%A0%ED%98%95-RED-BALCKAVL
• https://www.happycoders.eu/algorithms/red-black-tree-java/

여기서 주목해야할 특징은 AVL Tree의 경우 Restructoring하는 과정에서 더 많은 작업을 수행한다고 한다. 따라서 Insert / Delete 성능이 RBT와 비교해 비교적 떨어진다. 대신 트리 깊이가 낮아 검색 성능이 더 빠르다.

출처 : https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/

그렇다면 bucket collision이나 TreeMap에 AVL이 아닌 RBT를 사용할까? 내 예상에 애플리케이션 단에서 해결하고 싶은 건 주로 읽기보다는 삽입 / 삭제일 경우가 많기 때문이라는 생각이 든다. (Hash Collision 방식이 Opean Addressing이 아니라 Sepearate Chaining으로 결정한 것도 그 이유라고 알고 있다)DB의 경우 데이터를 다수 저장해 놓고 데이터를 읽어오면 된다지만, 애플리케이션의 경우 값을 읽으려면 매번 값을 넣어놓아야 하는 작업이 수행되어야 하기 때문은 아닐까 하는 생각이 든다.

 

또한 RBT의 경우 데이터 수가 적을 때 검색 성능도 AVL 보다 빠를 수 있다고 한다. 다음은 밑 주소에서 본 벤치마크 자료이다.

 

https://codereview.stackexchange.com/questions/277861/c-stl-like-avl-tree-benchmark-vs-my-red-black-tree-and-stdset

 

TreeSet
Time to find 50000 elements:
Average : 19758.7656 us,
Stdev : 9610.9668 us,
95% : 40658.7344 us,
99% : 47869.8672 us,
99.9% : 53613.1094 us,

 

AVL
Time to find 50000 elements:
Average : 19861.9648 us,
Stdev : 10665.3408 us,
95% : 38907.1016 us,
99% : 47714.2930 us,
99.9% : 121964.1719 us,

 

그렇다면 heap과의 차이점은 무엇일까? heap은 priority queue에 주로 사용되며, 최댓값 최솟값(루트) 검색시 O(1)이라는 측면은 같다. 가장 큰 차이점은 Heap은 루트만 꺼내볼 수 있다는 것이다. 따라서 필요 용도에 따라 다르게 사용할 수 있다.

 

예를 들어서 많은 수의 데이터에서 매번 최대값만 꺼내올 경우 굳이 RBT를 사용할 이유가 없다. RBT를 사용하면 아마 insert / delete에 더 많은 비용이 사용될 것이다.

 

결국 내가 원하는 식으로 전체를 다 받아서 정렬하는 방향을 원한다면, array를 활용한 정렬들(퀵, 병합, ...)을 사용하는 편이 좋겠다. 값을 매번 update하기 보다는 한 번에 딱 받아서 사용할 경우에는 정렬을 사용하는게 더 좋아보인다