자가 균형 이진 탐색 트리

[자료구조] 트리, AVL 트리

AVL Tree (AVL은 발명자 세명의 이름에서 따왔다) 자가 균형 이진 탐색 트리. 이진 탐색 트리에서, 노드들이 삽입시 한쪽으로 편향되면 결국 탐색에서 O(N)의 시간이 걸리게 된다. * 그림 : 편향트리. 이진 탐색 트리의 편향트리를 극복하기 위해 재구성(회전, Rotate)을 통해 트리를 균형있게 만든다. AVL 트리는 다음과 같은 특징을 가진다. 이진 탐색 트리(BST)의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이차이가 최대 1이다. 삽입, 삭제 등 어떤 시점에서 높이 차이가 1보다 커지면 회전(Ratation)을 통해 균형을 맞춰 높이를 1로 맞춘다. AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색 ,삭제의 시간 복잡도는 O(log N) 이다. AVL 트리는 균형이 무너졌..