이진탐색트리

 

이진탐색트리란?

 

이진 탐색트리 자료구조는 트리 기반 구조로 비선형 자료구조이다. 우선 이진 탐색 트리는 이진 트리와, 이진 탐색 기법을 합친 개념으로

 

이진 트리 구조로 이루어져있고, 모든 노드가 최대 두개 이하의 자식을 가지고 있는 구조다.

 

이진 탐색 기법이란 정렬된 배열에서 가운데 위치한 요소를 기준으로 왼쪽은 작은 요소들, 오른쪽은 큰 요소들로 구분하여 탐색할 요소가 있으면 가운데 위치한 요소와 비교하여 더 작거나, 더 큰 위치의 배열로 이동해 이 과정을 반복하는 탐색 기법으로 빠르게 해당 요소를 찾을 수 있는 방식이다.

 

이진 탐색 트리는 이 둘 개념을 합쳐 완전 이진 트리 구조를 이루며, 해당 노드의 왼쪽 서브 트리는 모두 해당 노드 보다 작은 요소들, 그리고 오른쪽 서브 트리는 큰 요소들로 이루어진 완전 이진 트리로 구성되어 있다. 이진 탐색 트리의 구현 원리는 이러한 구조가 유지 되어야한다.

 

이진탐색트리 구조

 

이진탐색트리 구현 원리

 

이진 탐색 트리의 추가(Insert)에 있어서 해당 트리의 Root가 없으면 Root가 될 것이고, 아니라면 Root 부터 시작해 들어온 해당 요소가 더 작으면 왼쪽, 더 크면 오른쪽 서브 트리로 이동하며 이러한 과정을 반복해 노드의 빈 위치에 삽입하게 될 것이다. 

이진탐색트리 삽입

 

이진 탐색 트리의 삭제(Remove)에 있어서는 해당 노드가 말단 위치에 있었다면 그 위치를 삭제해주면 될 것이고, 해당 노드가 자식을 하나 가지고 있었다면, 해당 노드의 자식의 부모를 자신의 부모로, 해당 노드의 부모의 자식을 자신의 자식으로 연결 구조만 바꿔 주면 될 것이다. 마지막으로 노드가 자식을 둘을 가지고 있었다면, 해당 노드를 자신의 왼쪽 서브 트리에서 최대값 또는 오른쪽 서브 트리에서의 최소값으로 변경해주면 이진 탐색 트리 구조를 유지하게 될 것이다.

 

이진탐색트리 삭제

 

이진탐색트리 불균형

 

이러한 이진 탐색 트리는 탐색에 있어서 O(logN)만큼의 시간 복잡도로 매우 빠르게 요소를 찾을 수 있을 것이다. 하지만 최악의 경우 O(N)만큼의 시간 복잡도를 가지게 될 수 있는데, 만약에 요소가 1, 2, 3, 4, 5 순서로 들어오게 되었다면 오른쪽으로 계속 자라나는 트리를 만들게 될 것이다. (이진탐색트리 불균형)

 

불균형 해결방법

 

균형을 맞추는 자가균형트리로 해결 할 수 있다. 자가균형트리에는 AVL 트리와 레드-블랙 트리가 있고, 이 둘은 불균형 상태가 발생 했을 때 회전 알고리즘을 더해 균형을 맞추는 알고리즘을 사용한다. 레드 블랙 트리는 빨간 색과 검정 색 플래그를 사용하여 둘의 불균형이 일어나면 균형을 맞추는 알고리즘을 사용하게 된다.

 

이진탐색트리 불균형

 

다음은 AVL트리의 회전 이미지 

 

피봇을 기준으로 좌회전, 우회전하는 AVL 트리