균형 이진 트리 효율
프로그래밍 질문 게시판이 없을 때 자유 게시판에다가 올렸던
질문이었는데, 답변이 없다가, 게시판 성격에 맞지 않아
삭제됐던 질문입니다. 꼭 알고 싶은 내용이라, 다시 한 번
올려 봅니다.
균형 이진 트리를 구현했습니다. AVL 트리죠.
그런데 인터넷을 뒤져보니, Red-Black 트리가 더 빠르다는 얘기가 있더군요.
그래서 libavl 제작자에게 메일을 보냈습니다. 보낸 메일하고 답장을
어디 저장해 놨는지 찾을 수가 없네요. 하여간 내용이 대충 이랬거든요?
{
질문 Red-Black 트리가 더 빠르다는 얘기를 여러 곳에서 들었다. 당신이 쓴
http//www.msu.edu/user/pfaffben/avl/avl.html 메뉴얼을 보면 회전수가
avl 은 1 이고, red-black 은 lg n 인데, 이것은 avl 이 더 빠르다는
것을 의미하지 않나? 여러 소스를 분석해봐도 red-black 은 트리 균형을
위해 반복 루프를 사용한다.
답변 (Ben Pfaff,libavl 제작자)
나도 그런 이상한 얘기를 들었지만, 확실한 이유는 모른다. 알게되면 나도 좀
알려주라. 하지만, 회전수보다는 트리 높이가 탐색에서 중요한 의미를
갖는다. avl 은 1.44 lg (n + 2) - .328 이고 red-black 은 2 lg (n + 1)
이다. 결국 avl 이 높이가 더 작다. 가장 좋은 방법은 둘 다 코딩해서
속도를 측정해보는 것이다.
}
하여간 제가 많은 red-black 트리 구현 소스를 다운로드해서 검토해봐도
avl 보다 빠르다는 건 이해가 안됐죠. 그래서 red-black 이 더 빠르다고
주장하는 2명을 찾아 유사한 질문을 보냈습니다.
http//www.cs.washington.edu/homes/sds/
Sean Sandys
이 사람은 red-black 이 빠르다고 노래 개사(The Red-Black Tree Song)
까지 해놨습니다.
http//hissa.ncsl.nist.gov/dads/HTML/redblack.html
Paul E. Black
Paul E. Black 에게서 답변이 왔습니다.
Dear Hee S. Chung,
I took some time to study AVL and Red-Black a little. I
think you are right about the number of rotations. Unhappily
I cannot explain why red-black trees would be faster than
AVL trees and I don't have the time to study it more.
회전수에 대해서는 제 말이 맞는데, 레드 블랙이 왜 더 빠른지는
모르겠다는 거죠. 더 이상 여기에 관심을 둘 시간도 없고...
어쨌든 제 결론으론 avl 이 red-black 보다 더 빠릅니다. 혹시
red-black 이 더 빠른 이유를 알고 계신분이 있나요?
Re: 균형 이진 트리 효율
제가 알기로는 AVL tree는 가장 depth가 깊은 path와 얕은 path의 차이가
최대 1(혹은 상수.??) 가 되도록 tree를 유지하는 것입니다.
red black tree는 그 둘의 차이가 최대 2배가 되게 유지하는 것이구요.
두 트리는 data를 insert, find, delete를 할 때, 임의로 rotation을 해서
depth를 유지하는데, 평균적으로 보았을 때, 그러한 임의적인 rotation에
의한 조작이 red-black tree에서 훨씬 적게 일어난다는 것이죠.
왜냐하면 조건이 훨씬 더 loose하니까요..(depth가 2배까지 허용..)
즉, red-black tree는 tree depth도 적당히 log n으로 유지해 주고,
rotation도 너무 자주 일어나지 않는 자료구조+알고리즘 인데반해,
AVL tree는 tree depth는 좀더 strict하게 유지하지만 rotation이
너무 자주 일어나므로 red-black tree에 비해서 좀 느린 거죠.
마치 각 변의 길이의 합이 일정할 때 정사각형이 가장 면적이
넓은 것과 비슷한가...요? ;;
p.s) 제 "생각" 이므로 틀릴 수 있습니다.
p.s2) 설마 평균적인 rotation 수가 AVL tree가 더 작다고 말씀하시는건
아니겠죠?
Re^2: 균형 이진 트리 효율
답변 감사합니다.
일단, 메뉴얼에는 평균 회전수에 대한 언급은 없습니다만,
최대 회전수에 대한 언급은 있습니다.
Maximum number of rotations per insertion
AVL RB = 1 lg n
Maximum number of rotations per deletion
AVL RB = lg n lg n
님께서 지적하신 평균 회전수가 최대 회전수보다 작은지는
잘 모르겠습니다만, 노드가 많아질수록 RB 는 최대 회전수가
1 이상인 값이 됩니다.
다음 님께서 find 에서도 rotation 이 있을거라 말씀하셨는데,
잘 못 생각하신 것 같구요... find 에는 회전이 일어나지
않으니, 탐색 속도는 어쨌든 AVL 이 약간 더 빠르다고 봐야될 것
같습니다. 높이가 더 낮으니까요.
libavl 제작자도 답변에서, 둘 다 구현해서 비교해보는 방법
밖엔 없다더군요. 전 아직 AVL 구현한 것 밖에 없어서
비교는 못해봤습니다. libavl 로는 테스트해보지 않았구요.
어쨌든, 제가 본 코드상으로는 RB 가 더 빠를 것 같은
생각이 들지 않더군요... 시원스럽게 평균 회전수에 대한
수식이 있다면 좋을텐데 말이죠.
Re: 균형 이진 트리 효율
탐색속도만을 따진다면 트리의 깊이에 의존하게 되니 당연 깊이를
모두 동일하게 조정하는 구조가 가장 빠른탐색을..하지만.. 트리생성
시간을 따지면 문제는 상당히 여러가지 변수가 작용하겠는데요....
[참고]STL에서도 red-black 트리를 쓰더군요.
ANSI C++ STL의 대부분의 구현에서
sorted associated containers(set, map 등)
는 red-black 트리로 되어 있습니다.
Re^2: [참고]STL에서도 red-black 트리를 쓰더군요.
예, 저도 STL 소스를 본 적이 있습니다. red-black 이지요.
그리고, mSQL 은 mmap 으로 구현한 AVL 입니다.
이론적인 식이 없다면 실시간 성능 테스트 없이는 누가 빠르다고
딱히 말하기 어려울 것 같습니다.
결국은 Red-Black 을 구현해봐야 겠네요.
libavl 을 이용해서도 테스트 해보구요...
오래전 글이지만 댓글 달아봅니다.
간단하게 말씀드리겠습니다.
AVL Rotation = 1
RBTree Rotation = log n
이라고 하면, 확실히 n이 늘어날수록
한번 수행될때의 Rotation횟수가 RBTree는 1 이상으로 증가하는 것은 맞습니다.
하지만, 최악의 경우
1,2,3,4,5....~이런식으로 정렬된 데이터를 삽입한다고 했을때
AVL 트리는 매번 Rotation이 1번씩 일어나게 될 것이고,
RB Tree는 훨씬 적은 횟수로 Rotation을 수행하게 될 것입니다.
그 이유는, AVL은 매번 균형을 유지하기 위해서 엄격하게 확인하기 때문이고
RB Tree는 느슨하게 확인하기 때문이겠죠.
정밀한 검사는, 최악의 경우 데이터를 삽입하면서 테스트하는 것이 맞을 것 같습니다만,
아마 제생각엔 제가 말한대로 Rotation 시도 횟수에서 차이가 나기 때문에 RB Tree가 더 빠르다고 하는 것 같습니다.
간단하게 말하면, AVL Tree는 두 세번 삽입때마다 Rotation이 일어나는 데 비해
RB Tree는 2~30번 또는 n이 증가할수록 Rotation이 일어나는 횟수가 더욱 줄어들 뿐만 아니라, 평균적으로 log n의 반만큼도 Rotation하지도 않기 땜문에
성능이 더 좋다고 평가하는 것이라고 생각합니다.
즉
한마디로 amortized complexity 면에서 rb tree가 월등합니다. 상수시간이죠.
그러나 avl tree는 선형시간 입니다.
아니
선형시간이 아니고 똑같이 상수시간이지만 몇회 더 높다고 보면 됩니다
댓글 달기