Data Structure
-
GLib의 GTree로 알아보는 균형 이진 트리 알고리즘Programmer/Computer Science 2013. 8. 20. 17:31
GLib에서 제공하는 균형 이진 트리(balanced binary tree)의 구현인 GTree의 알고리즘을 살펴보자. GTree는 AVL tree (Adelson-Velskii and Landis' tree) 알고리즘을 사용하였다. 우선 균형 상태에 대한 정의부터 해야하겠다. 트리 A가 균형 상태라고 하면A의 하위 트리(subtree) A(L)과 A(R)이 균형 상태이고A(L)과 A(R)의 높이의 차이가 1 이하이다. abs(height(A(L)) - height(A(R))) balance left->balance left->balance > 0 LR node->balance > 1 node->right->balance >= 0 RR node->right->balance < 0 RL..