Binary Search Tree (BST)의 특징 BST의 성능은 트리 높이에 의해서 결정된다. 입력되는 값의 순서에 따라 트리가 균형을 이룰 수도 있지만, 균형이 깨질 수도 있다. 삽입/삭제 과정에서 최적의 경우에는 O(log n)의 시간 복잡도를 가지지만, 최악의 경우에는 O(n)의 시간 복잡도를 가진다. AVL Tree (Adelson-Velsky and Landis Tree) 스스로 균형을 유지하는 트리를 AVL Tree라고 한다. 모든 노드에 대하여 각각의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하이다. C언어로 AVL Tree 구조체를 구현하면 다음과 같다. typedef struct AVLNode { int data; struct AVLNode* left; struct AVLN..
