Balanced Binary Search Tree
균형이진탐색트리
균형이진탐색트리를 알아보기 앞서 하나씩 끊어서 설명해보자.
먼저 이진트리란 각 노드의 자식노드가 최대 2개인 노드로 이루어진 트리를 의미한다.
다음은 이진탐색트리는 위에 설명한 이진트리의 조건을 만족하면서, 각 노드는 왼쪽 자식노드보다는 크거나 같고, 오른쪽 자식노드보다는 작거나 같은 조건을 만족하는 트리를 의미한다.
이진탐색트리를 사용하는 이유는 빠르게 원하는 데이터에 대한 탐색이 가능하기 때문이다. 이진탐색트리의 시간복잡도는 O(h) = O(logN)의 시간복잡도를 가지게 된다.
하지만, 노드의 삽입 순서에 따라서 연결리스트와 같은 형태로 노드가 구성될 수 있다.
이경우는 0(h) = log(N)이 되고 이진탐색트리를 이용한 빠른 검색이 불가능하다.
그렇기 때문에 트리의 높이를 어떻게 구성하는냐에 따라 O(logN)의 시간복잡도를 가지게 되는 것이다. 이를 고려한 트리형태가 균형이진탐색트리이다.
균형이진탐색트리는 N개의 노드를 가진 이진탐색트리의 높이가 log(N)에 비례하게 유지하는 트리를 의미한다. 강제로 h를 log(N)을 유지하게 하는 것을 말한다.
균형이진탐색트리에는 AVL트리, Red-Black트리, 2-3-4트리, splay트리 등이 있다.
어떻게 h를 log(N)을 유지하게 할까?
트리에 새로운 노드가 삽이되거나, 삭제될시 높이가 변화하게 되는데, 이때 log(N)보다 커지려고 하면 기준을 두고 재조정을 해서 높이가 log(N)을 유지하게 한다.
Rotation을 통해서 전체트리의 재구성한다. 재구성이 되면 높이가 변화하게된다.
AVL트리
모든 노드에 대해서 각 노드의 왼쪽부트리와 오른쪽 부트리의 높이차가 1이하인 이진탐색트리를 AVL트리라고 한다.
