[알고리즘] 탐색트리(1) - 설명

탐색트리는 사전의 두 번째 형태로써 이진트리로 구현되며 탐색, 삽입, 삭제의 주요 작업을 지원한다.

이진트리를 구현하는 방식에 따라 탐색트리를 이진탐색트리, AVL트리, 스플레이 트리로 나눌 수 있다.

이진탐색트리는 내부노드에 (키, 원소) 쌍을 저장하며 다음의 성질을 만족하는 트리이다.

- u, v, w는 모두 트리노드며 u와 w가 각각 v의 왼쪽 오른쪽 부트리에 존재할 때 key(u) < key(v) <= key(w)가 성립

이로인해 이진탐색트리를 중위순회를 하면 키가 증가하는 순서로 방문하게 된다.

이진탐색트리 주요메소드

1) 탐색(findElement(k)) : 루트에서 출발해서 하향경로를 추적, 현재노드보다 키보다 작으면 왼쪽 부트리, 크면 오른쪽부트리, 같다면 원소를 반환한다. 탐색의 실패했을 경우, NoSuchKey를 반환한다.

2) 삽입(insertItem(k, e)) : 키k를 탐색하고 k가 트리에 존재하지 않을경우, 잎w에 도달하여 w에 k를 삽입 후 expandExternal(w)로 w를 내부노드로 확장한다

3) 삭제(removeElement(k)) : 키k를 탐색하고 노트 w의 자식 중 하나라도 외부노드(z)라면 reduceExternal(z)로 w와 z를 트리로부터 삭제한다. 

만약 삭제되어야 할 키 k가 내부노드만을 자식들로 가지고 있다면, 아래의 작업을 거친다.

- 트리T에 대해 w의 중위순회 계승자 y와 그 자식노드 z을 찾아낸다.

     · 노드 y는 우선 w의 오른쪽 자식으로 이동한 후, 거기서부터 왼쪽 자식들만을 따라 끝까지 내려가면 도달하게 되는 마지막 내부노드며, 노드 z         은 y의 왼쪽 자식인 외부노드이다.

     · y는 T를 중위순회할 경우 노드 w 바로 다음에 ㅂㅇ문하게 되는 내부노드이므로 w의 중위순회 계승자(indorder successor)라 불린다.

     · 따라서 y는 w의 오른쪽 부트리 내 노드 중 가장 왼쪽으로 돌출된 내부노드이다.

- y의 내용을 w에 복사한다.

- reduceExternal(z) 작업을 사용하여 노드y와 z를 삭제한다.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

AVL트리는 트리 T의 모든 내부노드 v에 대해 v의 자식들의 좌우 높이 차이가 1을 넘지 않는(높이균형 속성) 이진탐색트리이다.

AVL트리는 삽입과 삭제로 인해 불균형이 생길 수 있다. 따라서 균형검사를 통해 불균형을 찾고, 개조(불균형을 수리)한다.

AVL트리 주요메소드

1) 탐색 : 이진탐색트리와 같다.

2) 삽입 : 이진탐색트리와 같으나, 균형을 잃을 수 있기 때문에 searchAndFixAfterInsertion을 호출하여 균형검사를 수행하고 만약 불균형이 있으면 개조를 통해 높이균형 속성을 회복한다.

3) 삭제 : 이진탐색트리와 같으나, 균형을 잃을 수 있기 때문에 searchAndFixAfterRemoval을 호출하여 균형검사를 수행하고 만약 불균형이 있으면 개조를 통해 높이균형 속성을 회복한다.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

스플레이트리는 트리의 노드가 (탐색 또는 갱신을 위해)접근된 후 스플레이되는 이진탐색트리를 말한다. 또한 스플레이 트리는 사용되는 환경에 적응하여 재조정되는 양식으로 작동되므로 일종의 자기조정 이진탐색트리이다.

스플레이트리는 3가지의 이점을 갖는다.

- AVL트리에서 요구되는 높이균형 유지가 불필요하기 때문에 비교적 단순하다

- 탐색, 삽입, 삭제에 O(log n) 상각실행시간을 제공한다

- 스플레이트리의 자기조정성은 각 항목에 대한 접근빈도가 균등하지 않은 사전에 사용하면 매우 유리하다.

스플레이트리 주요메소드

	어떤 노드를 스플레이 하는가
탐색	키가 어떤 내부노드에서 발견되면 그 노드를 스플레이 그렇지 않으면 탐색 실패 지점 외부노드의 부모노드를 스플레이
삽입	새로 삽입한 내부노드를 스플레이
삭제	실제로 삭제된 내부노드의 부모노드를 스플레이

탐색트리의 성능

	findElement	insertItem	removeElement	공간사용량
이진탐색트리	최악의 경우O(n)	최악의 경우O(n)	최악의 경우O(n)	O(n)
AVL트리	O(log n)	O(log n)	O(log n)	O(n)
스플레이트리	상각실행시간O(log n)	상각실행시간O(log n)	상각실행시간O(log n)	O(n)

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사