05년 11월 8일에 작성한 글이다.

당시 알고리즘을 어느정도 완성했지만 자세한 분석은 너무 힘들고, 왠지 내 Time efficiency 계산에 확신을 가질 수가 없어서 그냥 접어두었다.

그 알고리즘을 같이 올리려고 했지만 그걸 적어놓은 노트를 집에 놔두고 왔다. 다음에 덧붙여야지..

[#M_펼치기|접기|
이번학기에 듣고 있는 과목중의 하나인 Algorithm Analysis..

그 과목중에 Trasform and Conquer 단원에는 AVL Tree가 나오는데.. 이것은 Binary Tree의 Worst case를 막기 위해 Tree를 전체적으로 Balancing하는 알고리즘이다. 수업에서 그부분을 하면서 다른 생각이 들었다.. 어짜피 AVL Tree는 Data Structure 과목에서 들어서 어느정도 알고 있기 때문에 좀 다른 접근방식을 생각해보았다..

AVL Tree는 모든 Node에서 그 Subtree들의 Height 차이가 1을 넘지 않도록 Balancing을 한다.. 그리고 내가 생각한 것은 모든 Node에서 그 Subtree 들의 Weight(모든 Node의 갯수) 차이가 1을 넘지 않도록 하는것이다. 쉽게 말해 그 Tree를 언제나 Complete Binary Tree에 가깝도록 만드는것이다.

그 아이디어를 교수님께 말씀드렸더니 그런 알고리즘이 있는지는 잘 모르겠다고 한번 짜보라고 하신다.. 그게 지난주 금요일이였고 며칠동안 고민한 끝에 알고리즘을 정리했다.

일단.. 같은 개념의 알고리즘이 이미 존재하는지를 알아봐야하는데.. 적어도 많이 쓰이는 알고리즘중에는 없는것 같다. 제대로 뒤지려면 정말 빡셀것 같아서 일단 이미 존재하는지에 대해선 신경쓰지 않기로 했다. 어짜피 논문까지 쓸건 아니니까...

알고리즘의 Time Efficiency를 구해본 결과.. Average case의 경우에 Ta(n) = n^(log2 1.5) 으로 Logarithm보다는 느리고 Linear보다는 빠르다. 이것을 AVL과 비교해봐야 하는데.. AVL의 경우 일단 Insertion, Deletion, Serach 모든 경우에 Logarithm이라고 하지만 Insertion과 Deletion 후에는 Balancing을 해야하기 때문에 어느정도로 시간이 늘어나는지 아직 정확히 알아내지 못했다. 특히 Deletion의 경우엔 Implementation 자체가 복잡해서 잘 쓰지 않을정도라고 하니 어느정도 시간이 소요되는건 분명하다. 그래도 내가 계산한 알고리즘보다는 빠를꺼라고 생각된다. 혹시라도 AVL이 더 느리다면 논문 써야지... ㅡㅡ;;

그렇다면 이 알고리즘의 장점은 무엇일까.. 우선 Tree를 언제나 Complete Tree에 가깝게 유지시키기 때문에 특별히 Worst case나 Best case가 나타나지 않고 언제나 Average case( log2 (n-1) ~ log2 (n+1) )로 유지된다는 것이다. AVL의 경우엔 Height 차이를 1로 유지한 상태에서 (책에 따르면) 1.4405 log2 (n+2) - 1.3277 까지 지연된다. 그리고 AVL tree의 Implementation이 얼마나 복잡할지는 모르겠지만 적어도 이 알고리즘은 Implementation이 매우 간단하다. Insertion과 Deletion의 과정에 Balancing이 포함되어있기 때문에 속도를 좀더 늘리려고 하지 않는 이상 필요한 Function이 Search를 포함해서 3개뿐이다.

이 알고리즘의 정리는 일단락되었으니 AVL의 경우를 더 조사해서 비교분석을 해봐야겠다.._M#]