이진 탐색 트리 Binary search tree
이진 검색 트리라고도 하며, 이진 트리에 탐색을 위한 조건을 추가한 자료구조다. 조건은 다음과 같다.
- 모든 원소는 유일한 키값을 갖는다.
- 왼쪽 서브 트리의 원소 키들은 그 루트의 키보다 작다.
- 오른쪽 서브 트리의 원소들은 그 루트의 키보다 크다.
- 왼쪽 오른쪽 서브트리도 모두 이진 탐색 트리다.
그림의 예를 보자. 그림의 맨 위, 루트노드의 키값은 5이다. 오른쪽 자식노드의 키값 7이며 5보다 크다. 왼쪽 자식 노드의 키값은 3이며 5보다 작다. 이번엔 왼쪽 서브트리를 보자. 왼쪽 자식 노드의 키값은 1이며 3보다 작다. 4는 부모노드의 키값 3보다 크기 때문에 오른쪽으로 가게 된다.
이진 탐색 트리 - 검색
키값이 x인 값을 찾으려 한다. 이진 탐색 트리의 특성에 따르면 된다.
- x = 루트노드의 키값이면 검색 성공.
- x > 루트노드의 키값이면 오른쪽 서브트리에서 검색을 수행.
- x < 루트노드의 키값이면 왼쪽 서브트리에서 검색을 수행.
이진 탐색 트리 - 삽입
검색 연산을 기반으로 시작한다. 먼저 검색에 성공하면 같은 값이 있으므로 삽입할 수 없다.
검색에 실패하면 검색에 실패한 위치에 원소를 삽입하면 된다.
이진 탐색 트리 - 삭제
마찬가지로 검색에 실패하면 삭제가 불가능하고 검색에 성공해야만 삭제할 수 있다.
삭제할 노드가 존재하면 자식노드의 갯수에 따라 경우가 나뉜다.
1. 단말노드인 경우는 바로 삭제를 하면 된다.
2. 삭제할 노드가 하나의 자식 노드를 가졌을 때는, 삭제한 노드의 자리를 자식 노드에게 물려준다.
3. 자식노드가 둘인 경우에는 후계자에게 물려준다.
3번을 보자. 후계자의 선택 방법에는 2가지가 있다. 왼쪽 서브트리에서 가장 큰 자손노드를 선택하거나,
오른쪽 서브트리에서 가장 작은 자손노드를 선택하는 것이다.
이진 탐색 트리의 연산 수행 시간
보통 노드 수가 n이고 높이 h라면 삽입, 삭제, 검색 시간은 O(h)가 된다.
만약 트리의 좌우 균형이 맞다면 삽입, 삭제, 검색 시간은 O(log n).
편향 이진 트리라면 삽입, 삭제, 검색 시간은 O(n)이다.
힙 Heap
가장 큰 키값을 빠르고 쉽게 찾을 수 있도록 만든 완전 이진 트리다.
최대힙 Max heap은 키값이 가장 큰 노드이며, 부모노드의 키값이 자식 노드의 키값보다 크거나 같다.
최소힙 Min heap은 키값이 가장 작은 노드이며, 부모노드의 키값이 자식노드의 키값보다 작거나 같다.
삽입, 삭제 연산은 완전 이진트리의 형태와, 최대·최소힙의 특성만 지키면 어렵지 않다.
삽입했다면 노드수가 n+1인 완전 이진 트리로 재조정하고 마지막 위치에 값을 삽입한다. 그리고 현재 위치에서 부모노드와 크기를 비교한다. {현재부모노드의 키 값 ≥ 삽입 원소의 키 값}을 지키면 된다.
그림에서 보이듯 최대힙의 삽입 시간은 O(log n)이다.
삭제 연산도 노드 n-1개의 완전 이진 트리를 지키며 재조정하면 된다.
삭제시간은 O(log n), 조회시간은 O(1)이다.