AVL 트리에 대하여 알아봅시다.

        아델슨 A, 벨스키 v, 랜디스 L 는 자체적으로 균형을 잡는다는 뜻의 
        
        데이터 구조 즉, 최초의 자기 균형 이진 검색 트리를 개발 했습니다.
        
        이것이 AVL 트리 입니다.

        
        AVL 트리에서, 두 서브 트리의 높이의 차는 최대 1 만큼 차이가 납니다. 
       
        그런데 어떤 시점에서 이 높이 차이가 1 보다 클 때, AVL 트리는
        
        스스로 균형을 잡습니다.
        
        
        그런데 AVL 트리에서는 어떻게 스스로 균형을 잡을까요?

       
        AVL 트리에서 검색, 삽입, 삭제는 평균 및 worst 인 경우 O(log n) 이
        
        걸립니다. 그런데 삽입과 삭제는 트리 로테이션을 통해서
        
        균형을 잡을 수 있습니다.
        
        일반적인 이진 탐색 트리처럼 node 를 삽입, 삭제할 때,
        
        트리의 높이 균형 속성이 흐트러집니다. 그런데 AVL 트리에서는 
        
        이때 트리 로테이션을 통해서 트리를 재구성하여 높이의 
        
        균형을 맞춥니다.
        
        
        이제 AVL 트리에서 node 를 삽입하는 방법을 알아보겠습니다.

        
        AVL 트리에서 node 를 새롭게 삽입할 때, 삽입 하려는 node 를
        
        AVL 트리의 리프 node 의 서브 node 로 삽입 합니다.
        
        
        이때 AVL 트리의 균형이 흐트러질 수 있습니다. 
        
        이 균형을 맞추기 위해 AVL 트리는 로테이션 하여
        
        균형을 맞춥니다.
        
        보다 자세한 설명은 강의를 참고 하세요.