기출19

BST의 성능을 향상시킨 방법을 하나 예로 들어 간단히 설명하라?
===> AVL이 있다. BST의 문제점은 초기 입력값에 따라 Tree의 Balance가 달라져서, 최악의 경우 검색 시간이 O(n)이 될 수 있다. AVL는 초기 입력값에 상관없이, 노드를 삽입하다가, Balance가 달라지는 경우의 Insert를 할 때, 노드를 재배치 하여 다시 좌우 Sibling 노드들의 balance를 유지하여 검색속도를 항상 O(log n)으로 보장해준다.