10장 탐색 트리(1)

2024. 1. 3. 22:07ㆍ프로그래밍 공부/Data Structure

10.1 이진 탐색 트리

탐색 트리(search tree): 딕셔너리를 구현하는 데 사용할 수 있는 트리 자료 구조

따라서 딕셔너리 ADT의 기본적인 메소드를 간단히 검토하는 것으로 시작하겠다:

• find(k): 키가 k인 항목이 있으면 반환한다.
• findAll(k): 키가 k인 모든 항목의 반복 가능한 컬렉션을 반환한다.
• insert(k,x): 키 k와 값 x를 가진 엔트리를 삽입한다.
• remove(e): 입력 e를 제거하고 반환한다.
• remove All(k): 키 k로 모든 엔트리를 제거하고 해당 값의 반복자를 반환한다.

메소드 find는 k를 찾지 못하면 null을 반환한다. 

정렬된 딕셔너리 ADT는 키나 엔트리의 이전이나 

이전을 탐색하는 추가적인 메소드들을 포함하고 있지만, 그 성능은 find와 비슷하다. 

그래서 우리는 이 장에서 일차적인 탐색 연산으로서 find에 초점을 맞출 것이다.

이진 트리는 키에 정의된 순서 관계를 가진다고 가정할 때 

딕셔너리의 항목을 저장하기 위한 훌륭한 자료 구조이다. 

앞에서 언급한 바와 같이(7.3.6절), 

이진 탐색 트리(binary search tree)는 이진 트리 T이므로 

T의 각 내부 노드 v는 다음과 같은 항목(k,x)을 저장한다:

• v의 왼쪽 하위 트리의 노드에 저장된 키가 k보다 작거나 같다.
• v의 오른쪽 하위 트리에 있는 노드에 저장된 키는 k보다 크거나 같다.

아래와 같이 T의 노드에 저장된 키는 

각 내부 노드 v를 비교하여 탐색을 수행하는 메소드를 제공하며, 

이들은 v에서 멈추거나 v의 왼쪽 또는 오른쪽 자식에서 계속될 수 있다. 

따라서 여기서는 이진 탐색 트리가 비어 있지 않은 올바른 이진 트리라는 관점을 갖는다. 

즉, 우리는 항목을 이진 탐색 트리의 내부 노드에만 저장하고 

외부 노드는 "자리표시자" 역할만 한다. 

이 접근 방식은 몇 가지 탐색 및 업데이트 알고리즘을 단순화한다. 

덧붙여서, 우리는 공간 사용이 더 좋지만 

더 복잡한 탐색 및 업데이트 메소드를 희생시키면서 

부적절한 이진 탐색 트리를 허용할 수도 있었다.

이진 탐색 트리를 적절한 것으로 보든 그렇지 않든 상관없이, 

이진 탐색 트리의 중요한 속성은 정렬된 딕셔너리(또는 맵)을 구현하는 것이다. 

즉, 이진 탐색 트리는 부모와 자식 사이의 관계를 사용하여 

키의 순서를 계층적으로 나타내야 한다. 

구체적으로, 이진 탐색 트리 T의 노드들 중 중위 순회(7.3.6절)는

키들을 감소하지 않는 순서로 방문해야 한다.


10.1.1 탐색

이진 탐색 트리 T로 표현된 딕셔너리 D에서 

연산 find(k)를 수행하기 위해 트리 T를 의사 결정 트리로 본다(그림 7.10 참조). 

이 경우 T의 각 내부 노드 v에서 질문하는 것은 

탐색 키 k가 노드 v에 저장된 키보다 작거나 같거나 크거나 key(v)로 표시되는 것이다. 

만약 답이 "더 작으면", 왼쪽 부분 트리에서 탐색을 계속한다. 

만약 답이 "동일하면", 탐색이 성공적으로 종료된다.

 

만약 답이 "더 크"면, 탐색은 오른쪽 하위 트리에서 계속된다. 

마지막으로, 외부 노드에 도달하면, 탐색은 성공적으로 종료된다

(그림 10.1 참조)

그림 10.1: 

(a) 정수 키를 가진 딕셔너리 D를 나타내는 이진 탐색 트리 T; 

(b) D에서 find(76)(성공) 및 find(25)(실패) 연산을 실행할 때 T의 노드가 방문한다. 

단순화를 위해 키는 표시하지만 입력 값은 표시한다.



이 접근 방식은 코드 조각 10.1에서 자세히 설명한다. 

탐색 키 k와 T의 노드 v가 주어지면 

트리 탐색은 v에 뿌리를 둔 T의 서브트리 T(v)의 노드(위치) w를 반환하므로 

다음 중 하나가 발생한다:

• w는 내부 노드이며 w의 엔트리는 k와 같은 키를 갖는다.
• w는 순서 순회에서 k의 적절한 위치를 나타내는 외부 노드이다
T(v)의 k는 T(v)에 포함된 key가 아니다.

따라서 메소드 find(k)는 TreeSearch(k, T.root())를 호출하여 수행할 수 있다. 

w: 이 호출에 의해 반환되는 T의 노드

w가 내부 노드이면 w의 엔트리를 반환하고, 그렇지 않으면 null을 반환한다.

코드 조각 10.1: 이진 탐색 트리에서 재귀적 탐색.

Algorithm TreeSearch(k, v):

      if T.isExternal(v) then

          return v

      if k < key(v) then

          return TreeSearch(k, T.left(v))

      else if k > key(v) then

          return TreeSearch(k, T.right(v))

      return v              { we know k = key(v)}


이진 탐색 트리 분석

이진 탐색 트리 T에서 탐색하는 최악의 경우 실행 시간을 분석하는 것은 간단하다. 

알고리즘 트리 탐색은 재귀적이며 

각 재귀적 호출에 대해 일정한 수의 원시 연산을 수행한다. 

트리 탐색의 각 재귀적 호출은 이전 노드의 자식에 대해 이루어진다. 

즉, 트리 탐색은 루트에서 시작하여 

한 단계씩 내려가는 T 경로의 노드에서 호출된다. 

따라서 이러한 노드의 수는 h + 1로 제한된다. (h: T의 높이)

즉, 탐색에서 발견되는 노드당 O(1) 시간을 소비하므로 

딕셔너리 D에서 찾는 메소드는 O(h) 시간으로 실행된다.

(h: D를 구현하는 데 사용되는 이진 탐색 트리 T의 높이)(그림 10.2 참조)

그림 10.2: 이진 탐색 트리에서 탐색 실행 시간을 보여준다. 

그림은 이진 탐색 트리를 큰 삼각형으로 보고 

루트에서 오는 경로를 지그재그 선으로 보는 표준 시각화 바로가기를 사용한다.


우리는 또한 위 알고리즘의 변형이 

O(h + s) 시간에 All(k)를 찾는 연산을 수행한다는 것을 보여줄 수 있다. 

s = 반환된 엔트리 수

물론 T의 높이 h는 n만큼 클 수 있지만, 

우리는 일반적으로 그것이 훨씬 더 작기를 기대한다. 

실제로 우리는 10.2절에서

탐색 트리 T의 높이에서 O(logn)의 상한을 유지하는 메소드를 보여줄 것이다. 

그러나 이러한 방식을 설명하기 전에 

딕셔너리 업데이트 메소드에 대한 구현을 설명하겠다.


10.1.2 업데이트 연산

이진 탐색 트리를 사용하면 상당히 간단하지만 

사소하지 않은 알고리즘을 사용하여 insert 및 remove 연산을 구현할 수 있다.

 

삽입

적절한 이진 트리 T가 다음 업데이트 연산을 지원한다고 가정해 보겠다: 
insertAtExternal(v,e): 외부 노드 v에 요소 e를 삽입하고
v를 내부로 확장하여 새(공허한) 외부 노드 자식을 갖는다. 

v가 내부 노드인 경우 오류가 발생한다.

이 메소드를 사용하면 

코드 조각 10.2에 주어진 TreeInsert(k, x, T.root())를 호출하여 

이진 탐색 트리 T로 구현된 딕셔너리에 대해 insert(k, x)를 수행한다.

코드 조각 10.2: 이진 탐색 트리에 삽입하기 위한 재귀적 알고리즘.

Algorithm TreeInsert(k, x, v):

      Input: A search key k, an associated value, x, and a node v of T

      Output: A new node w in the subtree T(v) that stores the entry (k, x)

      w ← TreeSearch(k, v)

      if k = key(w) then     {the key at w is equal to k, so recurse at a child}

          return TreeSearch(k, T.left(v))   {going to the right would be correct too}

      T.insertAtExternal(w, (k, x))              {this is an appropriate place to put (k, x)}

      return w  


이 알고리즘은 T의 루트에서 외부 노드로 가는 경로를 추적하여

새로운 엔트리를 수용하는 새로운 내부 노드로 확장한다. 

이진 탐색 트리에 삽입하는 예를 그림 10.3에 나타낸다.

그림 10.3:

키 78의 엔트리를 그림 10.1의 탐색 트리에 삽입한다. 

삽입할 위치를 찾는 것은 (a)에 표시되며, 

그 결과 트리는 (b)에 표시된다.


제거

이진 탐색 트리 T로 구현된 딕셔너리 D에 

remove(k) 연산을 구현하는 것은 좀 더 복잡한데, 

트리 T에 "구멍"을 생성하는 것을 원하지 않기 때문이다. 

이 경우 적절한 이진 트리가 다음과 같은 추가 업데이트 연산을 지원한다고 가정한다:

removeExternal(v): 

v의 부모를 v의 형제로 대체하여 외부 노드 v와 해당 부모를 제거한다. 

v가 외부에 없으면 오류가 발생한다.

이 연산이 주어지면 

T에서 TreeSearch(k, T.root())를 호출하여 

k와 같은 키를 가진 엔트리를 저장하는 T의 노드를 찾음으로써 

딕셔너리 ADT의 remove(k) 연산 구현을 시작한다. 

만약 TreeSearch가 외부 노드를 반환한다면, 

딕셔너리 D에 k 키를 가진 엔트리가 없고 null을 반환한다 (그리고 완료되었다). 

만약 TreeSearch가 대신 내부 노드 w를 반환한다면, 

w는 제거하고자 하는 엔트리를 저장하고, 

(난이도가 증가하는) 두 가지 경우를 구별한다:

• 노드 w의 자식 중 하나가 외부 노드, 예를 들어 노드 z인 경우, 

단순히 T에서 removeExternal(z) 연산을 통해 T에서 w와 z를 제거한다. 

이 연산은 T에서 w와 z를 모두 제거하고, 

z를 z의 형제로 대체하여 T를 재구조화한다(그림 10.4 참조)

• 노드 w의 두 자식이 모두 내부 노드일 경우, 

T에 "구멍"이 생기므로 

단순히 노드 w를 T에서 제거할 수 없다. 

대신 다음과 같이 진행한다(그림 10.5 참조):

○ 우리는 T의 순서대로 진행하는 첫 번째 내부 노드 y를 찾는다. 

노드 y는 w의 오른쪽 부분 트리에서 가장 왼쪽에 있는 내부 노드이며, 

먼저 w의 오른쪽 자식으로 가고 거기서 왼쪽 자식을 따라 T 아래로 내려간다. 

또한, y의 왼쪽 자식 x는 T의 순서대로 진행하는 노드 w를 바로 뒤따르는 외부 노드이다.

○ w에 저장된 엔트리를 임시 변수 t에 저장하고, y의 엔트리를 w로 이동한다. 

이 동작은 w에 저장된 이전 엔트리를 제거하는 효과가 있다.

○ T 위에서 removeExternal(x)를 호출하여 T에서 노드 x와 y를 제거한다. 

이 작업은 y를 x의 형제로 대체하고 T에서 x와 y를 모두 제거한다.

 

○ 임시 변수 t에 저장한 w에 미리 저장한 항목을 반환한다.

이 제거 알고리즘은 탐색 및 삽입과 마찬가지로 

루트에서 외부 노드로 경로를 이동하여 

이 경로의 두 노드 사이에서 항목을 이동한 다음 

해당 외부 노드에서 removeExternal 작업을 수행한다.

그림 10.4: 그림 10.3b의 이진 탐색 트리에서 제거: 

외부 자식이 있는 노드(w)에 제거할 항목(키 32 포함)이 저장된다. 

(a) 제거 전에

(b) 제거 후에.


그림 10.5: 그림 10.3b의 이진 탐색 트리에서 제거: 

제거할 항목(키 65로)이 자식이 둘 다 내부에 있는 노드(w)에 저장된다. 

(a) 제거 전; 

(b) 제거 후.

 


이진 탐색 트리의 성능

탐색, 삽입 및 제거 알고리즘의 분석도 비슷하다. 

저희는 방문한 각 노드에서 O(1) 시간을 보내며, 

최악의 경우 방문한 노드 수는 T의 높이 h에 비례한다. 

따라서 이진 탐색 트리 T로 구현된 딕셔너리 D에서

find, insert 및 remove 메소드는 O(h) 시간으로 실행된다. (h: T의 높이)

따라서 이진 탐색 트리 T는 T의 높이가 작은 경우에만 

n개의 원소가 있는 딕셔너리를 효율적으로 구현하는 것이다. 

최상의 경우 T의 높이는 h = log(n + 1)이므로 

모든 딕셔너리 작업에 대해 로그 시간 성능을 얻을 수 있다. 

그러나 최악의 경우 T의 높이는 n이며, 

이 경우 딕셔너리의 정렬된 리스트 구현처럼 보이고 느끼게 된다. 

예를 들어 키가 증가하거나 감소하는 순서로 일련의 원소를 삽입하면 

이러한 최악의 구성이 발생한다(그림 10.6 참조)

그림 10.6: 키가 있는 항목을 순서대로 삽입하여 얻은 선형 높이의 이진 탐색 트리의 예.



이진 탐색 트리로 구현된 딕셔너리의 성능은 다음 명제와 표 10.1에 요약되어 있다.

명제 10.1: n개의 키 값 엔트리에 대한 높이 h를 갖는 이진 탐색 트리 T는 

O(n) 공간을 사용하고 다음 실행 시간으로 딕셔너리 ADT 연산을 실행한다. 

연산 size와 isEmpty는 각각 O(1) 시간이 걸린다. 

연산 find, insert, remove는 각각 O(h) 시간이 걸린다. 

연산 findAll은 O(h + s) 시간이 소요된다.

(s: 반환되는 컬렉션의 크기)

표 10.1: 이진 탐색 트리에 의해 실현된 딕셔너리의 주요 메소드의 실행 시간. 

h: 트리의 현재 높이

s: findAll로 반환되는 컬렉션의 크기

공간 사용량: O(n)

n: 딕셔너리에 저장된 엔트리 수

 

메소드 시간
size, isEmpty O(1)
find, insert, remove O(h)
findAll O(h + s)



이진 탐색 트리에서 탐색 및 업데이트 작업의 실행 시간은 트리의 높이에 따라 크게 달라진다. 

그럼에도 불구하고 평균적으로 임의의 일련의 키 삽입 및 제거로부터 생성된

n개의 키를 갖는 이진 탐색 트리가 예상 높이 O(logn)를 갖는다.

 

그런 문장은 우리가 무작위로 삽입하고 제거하는

일련의 의미를 정확하게 정의하기 위한 세심한 수학적 언어와

증명해야 할 정교한 확률 이론을 필요로 하기 때문에

그 정당성은 이 책의 범위 밖이다. 

그럼에도 불구하고 최악의 경우 성능이 떨어지는 점을 염두에 두고 

업데이트가 무작위적이지 않은 애플리케이션에서는 

표준 이진 탐색 트리를 사용할 때 주의해야 한다. 

결국 최악의 경우 탐색 및 업데이트 시간이 빠른 딕셔너리가 필수적인 애플리케이션도 있다. 

다음 절에서 설명하는 자료 구조는 이러한 필요성을 해결한다.


10.1.3 Java 구현

코드 조각 10.3~10.5에서는 BSTEntry(Entry 인터페이스 구현) 클래스의 개체를 

노드에 저장하는 이진 탐색 트리 클래스인 BinarySearchTree를 설명한다. 

클래스 BinarySearchTree는 코드 조각 7.16에서 7.18로 

클래스 Linked BinaryTree를 확장하여 코드 재사용의 이점을 활용한다.

이 클래스에서는 여러 보조 메소드를 사용하여 무거운 리프팅 작업을 많이 수행한다. 

보조 메소드 treeSearch:

treeSearch 알고리즘(코드 조각 10.1)을 기반으로 한다.

find, findAll 및 insert 메소드로 호출된다. 

 

findAll(k) 메소드:

k와 동일한 키로 모든 엔트리를 중위 순회한다는 점에서 재귀적인 addAll 메소드를 사용한다

(빠른 알고리즘을 사용하지는 않지만 찾은 모든 엔트리에 대해 실패한 탐색을 수행하므로). 

 

다음의 두 가지 추가 업데이트 메소드를 사용한다.

insertAtExternal - 외부 노드에 새 엔트리를 삽입한다.

removeExternal - 외부 노드와 그 부모를 제거한다.

클래스 BinarySearchTree에서는 위치 인식 항목을 사용한다(섹션 8.4.2 참조). 

따라서, BSTEntry의 업데이트 메소드는 이동한 BSTEntry 개체에 새 위치를 알려준다. 

또한 자료에 접근하고 테스트하는 데 

checkKey와 같은 몇 가지 간단한 보조 메소드를 사용한다. 

(이 경우 상당히 간단한 규칙을 사용하더라도) 키가 올바른지 확인한다. 

 

인스턴스 변수 actionPos:

가장 최근의 탐색, 삽입 또는 제거가 종료된 위치를 저장한다. 

이 인스턴스 변수는 이진 탐색 트리의 구현에는 필요하지 않지만 

이전 탐색, 삽입 또는 제거가 수행된 위치를 식별하기 위해 

BinarySearchTree(코드 조각 10.7, 10.8, 10.10 및 10.11 참조)를 확장하는 클래스에 유용하다. 

위치 actionPos는 메소드 find, insert 또는 remove를 실행한 직후에 사용되는 경우 의도된 의미를 갖는다.

코드 조각 10.3-10.5: 

클래스 BinarySearchTree. 

// Realization of a dictionary by means of a binary search tree
public class BinarySearchTree<K,V>
  extends LinkedBinaryTree<Entry<K,V>> implements Dictionary<K,V> {
  protected Comparator<K> C; // comparator
  protected Position<Entry<K,V>>
             actionPos; // insert node or remove node's parent
  protected int numEntries = 0; // number of entries
  /** Creates a BinarySearchTree with a defualt comparator. */
  public BinarySearchTree() {
    C = new DefaultComparator<K>();
    addRoot(null);
  }
  public BinarySearchTree(Comparator<K> c) {
    C = c;
    addRoot(null);
  }
  /** Nested class for location-aware binary search tree entries */
  protected static class BSTEntry<K,V> implements Entry<K,V> {
    protected K key;
    protected V value;
    protected Position<Entry<K,V>> pos;
    BSTEntry() { /* defualt comparator */ }
    BSTEntry(K k, V v, Position<Entry<K,V>> p) {   
      key = k; value = v; pos = p;
    }
    public K getKey() { return key; }
    public V getValue() { return value; }
    public Position<Entry<K,V>> position() { return pos; }
  }
  /** Extracts the key of the entry at a given node of the tree. */
  protected K key(Position<Entry<K,V>> position) {
    return position.element().getKey();
  }
  /** Extracts the value of the entry at a given node of the tree. */
  protected V value(Position<Entry<K,V>> position) {
    return position.element().getValue();
  }
  /** Extracts the entry at a given node of the tree. */
  protected Entry<K,V> entry(Position<Entry<K,V>> position) {
    return position.element();
  }
  /** Replaces an entry with a new entry (and reset the entry's location) */
  protected void replaceEntry(Position<Entry<K,V>> pos, Entry<K,V> ent) {
    ((BSTEntry<K,V>) ent).pos = pos;
    replace(pos, ent);
  }
  /** Checks whether a given key is valid. */
  protected void checkKey(K key) throws InvalidKeyException {
    if(key == null)  // just a simple test for now
      throw new InvalidKeyException("null key");
  }
  /** Checks whether a given entry is valid. */
  protected void checkEntry(Entry<K,V> ent) throws InvalidKeyException {
    if(ent == null || !(ent instanceof BSTEntry))
      throw new InvalidKeyException("invalid entry");
  }
  /** Auxiliary method for inserting an entry at an external node */
  protected Entry<K,V> insertAtExternal(Position<Entry<K,V>> v, Entry<K,V> e) {
    expandExternal(v,null,null);
    replace(v, e);
    numEntries++;
    return e;
  }
  /** Auxiliary method for removing an external node and its parent */
  protected void removeExternal(Position<Entry<K,V>> v) {
    removeAboveExternal(v);
    numEntries--;
  }
  /** Auxiliary method used by find, insert, and remove */
  protected Position<Entry<K,V>> treeSearch(K key, Position<Entry<K,V>> pos) {
    if (isExternal(pos)) return pos; // key not found; return external node
    else {
      K curKey = key(pos);
      int comp = C.compare(key, curKey);
      if (comp < 0)
        return treeSearch(key, left(pos));      // search left subtree
      else if (comp > 0)
        return treeSearch(key, right(pos));      // search right subtree
      return pos;         // return internal node where key is found
    }
  }
  // Adds to L all entries in the subtree rooted at v having keys equal to k
  protected void addAll(Position<Entry<K,V>> L, 
                      Position<Entry<K,V>> v, K k) {
    if (isExternal(pos)) return;
    Position<Entry<K,V>> pos = treeSearch(k, v);
    if (!isExternal(pos)) {  // we found an entry with key equal to k
      addAll(L, left(pos), k);
      L.addLast(pos.element());  // add entries in inorder
      addAll(L, right(pos), k);
    } // this recursive algorithm is simple, but it's not the fastest
  }
  // methods of the dictionary ADT
  public int size() { return numEntries; }
  public boolean isEmpty() { return size() == 0; }
  public Entry<K,V> find(K key) throws InvalidKeyException {
    checkKey(key);        // may throw an InvalidKeyException
    Position<Entry<K,V>> curPos = treeSearch(key, root());
    actionPos = curPos;       // node where the search ended
    if (isExternal(curPos)) return entry(curPos);
    return null;
  }
  public Interable<Entry<K,V>> findAll(K key) throws InvalidKeyException {
    checkKey(key);        // may throw an InvalidKeyException
    PositionList<Entry<K,V>> L = new NodePositionList<Entry<K,V>>();
    addAll(L, root(), key);
    return L;
  }
  public Entry<K,V> insert(K k, V x) throws InvalidKeyException {
    checkKey(key);        // may throw an InvalidKeyException
    Position<Entry<K,V>> insPos = treeSearch(k, root());    
    while (!isExternal(insPos)) // iterative search for insertion position
      insPos = treeSearch(k, left(insPos));    
    actionPos = curPos; // node where the new entry is being inserted
    return insertAtExternal(insPos, new BTSEntry<K,V>(k, x, insPos));
  }
  public Entry<K,V> remove(Entry<K,V> ent) throws InvalidKeyException {
    checkKey(key);        // may throw an InvalidKeyException
    Position<Entry<K,V>> remPos = ((BSTEntry<K,V>) ent).position();
    Entry<K,V> toReturn = entry(remPos);  // entry to be returned
    if (isExternal(left(remPos))) remPos = left(remPos); // left easy case
    else if (isExternal(right(remPos))) remPos = right(remPos); // right easy case
    else {             // entry is at a node with internal children
      Position<Entry<K,V>> swapPos = remPos; // find node for moving entry
      remPos = right(swapPos);
      do
        remPos = left(remPos);
      while (isExternal(remPos));
      replaceEntry(swapPos, (Entry<K,V>) parent(remPos).element());
    }
    actionPos = sibling(remPos);    // sibling of the leaf to be removed
    removeExternal(remPos);
    return toReturn;
  }
}        // entries() method is omitted here


10.2 AVL 트리

이전 절에서는 효율적인 딕셔너리 자료 구조가 무엇이어야 하는지에 대해 논의했지만, 

다양한 작업에서 달성되는 최악의 성능은 선형 시간이며, 

이는 리스트 및 배열 기반 딕셔너리 구현의 성능보다 향상되지 않는다. 

(예: 9장에서 설명한 순서 없는 리스트 및 탐색 테이블)

이 절에서는 모든 기본 딕셔너리 작업에 대해 로그 시간을 달성하기 위해 

이 문제를 수정하는 간단한 메소드를 설명한다.


AVL 트리의 정의

간단한 수정은 트리에 대한 로그 높이를 유지하는

이진 탐색 트리 정의에 규칙을 추가하는 것이다. 

이 절에서 고려하는 규칙은 높이 균형 속성이다.

높이 균형 속성(height-balance property): 내부 노드의 높이에 대한 이진 탐색 트리 T의 구조를 나타낸다.

(7.2.1절에서 트리의 노드 v의 높이는 

v에서 외부 노드까지의 가장 긴 경로의 길이임을 상기하자):
높이 균형 속성: T의 모든 내부 노드 v에 대해 v의 자식의 높이는 최대 1만큼 다르다.

AVL 트리: 높이 균형 특성을 만족하는 이진 탐색 트리 T

개발자들의 머리글자인 Adel'son-Vel'skii와 Landis를 따서 이름을 붙였다.

 

AVL 트리의 예는 그림 10.7에 나와 있다.

그림 10.7: AVL 트리의 예시. 

입력된 항목의 키는 노드 내부에 표시되며, 

노드의 높이는 노드 옆에 표시된다.


높이 균형 속성의 직접적인 결과는 

AVL 트리의 부분 트리가 그 자체로 AVL 트리라는 것이다. 

높이 균형 속성은 다음 명제와 같이 높이를 작게 유지하는 중요한 결과도 갖는다.

제안 10.2: n개의 엔트리를 저장하는 AVL 트리의 높이는 O(logn)이다.

정당성: AVL 트리의 높이에서 상한을 직접 찾으려고 하는 대신, 

높이가 h인 AVL 트리의 최소 내부 노드 수 n(h)에서 

하한을 찾는 "역 문제" 작업이 더 쉬운 것으로 나타났다. 

우리는 n(h)가 적어도 기하급수적으로 증가한다는 것을 보여줄 것이다. 

이로부터 n개의 엔트리를 저장하는 AVL 트리의 높이가 O(logn)임을 도출하는 것은 쉬운 단계가 될 것이다.

우선 높이 1의 AVL 트리에는 적어도 하나의 내부 노드가 있어야 하고 

높이 2의 AVL 트리에는 적어도 두 개의 내부 노드가 있어야 하기 때문에 

n(1) = 1 및 n(2) = 2임을 주목하자. 

이제 높이 h와 최소 노드 수를 가진 AVL 트리는 

h ≥ 3의 경우 두 부분 트리 모두 최소 노드 수를 가진 AVL 트리이며, 

하나는 높이 h - 1이고 다른 하나는 높이 h - 2이다. 

근을 고려하여 h ≥ 3에 대해 

n(h)부터 n(h - 1) 및 n(h - 2)까지의 관계를 다음 공식을 얻는다:
n(h) = 1 + n(h−1) + n(h−2).   

(10.1)

이 시점에서 피보나치 진행의 특성(섹션 2.2.3 및 연습 C-4.12)에 익숙한 독자는 

n(h)가 h의 함수 지수임을 이미 알 수 있다.

 

나머지 독자 분들은 저희의 추론을 진행하겠다.

화학식 10.1은 n(h)가 h의 엄밀하게 증가하는 함수임을 암시한다. 

따라서, 우리는 n(h - 1) > n(h - 2)임을 알 수 있다. 

화학식 10.1에서 n(h - 1)을 n(h - 2)로 바꾸고 1을 떨어뜨리면, 

우리는 h ≥ 3에 대해,
n(h) > 2·n(h − 2).
(10.2)

공식 10.2는 n(h)가 h가 2만큼 증가할 때마다

적어도 2배씩 증가한다는 것을 나타내므로 

직관적으로 n(h)가 지수 함수적으로 증가한다는 것을 의미한다. 

이 사실을 공식적으로 보여주기 위해 

공식 10.2를 반복적으로 적용하여

다음과 같은 일련의 부등식을 산출한다:
n(h) > 2·n(h − 2) > 4·n(h − 4) > 8·n(h - 6) >(2^i) ·n(h−2i). 

(10.3)

즉, 임의의 정수 i에 대하여, 

h - 2i ≥1에 대하여 n(h)>(2^i) · n(h-2i)이다. 

n(1)과 n(2)의 값을 이미 알고 있으므로, 

h -2i가 1 또는 2 중 하나가 되도록 i를 선택한다. 

즉, 우리가 선택한다
.
위의 i 값을 식 10.3에 대입하면,

h ≥ 3을 얻을 수 있다,

(10.4)

공식 10.4의 양변에 로그를 취하면 

log n(h) > h/2 - 1,
우리가 얻는 바로는
h < 2logn(h) + 2,
(10.5)


즉, n개의 엔트리를 저장하는 AVL 트리의 높이는 최대 2logn + 2이다.

명제 10.2와 섹션 10.1에 주어진 이진 탐색 트리 분석을 통해 

AVL 트리로 구현된 딕셔너리에서

find 연산은 시간 O(logn)에 실행되고

findAll 연산은 시간 O(logn + s)에 실행된다. 

n: 딕셔너리의 항목 수

s: 반환되는 컬렉션의 크기

물론 삽입 또는 제거 후에도 높이 균형 속성을 유지하는 메소드를 보여주어야 한다.


10.2.1 업데이트 연산

AVL 트리에 대한 삽입 및 제거 연산은 이진 탐색 트리에 대한 연산과 유사하지만 

AVL 트리에 대해서는 추가 계산을 수행해야 한다.


삽입

AVL 트리 T의 삽입은 (단순한) 이진 탐색 트리의 10.1.2절에서 설명한 삽입 연산처럼 시작된다. 

이 연산은 항상 새로운 엔트리를 외부 노드인 T의 노드 w에 삽입하고, 

w를 insertAtExternal 연산으로 내부 노드가 되게 한다. 

즉, w에 2개의 외부 노드 자식을 추가한다. 

그러나 일부 노드의 경우 높이를 1개 증가시키기 때문에 높이 균형 속성을 위반할 수 있다. 

특히, 노드 w, 그리고 아마도 일부 상위 노드의 경우 높이를 1개 증가시키기도 한다. 

따라서 높이 균형을 복원하기 위해 T를 재구성하는 방법을 설명해 보겠다.

이진 탐색 트리 T가 주어졌을 때, 

우리는 v의 자식 높이들 사이의 차이의 절대값이 1이면 

T의 내부 노드 v는 균형이 잡혔다(balanced)고 말하고, 

그렇지 않으면 균형이 맞지 않다(unbalanced)고 말한다. 

따라서 AVL 트리를 특징짓는 높이 균형 속성은 

모든 내부 노드가 균형이 잡혔다고 말하는 것과 같다.

새로운 항목을 삽입하기 전에 T가 높이 균형 특성을 만족하므로 AVL 트리라고 가정한다. 

앞서 언급한 것처럼 T에 대해 insertAtExternal 연산을 수행한 후 

w를 포함한 T의 일부 노드의 높이가 증가한다.

 

이러한 모든 노드는 w에서 T의 루트로 가는 T의 경로에 있으며, 

T의 노드 중에서 방금 불균형 상태가 되었을 수 있는 유일한 노드이다(그림 10.8a 참조). 

물론 이렇게 되면 T는 더 이상 AVL 트리가 아니므로 

방금 발생한 "불균형"을 해결하기 위한 메커니즘이 필요하다.

그림 10.8: 그림 10.7의 AVL 트리에 키 54가 있는 엔트리 삽입 예: 

(a) 키 54에 대한 새 노드를 추가한 후 키 78과 44를 저장하는 노드가 불균형이 되고, 

(b) 트라이노드 재구조화는 높이 균형 속성을 복구한다. 

옆에 있는 노드의 높이를 보여주고 트라이노드 재구조화에 참여하는 노드 x, y, z를 식별한다.



 간단한 "탐색 및 복구" 전략을 통해 이진 탐색 트리 T에서 노드의 균형을 복원한다. 

다음과 같은 노드 x, y z가 있다고 하자.

노드 z: z가 불균형 상태가 되도록 w에서 T의 루트를 향해 올라가는 첫 번째 노드

(그림 10.8a 참조) 

노드 y: 더 높은 높이를 가진 z의 자식

(노드 y는 w의 조상이어야 한다.)

노드 x: 더 높은 높이를 가진(같은 높이는 있을 수 없음) y의 자식

(노드 x는 w의 조사이어야 한다.)

또한 노드 x는 z의 손자이며 w와 같을 수도 있다. 

z가 자식 y에 루트를 둔 부분 트리에 삽입되어 불균형 상태가 되었기 때문에 

y의 높이는 형제 노드보다 2가 더 크다.

이제 코드 조각 10.6에 제공되고 그림 10.8과 10.9에 표시된

트라이노드 재구조화 메소드인 restructure(x)를 호출하여 

z에 뿌리를 둔 부분 트리의 균형을 재조정한다. 

트라이노드 재구조화는 일시적으로 노드 x, y, z를 a, b, c로 이름을 바꾸므로 

T의 순서대로 진행할 때 b와 b가 c보다 먼저 나온다. 

그림 10.9와 같이 x, y, z를 a, b, c에 매핑하는 방법은 네 가지가 가능하며, 

이는 재라벨링에 의해 하나의 경우로 통합된다. 

그런 다음 트라이노드 재구조화는 z를 b라는 노드로 대체하고 

이 노드의 자식을 a와 c로 만들고, 

a와 c의 자식을 T의 모든 노드의 순서 관계를 유지하면서 

x, y, z의 네 개의 이전 자식(x와 y를 제외한)이 되도록 한다.

코드 조각 10.6: 이진 탐색 트리에서의 트라이노드 재구조화 연산.

Algorithm restructure(x):

      Input: A node x of a binary search tree T that a parent y and

           a grandparent z

      Output: Tree T after a trinode restructuring (which corresponds to a single or

           double rotation) involving nodes x, y, and z

     1: Let (a, b, c) be a left-to-right (inorder) listing of the nodes x, y, and z, and let

         (T0, T1, T2, T3) be a left-to-right (inorder) listing of the four subtrees of x, y, and

         z not rooted at x, y, or z.

     2: Replace the subtree rooted at z with a new subtree rooted at b.

     3: Let a be the left child of b, and let T0 and T1 be the left and right subtrees of a,

         respectively.

     4: Let c be the left child of b, and let T2 and T3 be the left and right subtrees of c,

         respectively.


회전(rotation):

  • 트라이노드 재구조화 연산에 의해 트리 T를 수정하는 것
  • 트라이노드 재구조화 연산이 T를 변화시키는 방법을 시각화할 수 있는 기하학적 방법

 

단일 회전(single rotation):

  • b = y인 경우의 트라이노드 재구조화 연산
  • z 위에서 " 회전하는" y로 시각화할 수 있다.
  • (그림 10.9a 및 b 참조). 

 

이중 회전(double rotation):

  • b = x인 경우의 트라이노드 재구조화 연산
  • 처음에는 " 회전하는" x로 y 위에서 그리고 다시 z 위에서 시각화할 수 있다.
  • (그림 10.9c 및 d, 그림 10.8 참조). 

 

일부 컴퓨터 연구자들은 이 두 종류의 회전을 각각 두 개의 대칭형을 갖는 별개의 방법으로 취급한다. 

그러나 우리는 이 네 가지 유형의 회전을 단일 트라이노드 재구조화 연산으로 통합하는 것을 선택했다.

 

그러나 트라이노드 재구조화 방법은 

어떻게 보든 T에 있는 모든 노드의 순서대로 순회하는 순서를 유지하면서 

T에 있는 O(1) 노드의 부모-자식 관계를 수정한다.

순서 보존 특성 외에도 

트라이노드 재구조화는 균형을 복원하기 위해 T에 있는 여러 노드의 높이를 변경한다. 

x의 조부모인 z가 불균형하므로 메소드 restructure(x)를 실행한다는 것을 기억하자. 

더욱이 이러한 불균형은 x의 자식 중 하나가 z의 다른 자식의 높이에 비해 너무 큰 높이를 가지고 있기 때문이다. 

 

회전의 결과로 

x의 "키가 큰" 자식을 위로 이동시키고 

z의 "키가 작은" 자식을 아래로 밀어낸다. 

 

따라서 restructure(x)를 수행한 후에 

부분 트리의 모든 노드가 균형을 이루게 된다. (그림 10.9 참조) 

따라서 x, y, z 노드에 지역적으로(locally) 위치한 높이 균형 속성을 복원한다. 

 

또한 새로운 항목 삽입을 수행한 후 

b에 위치한 부분 트리가 이전에 한 단위 더 큰 z에 위치한 부분 트리를 대체하므로 

이전에 불균형했던 z의 조상은 모두 균형을 이루게 된다. (그림 10.8 참조)
따라서 이 한 번의 재구조화는 전역적으로(globally) 높이 균형 속성을 복원한다.

그림 10.9: 트라이노드 재구조화 연산(코드 조각 10.6): 

(a) 및 (b) 단일 회전; (c) 및 (d) 이중 회전.


제거

insert 딕셔너리 연산의 경우와 마찬가지로

정규 이진 탐색 트리에 대해 이 연산을 수행하는 알고리즘을 사용하여 

AVL 트리 T에 대한 remove 딕셔너리 연산 구현을 시작한다. 

AVL 트리에 대해 이 접근법을 사용하는 데 있어 추가적인 어려움은

높이 균형 속성을 위반할 수 있다는 것이다. 

특히 removeExternal 연산으로 내부 노드를 제거하고 자식 중 하나를 그 자리에 올린 후 

이전에 제거된 노드의 부모 w에서 T의 루트로 가는 경로에 T에 불균형 노드가 있을 수 있다(그림 10.10a 참조). 

실제로 이러한 불균형 노드는 많아야 하나 존재할 수 있다. 


그림 10.10: 그림 10.7의 AVL 트리에서 키 32로 항목 제거: 

(a) 노드 저장 키 32를 제거한 후 루트가 불균형해지고 

(b) (단일) 회전으로 높이-균형 속성이 복원된다.



삽입과 마찬가지로 트리 T에서 균형을 복원하기 위해 트라이노드 재구조화를 사용한다. 

노드 x, y, z를 다음과 같이 가정한다.

노드 z: w에서 T의 루트 쪽으로 올라가는 첫 번째 불균형 노드

노드 y: 큰 높이를 가진 z의 자식

(노드 y가 w의 조상이 아닌 z의 자식이다), 

노드 x: 다음과 같이 정의한 y의 자식

만약 y의 자식 중 하나가 다른 하나보다 크다면 x를 y의 더 큰 자식이라 하고, 

그렇지 않으면(y의 두 자식이 모두 같은 높이를 가지면), x를 y와 같은 쪽에 있는 y의 자식이라 한다

(즉, y가 왼쪽 자식이면 x를 y의 왼쪽 자식이라 하고, 그렇지 않으면 x를 y의 오른쪽 자식이라 한다). 

 

어떤 경우에도, z에 루트를 두고 있다가 현재 임시로 b라고 부르는 노드에 루트를 둔 부분 트리에서 

높이 균형 속성을 지역적으로(locally) 복원하는 restructure(k) 연산을 수행한다(그림 10.10b 참조)

불행히도 이 트라이노드 재구조화는 

b에 루트를 둔 부분 트리의 높이를 1로 줄일 수 있으므로 

b의 조상이 불균형해질 수 있다. 

따라서 z를 재조정한 후에도 불균형 노드를 찾기 위해 T를 계속 걸어 올라간다. 

다른 것을 찾으면 균형을 복원하기 위해 재구조화 연산을 수행하고 

루트까지 더 많은 것을 찾기 위해 T를 계속해서 위로 행진한다. 

그래도 T의 높이는 O(logn)이기 때문에 (n: 엔트리의 수) 

명제 10.2에 의해 O(logn) 트라이노드 재구조화로 높이 균형 속성을 복원할 수 있다.


AVL 트리의 성능

AVL 트리 T의 성능에 대한 분석을 다음과 같이 요약한다. 

연산 find, insert, remove는 T의 루트 노드에서 리프 노드까지의 경로를 따라 방문하고, 

그리고 아마도 형제 노드를 방문하여 노드당 O(1) 시간을 보낸다.

따라서 T의 높이는 명제 10.2에 의해 O(logn)이므로 

위의 연산은 각각 O(logn) 시간이 걸린다. 

표 10.2에서는 AVL 트리로 구현된 딕셔너리의 성능을 요약한다. 

저희는 이 성능을 그림 10.11에 설명한다.

표 10.2: AVL 트리에 의해 실현되는 n개의 엔트리를 가진 딕셔너리의 성능. 

여기서 s는 findAll에 의해 반환되는 컬렉션의 크기를 나타낸다. 

공간 사용량: O(n)

연산 시간
size, isEmpty O(1)
find, insert, remove O(logn)
findAll O(logn + s)


그림 10.11: AVL 트리에서 탐색 및 업데이트의 실행 시간을 보여준다. 

시간 성능: 레벨당 O(1)

다운 페이즈(down phase): 탐색이 포함된다.

업 페이즈(up phase): 높이 값과 지역적 트라이노드 재구조화(회전)을 수행한다.


10.2.2 Java 구현

이제 n개의 엔트리로 구성된 정렬된 딕셔너리를 구현하기 위해 

n개의 내부 노드가 있는 AVL 트리 T를 사용하는 구현 세부 정보와 분석을 살펴보겠다. 

T에 대한 삽입 및 제거 알고리즘은 트라이노드 재구조화를 수행하고 

두 형제 노드의 높이 간의 차이를 결정할 수 있어야 한다. 

이제 재구조화와 관련하여 이진 탐색 트리의 기본 구현에

트라이노드 재구조화 작업을 수행하는 메소드 restructure(x)가 포함되어 있는지 확인해야 한다

(코드 조각 10.6).

 

T를 연결 구조로 구현하면 O(1) 시간으로 restructure 연산을 수행할 수 있음을 쉽게 알 수 있다(섹션 7.3.4). 

우리의 경우 BinarySearchTree 클래스에 이 메소드가 포함된다고 가정한다.

높이 정보와 관련하여, 각 내부 노드의 높이 v를 노드 자체에 명시적으로 저장할 수 있다. 

또는 v의 균형 계수를 v에 저장할 수 있다.

v의 균형 계수(balance factor) = (v의 왼쪽 자식의 높이) - (v의 오른쪽 자식의 높이)

따라서 v의 균형 계수는 항상 -1, 0 또는 1과 같다.

(-2 또는 +2로 일시적으로 같아질 수 있는 삽입 또는 제거 중을 제외한다.)

삽입 또는 제거를 수행하는 동안

O(logn) 노드의 높이와 균형 계수는 영향을 받으며

O(logn) 시간으로 유지될 수 있다.

코드 조각 10.7 및 10.8에서는 완전한 Java 클래스 AVLTree를 보여준다.

완전 자바 클래스 AVLTree의 특징

- AVL 트리를 사용하여 딕셔너리를 구현한다.

  (부모 클래스에는 restructure 메소드의 구현이 포함되어 있다고 가정한다). 

- 이 클래스는 BinarySearchTree(코드 조각 10.3–10.5)를 확장한다.

- 이 클래스는 중첩 클래스 AVLNode를 포함한다.

   AVLNode 클래스: 이진 트리의 노드를 나타내는 BTNode 클래스를 확장한다.

                                노드의 높이를 나타내는 추가 인스턴스 변수 높이를 정의한다. 

   createNode 메소드를 재정의하여 BTNode 클래스 대신 AVLNode 클래스를 사용하도록 이진 트리를 가져온다. 

   createNode 메소드: 새로운 이진 트리 노드를 생성하는 데 전용으로 사용된다.

- 클래스 AVLTree는 슈퍼 클래스인 BinarySearchTree에서 

   size, isEmpty, find 및 findAll 메소드를 상속하지만 

   탐색 트리의 균형을 유지하기 위해 메소드 insert 및 remove를 재정의한다.

1. 메소드 insert(코드 조각 10.8)는

슈퍼클래스의 insert 메소드를 호출함으로써 시작되는데, 

이 메소드는 새로운 엔트리를 삽입하고 

인스턴스 변수 actionPos에 삽입 위치(예를 들어, 그림 10.8의 노드 저장 키 54)를 할당한다. 

 

2. 보조 메소드 rebalance을 사용하여

삽입 위치에서 루트로 경로를 순회한다. 

이 순회는 방문한 모든 노드의 높이를 업데이트하고 

필요한 경우 트라이노드 재구조화를 수행한다. 

 

3. 메소드 remove(코드 조각 10.8)는 

슈퍼클래스의 remove 메소드를 호출함으로써 시작되는데, 

이 메소드는 엔트리의 제거를 수행하고

삭제된 위치를 인스턴스 변수 actionPos에 할당한다. 

 

4. 보조 메소드 rebalance을 사용하여 

제거된 위치에서 루트로 경로를 횡단함으로써 필요한 재구조화를 수행한다.

코드 조각 10.7: 클래스 AVLTree의 생성자 및 보조 메소드.

// Implementation of an AVL tree
public class AVLTree<K,V>
  extends BinarySearchTree<Entry<K,V>> implements Dictionary<K,V> {
  public AVLTreeTree(Comparator<K> c) { super(c); }
  public AVLTreeTree() { super(); }
  /** Nested class for nodes of an AVL tree. */
  protected static class AVLNode<K,V> extends BTNode<Entry<K,V>> {
    protected int height;  // we add a height field to BTNode
    AVLNode() { /** defualt comparator */ }
    /** Preferred comparator */
    AVLNode(Entry<K,V> element, BTPosition<Entry<K,V>> parent, 
         BTPosition<Entry<K,V>> left, BTPosition<Entry<K,V>> right) {   
      super(element, parent, left, right);
      height = 0;
      if(left != null)
        height = Math.max(height, 1 + ((AVLNode<K,V>) left).getHeight());
      if(right != null)
        height = Math.max(height, 1 + ((AVLNode<K,V>) right).getHeight());
    } // we assume that the parent will revise its height if needed
    public void setHeight(int h) { height = h; }
    public int getHeight() { return height; }
  }
  /** Creates a new binary search tree node (overrides super's version). */
  protected BTPosition<Entry<K,V>> createNode(Entry<K,V> element, 
      BTPosition<Entry<K,V>> parent, BTPosition<Entry<K,V>> left, 
      BTPosition<Entry<K,V>> right) {
    return new AVLNode<K,V>(element,parent,left,right);  // now use AVL nodes
  }
  /** Returns the height of a node (call back to an AVLNode). */
  protected int height(Position<Entry<K,V>> p) {
    return ((AVLNode<K,V>) p).getHeight();
  }
  /** Sets the height of an internal node (call back to an AVLNode). */
  protected void setHeight(Position<Entry<K,V>> p) {
    ((AVLNode<K,V>) p).setHeight(1+Math.max(height(left(p)),height(right(p))));
  }
  /** Returns whether a node has balance factor between -1 and 1. */
  protected boolean isBalanced(Position<Entry<K,V>> p) {
    int bf = height(left(p)) - height(right(p));
    return((-1 <= bf) && (bf <= 1));
  }


코드 조각 10.8: 

클래스 AVLTree의 보조 메소드 tallerChild 및 rebalance 및 딕셔너리 메소드 insert와 remove.

// Implementation of an AVL tree
public class AVLTree<K,V>
  extends BinarySearchTree<Entry<K,V>> implements Dictionary<K,V> {
  public AVLTreeTree(Comparator<K> c) { super(c); }
  public AVLTreeTree() { super(); }
  /** Nested class for nodes of an AVL tree. */
  protected static class AVLNode<K,V> extends BTNode<Entry<K,V>> {
    protected int height;  // we add a height field to BTNode
    AVLNode() { /** defualt comparator */ }
    /** Preferred comparator */
    AVLNode(Entry<K,V> element, BTPosition<Entry<K,V>> parent, 
         BTPosition<Entry<K,V>> left, BTPosition<Entry<K,V>> right) {   
      super(element, parent, left, right);
      height = 0;
      if(left != null)
        height = Math.max(height, 1 + ((AVLNode<K,V>) left).getHeight());
      if(right != null)
        height = Math.max(height, 1 + ((AVLNode<K,V>) right).getHeight());
    } // we assume that the parent will revise its height if needed
    public void setHeight(int h) { height = h; }
    public int getHeight() { return height; }
  }
  /** Creates a new binary search tree node (overrides super's version). */
  protected BTPosition<Entry<K,V>> createNode(Entry<K,V> element, 
      BTPosition<Entry<K,V>> parent, BTPosition<Entry<K,V>> left, 
      BTPosition<Entry<K,V>> right) {
    return new AVLNode<K,V>(element,parent,left,right);  // now use AVL nodes
  }
  /** Returns the height of a node (call back to an AVLNode). */
  protected int height(Position<Entry<K,V>> p) {
    return ((AVLNode<K,V>) p).getHeight();
  }
  /** Sets the height of an internal node (call back to an AVLNode). */
  protected void setHeight(Position<Entry<K,V>> p) {
    ((AVLNode<K,V>) p).setHeight(1+Math.max(height(left(p)),height(right(p))));
  }
  /** Returns whether a node has balance factor between -1 and 1. */
  protected boolean isBalanced(Position<Entry<K,V>> p) {
    int bf = height(left(p)) - height(right(p));
    return((-1 <= bf) && (bf <= 1));
  }
  /** Returns a child of p with height no smaller than that of the other child */
  protected Position<Entry<K,V>> tallerChild(Position<Entry<K,V>> p) {
    if(height(left(p)) > height(right(p))) return left(p);
    else if(height(left(p)) < height(right(p))) return right(p);
    // equal height children - break tie using parent's type
    if (isRoot(p)) return left(p);
    if (p == left(parent(p))) return left(p);
    else return right(p);
  }
  /** 
    * Rebalance method called by insert and remove. Traverses the path from
    * zPos to the root. For each node encountered, we recompute its height
    * and performn a trinode restructuring if it's unbalanced.
    */
  protected void rebalance(Position<Entry<K,V>> zPos) {
    if (isInternal(zPos))
      setHeight(zPos);
    while (!isRoot(zPos)) {  // traverse up the tree towards the root
      zPos = parent(zPos);
      setHeight(zPos);
      if (!isBalanced(zPos)) {
        // perform a trinode restructuring at zPos's tallest grandchild
        Position<Entry<K,V>> xPos = tallerChild(tallerChild(zPos));
        zPos = restructure(xPos);  // tri-node restructure (from parent class)
        setHeight(left(zPos));  // recompute heights
        setHeight(right(zPos));
        setHeight(zPos);
      }
    }
  }
  // overridden methods of the dictionary ADT
  public Entry<K,V> insert(K k, V v) throws InvalidKeyException {
    Entry<K,V> toReturn = super.insert(k, v); // calls our createNode method
    rebalance(actionPos); // rebalance up from the insertion position
    return toReturn;
  }
  public Entry<K,V> remove(Entry<K,V> ent) throws InvalidKeyException {
    Entry<K,V> toReturn = super.remove(ent);
    if (toReturn != null)  // we actually removed something
      rebalance(actionPos); // rebalance up the tree
    return toReturn;
  }
} // end of AVLTree class


10.3 스플레이 트리

기본 딕셔너리 연산을 구현할 수 있는 또 다른 방법은 

스플레이 트리(splay tree)로 알려진 균형 탐색 트리 자료 구조를 사용하는 것이다.

 

이 구조는 개념적으로 이 장에서 논의하는 다른 균형 탐색 트리들과는 상당히 다른데, 

왜냐하면 스플레이 트리는 균형을 맞추기 위해 어떤 명시적인 규칙도 사용하지 않기 때문이다. 

대신에, 이 구조는 탐색 트리를 분할된(amortized) 상태로 유지하기 위해 

모든 접근 후에 스플레잉(splaying)이라는 특정한 이동-루트 작업을 적용한다. 

스플레잉 연산은 삽입, 삭제, 심지어 탐색 중에 도달한 가장 아래쪽 노드 x에서 수행된다. 

스플레잉의 놀라운 점은 분할 연산을 통해

삽입, 삭제, 탐색에 대해 분할된 실행 시간, 즉 로그를 보장할 수 있다는 것이다. 

스플레이 트리의 구조는 단순히 이진 탐색 트리 T이다. 

사실 이 트리의 노드에 연결된 추가적인 높이, 균형, 또는 색상 레이블은 없다.


10.3.1 스플레잉

이진 탐색 트리 T의 내부 마디 x가 주어졌을 때, 

일련의 재구조화 과정을 통해 x를 T의 루트로 이동시킴으로써 x를 스플레이한다(splay). 

우리가 수행하는 특별한 재구조화는 중요한데, 

왜냐하면 어떤 재구조화 과정만으로 x를 T의 루트로 이동시키는 것으로는 충분하지 않기 때문이다. 

x를 위로 이동시키기 위해 수행하는 특정한 연산은 

x, 그 부모 y, 그리고 (존재하는 경우) x의 조부모 z의 상대적인 위치에 의존한다. 

우리가 고려하는 것은 세 가지 경우이다.

지그지그(zig-zig): 노드 x와 그것의 부모 y는 둘 다 왼쪽 자식이거나 둘 다 오른쪽 자식이다. 

(그림 10.12 참조) 우리는 T의 노드들의 순서 관계를 유지하면서 

z를 x로 바꾸어 y를 x의 자식으로 만들고 z를 y의 자식으로 만든다.

그림 10.12: Zig-zig: (a) 이전; (b) 이후. 

x와 y가 왼쪽 자식인 다른 대칭 구성이 있다.



지그재그(zig-zag): x와 y 중 하나는 왼쪽 자식이고 다른 하나는 오른쪽 자식이다. 

(그림 10.13 참조) 이 경우, T의 마디들의 순서 관계를 유지하면서 

z를 x로 대체하고 x를 y와 z를 자식으로 만든다.

그림 10.13: 지그재그: (a) 이전; (b) 이후. 

x는 오른쪽 자식이고 y는 왼쪽 자식인 다른 대칭 구성이 있다.


지그(zig): x에는 조부모가 없다

(또는 어떤 이유에서인지 x의 조부모를 고려하지 않는다).

(그림 10.14 참조) 

이 경우 x를 y 위로 회전시켜 

x의 자식을 노드 y로 만들고 

x의 이전 자식 중 하나를 w로 만들어 

T에 있는 노드의 상대적인 순서 관계를 유지한다.

그림 10.14: 지그: (a) 전; (b) 후. 

x와 w가 자식으로 남은 다른 대칭 구성이 있다.


x가 조부모를 가질 때 지그재그 또는 지그재그를 수행하고, 

x가 부모를 갖지만 조부모가 아닐 때 지그재그를 수행한다. 

스플레잉 단계는 x가 T의 루트가 될 때까지 

x에서 이러한 재구조화를 반복하는 것으로 구성된다. 

이것은 x를 루트에 가져오는 단순 회전의 시퀀스와 같지 않다는 것을 유의하자. 

노드의 스플레잉의 예는 그림 10.15와 10.16에 나와 있다.

그림 10.15: 노드를 스플레이하는 예: 

(a) 14를 저장하는 노드를 스플레이하는 것은 지그재그로 시작하고, 

(b) 지그재그 후에,

(c) 다음 단계는 지그지그이다.

(그림 10.16에서 계속)


그림 10.16: 노드를 스플레이하는 예: 

(d) 지그지그 후에; 

(e) 다음 단계는 다시 지그지그 후이다; 

(f) 지그지그 후에. (그림 10.16에서 계속)


10.3.2 스플레이 시점

스플레이를 수행할 때 지시되는 규칙은 다음과 같다:
• 키 k를 탐색할 때, 만약 k가 노드 x에서 발견된다면, 우리는 x를 표시하고, 

그렇지 않으면 우리는 탐색이 성공적으로 종료되는 외부 노드의 부모를 표시한다. 

예를 들어, 그림 10.15와 10.16의 스플레이는

키 14를 성공적으로 탐색한 후에 수행되거나 

키 14.5를 성공적으로 탐색하지 못한 후에 수행된다.

• 키 k를 삽입할 때, 우리는 k가 삽입되는 곳에 새로 생성된 내부 노드를 표시한다. 

예를 들어, 그림 10.15와 10.16의 표시는 14가 새로 삽입된 키일 경우에 수행된다. 

그림 10.17의 스플레이 트리에서 삽입되는 일련의 순서를 보여준다.

그림 10.17: 스플레이 트리의 삽입 순서: 

(a) 초기 트리; 

(b) 2를 삽입 후; 

(c) 스플레잉 후; 

(d) 3을 삽입 후;

(e) 스플레잉 후;

(f) 4를 삽입 후;

(g) 스플레잉 후.



 • 키 k를 삭제할 때 제거되는 노드 w의 부모를 스플레이한다.

 여기서 w는 k를 저장하는 노드 또는 그 하위 노드 중 하나이다.

(이진 탐색 트리에 대한 제거 알고리즘을 호출한다.) 

삭제 후에 표시되는 예는 그림 10.18과 같다.

그림 10.18: 스플레이 트리에서 삭제: 

(a) 노드 r에서 8의 삭제는 

r의 왼쪽 서브 트리에 있는 가장 오른쪽 내부 노드 v의 키 r로 이동하여 

v를 삭제하고 v의 부모 u를 스플레이함으로써 수행된다. 

(b) 스플레이 트리 u는 지그지그로 시작하고, 

(c) 지그지그 후;

(d) 다음 단계는 지그이다; 

(e) 지그 후.


10.3.3 스플레잉의 분할 상환 분석

지그지그나 지그재그 이후에는 x의 깊이가 2만큼 감소하고 

지그 이후에는 x의 깊이가 1만큼 감소한다. 

따라서 x가 깊이 d를 가지면 

스플레잉 x는 d/2 지그지그 및 지그재그의 시퀀스로 구성되며, 

d가 홀수이면 하나의 최종 지그로 구성된다. 

 

단일 지그지그, 지그재그 또는 지그는 일정한 수의 노드에 영향을 미치므로 

O(1) 시간으로 수행할 수 있다. 

따라서 이진 탐색 트리 T에서 노드 x를 스플레잉하는 데는 시간 O(d)가 소요되며, 

(d: T의 x의 깊이)

즉, 노드 x에 대해 스플레잉 단계를 수행하는 시간은 

T의 루트에서 하향식 탐색에서 해당 노드에 도달하는 데 필요한 시간과 점근적으로 동일하다.

 

최악의 경우 시간

최악의 경우, 높이 h의 스플레이 트리에서 탐색, 삽입 또는 삭제의 전체 실행 시간은 O(h)이다. 

게다가, 그림 10.17과 같이 h가 n만큼 클 수도 있다. 

따라서 최악의 경우, 스플레이 트리는 매력적인 자료 구조가 아니다.

스플레이 트리는 최악의 성능에도 불구하고 분할 상환된 의미에서 탁월한 성능을 발휘한다. 

즉, 혼합된 탐색, 삽입 및 삭제 순서에서 각 연산은 평균적으로 로그 시간이 소요된다.

우리는 회계 방법을 사용하여 스플레이 트리의 분할 상환 분석을 수행한다.


스플레이 트리의 분할 상환 성능

분석을 위해 탐색, 삽입 또는 삭제를 수행하는 시간은 

관련 스플레잉 시간에 비례하므로 스플레잉 시간만 고려해 보겠다.

 

T, v, n(v), r(v)를 다음과 같이 정의하자.
T: n개의 키를 가진 스플레이 트리

v: T의 노드

v의 크기 n(v): v에 루트를 둔 부분 트리의 노드 수

이 정의는 다음을 의미한다.

(내부 노드의 크기) = (두 자식의 크기의 합) + 1

노드 v의 순위(rank) r(v): v의 크기의 밑 2에 있는 로그, 즉 r(v) = log(n(v))

분명히 T의 근은 최대 크기 (2n + 1)와 최대 순위인 로그(2n + 1)를 가지며, 

반면에 외부 노드는 크기 1과 순위 0을 가진다.

저희는 T에서 노드 x를 분할하는 작업의 비용을 지불하기 위해 사이버 달러를 사용하고, 

1 사이버 달러는 지그를 지불하고, 

2 사이버 달러는 지그지그 또는 지그재그를 지불한다고 가정한다. 

따라서 깊이 d에서 노드를 분할하는 비용은 d 사이버 달러이다. 

저희는 T의 각 내부 노드에 사이버 달러를 저장하는 가상 계정을 유지한다. 

이 계정은 분할 상환 분석 목적으로만 존재하며, 

분할 트리 T를 구현하는 자료 구조에 포함될 필요는 없다.


스플레잉의 회계분석

우리는 스플레이를 수행할 때 일정 수의 사이버 달러를 지불한다

(정확한 지불 금액은 분석이 끝날 때 결정된다). 

우리는 세 가지 경우를 구별한다:

•  if (지불 금액 == 스플레잉 작업) 모든 비용을 분할 비용으로 사용한다.
• if (지불 금액 > 스플레잉 작업) 초과 금액을 여러 노드의 계좌에 입금한다.
• if (지불 금액 < 스플레잉 작업) 부족분을 충당하기 위해 여러 노드의 계좌에서 출금한다.

이 섹션의 나머지 부분에서는 

작업당 O(logn) 사이버 달러를 지불하면 시스템 작동을 유지할 수 있으며, 
즉 각 노드가 부정적이지 않은 계정 잔액을 유지할 수 있음을 보여준다.


스플레잉을 위한 사이버 달러 불변성

노드의 계정 간에 전송이 이루어지는 방식을 사용하여 

필요할 때 스플레이 작업 비용을 지불하기 위해 

인출할 수 있는 충분한 사이버 달러가 항상 존재하도록 한다.

회계 방법을 사용하여 플레이 분석을 수행하기 위해 다음과 같은 불변성을 유지한다:

T의 각 노드 v는 해당 계정에 r(v)개의 사이버 달러를 가지고 있다.

불변량은 "재정적으로 건전하다"는 점에 주목하자. 

왜냐하면 0개의 키를 나무에 기부하기 위해 예비 예금을 할 필요가 없기 때문이다.

r(T): T의 모든 노드들의 순위들의 합

스플레잉 후 불변량을 보존하기 위해서, 

스플레잉 작업에 r(T)의 총 변화를 더한 값을 지불해야 한다. 

스플레잉 하위 단계(substep): 스플레잉에서의 단일 지그, 지그지그 또는 지그재그 연산

 

r'(v): 스플레잉 하위 단계 전의 T의 노드 v의 순위

r(v): 스플레잉 하위 단계 후의 T의 마디 v의 순위

 

다음 명제는 단일 스플레잉 하위 단계에 의해 야기되는 r(T)의 변화에 상한을 제공한다. 

루트에 대한 노트의 전체 스플레잉을 분석할 때 이 보조정리를 반복적으로 사용할 것이다.

명제 10.3: 

δ: T에 있는 노드 x에 대한 단일 스플레잉 하위 단계

(지그, 지그지그 또는 지그재그)에 의해 발생하는 r(T)의 변화

다음이 성립한다:
• 하위 단계가 지그지그이거나 지그재그인 경우 δ ≤ 3(r ′(x)−r(x))−2).

• 하위 단계가 지그인 경우  δ ≤ 3(r'(x) - r(x)).

정당화 : a > 0, b > 0, c > a + b이면 (안 A.1, 부록 A 참조) 다음 사실을 사용한다,
loga+logb ≤ 2logc−2. (10.6)

각 유형의 분할 하위 단계에 의한 r(T)의 변화를 고려해 보겠다.

지그지그:

(그림 10.12를 참조)

각 노드의 크기는 두 자식의 크기보다 하나 더 크므로 

지그지그 연산에서 x, y, z의 순위만 변경된다.

(y: x의 부모, z: y의 부모) 또한,


n(x)+n ′(z) ≤ n ′(x)임을 주목하라. 

따라서, 10.6에 의해, r(x)+r ′(z) ≤ 2r ′(x)−2, 

즉, r ′(z) ≤ 2r ′(x)−r(x)−2.

이 부등식과 10.7은 다음을 의미한다
δ ≤ r ′(x)+(2r ′(x)−r(x)−2)−2r(x) ≤ 3(r'(x)-r(x))-2.

지그재그: 

(그림 10.13을 참조) 

이번에도 크기와 순위의 정의에 따라 x, y, z의 순위만 변경되며, 

(y: x의 부모, z: y의 부모)

또한 r'(x) = r(z) 및 r(x) ≤ r(y)이다. 따라서
δ = r ′(x) + r ′(y) + r ′(z)−r(x)−r(y)−r(z) ≤ r ′(y) + r ′(z)−r(x)−r(y)
    ≤ r ′(y) + r ′(z)−2r(x). (10.8)

n ′(y) + n ′(z) ≤ n ′(x)임을 주목하라; 

따라서,10.6에 의해, r ′(y)+r ′(z) ≤ 2r ′(x) −2. 

그러므로, δ ≤ 2r ′(x)−2−2r(x) ≤ 3(r'(x)-r(x))-2.

지그: (그림 10.14를 참조) 

이 경우 x와 y의 순위만 변경되며, y는 x의 상위를 나타낸다. 

또한 r'(y) ≤ r(y) 및 r'(x) ≥는 r(x)이다. 따라서 
δ = r ′(y)+r ′(x)−r(y)−r(x) ≤ r'(x)-r(x) ≤ 3(r'(x)-r(x)).

명제 10.4:

T: 루트 t를 갖는 스플레이 트리

δ: 깊이 d에서 노드 x를 스플레이함으로써 발생하는 r(T)의 총 변화
Δ ≤ 3(r(t) − r(x)) − d+2.

정당성: 스플레잉 노드 x는 p = d/2 스플레잉 하위 단계로 구성되며, 

d가 홀수인 경우 마지막 것을 제외하고, 각각은 지그지그 또는 지그재그이다. 

r0(x) = r(x)를 x의 초기 랭크

i = 1, ..., p일 때

ri(x): i번째 하위 단계 다음에 오는 x의 순위

δi: i번째 하위 단계에 의한 r(T)의 변화

보조정리 10.3에 의해, 

x의 스플레잉에 의한 r(T)의 총 변화 δ은 다음과 같다

   = 3(rp(x) − r0(x))− 2p + 2
   ≤ 3(r(t)-r(x))-d+2.

제안 10.4에 의해, 

노드 x의 스플레잉을 위해 3(r(t) - r(x))+ 2 사이버 달러를 지불하면, 

T의 각 노드 v에 r(v) 사이버 달러를 유지하고 

전체 스플레잉 작업에 지불할 수 있는 충분한 사이버 달러가 있으며, 이 비용은 d달러이다. 

루트 t의 크기가 2n + 1이므로 순위 r(t) = log(2n + 1)이다. 

또한, r(x) < r(t)가 있다. 

따라서, 스플레잉에 대한 지불은 O(logn) 사이버 달러이다.

분석을 완료하려면 노드가 삽입되거나 삭제될 때 불변성을 유지하기 위한 비용을 계산해야 한다.

n개의 키를 가진 스플레이 트리에 새로운 노드 v를 삽입하면 

v의 모든 조상의 순위가 증가한다. 

즉, v0, vi, ..., vd를 v의 조상이라고 하자.

v0 = v, vi: vi-1의 부모, vd: 루트 

i = 1,...,d에 대하여 

n'(vi): 삽입 전의 vi의 크기

n(vi): 삽입 후의 vi의 크기

r'(vi): 삽입 전의 vi의 순위

r(vi): 삽입 후의 vi의 순위

우리는 다음과 같은 것을 가지고 있다
n ′(vi) = n(vi) + 1.

또한 n(vi)+1 ≤ n(vi+1)이므로, 

i = 0,1,..., d-1에 대하여, 

이 범위에 속하는 각각의 i에 대하여 다음과 같은 것이 있다:
r ′(vi) = log(n ′(vi)) = log(n(vi) + 1) ≤ log(n(vi+1)) = r(vi+1). 

따라서 삽입으로 인한 r(T)의 총 변화량은


= r'(vd)-r(v0) ≤ log(2n+1).
따라서 O(logn) 사이버 달러의 지불은 새로운 노드가 삽입될 때 불변성을 유지하기에 충분하다.

n개의 키를 가진 스플레이 트리에서 노드 v를 삭제하면 

v의 모든 조상의 순위가 감소한다. 

따라서 삭제로 인한 r(T)의 총 변동은 음수이며 

노드가 삭제되었을 때 불변성을 유지하기 위해 지불할 필요가 없다. 

따라서 분할 분석을 다음 명제

(때로는 스플레이 트리에 대한 "균형 명제"라고도 함)로 요약할 수 있다:

명제 10.5: 0개의 키를 가진 스플레이 트리부터 시작하여 

스플레이 트리에 대한 일련의 m개의 연산들을 생각해보자. 

n^i: i번째 연산 후 트리에 있는 키의 수,

n: 총 삽입의 수

연산을 수행하기 위한 총 실행 시간은 다음과 같다

= O(m logn)이다.

즉, 분할 트리에서 탐색, 삽입 또는 삭제를 수행하는 분할 실행 시간은 O(logn)이다.

n: 당시 분할 트리의 크기이다. 

따라서 스플레이 트리는 정렬된 딕셔너리 ADT를 구현하기 위한

로그 시간 분할 상환 성능을 달성할 수 있다. 

이 분할 상환 성능은 AVL 트리, (2,4) 트리 및 레드블랙 트리의 최악의 성능과 일치하지만 

각 노드에 저장된 추가 균형 정보가 필요 없는 단순 이진 트리를 사용하여 수행된다. 

또한 스플레이 트리에는 이러한 다른 균형 탐색 트리가 공유하지 않는 여러 가지 흥미로운 속성이 있다. 

다음 제안에서 이러한 추가 속성 중 하나

(때로는 분할 트리에 대한 "정적 최적성" 제안이라고 함)를 탐색한다:

명제 10.6: 0개의 키를 가진 스플레이 트리 T부터 시작하여 

스플레이 트리에 대한 일련의 m개의 연산들을 생각해보자. 

f(i): 스플레이 트리에서 엔트리 i가 엑세스한 횟수, 즉 빈도

n: 총 엔트리 수

각 항목이 적어도 한 번 액세스되었다고 가정할 때, 

연산 순서를 수행하기 위한 총 실행 시간은 다음과 같다

주목할 만한 것은 이 명제가 어떤 엔트리 i에 접근하는 분할 상환 실행 시간은 

O(log(m/f(i))라고 기술한다는 것이다.

'프로그래밍 공부 > Data Structure' 카테고리의 다른 글

11장 정렬, 집합, 선택(1)  (1) 2024.01.05
10장 탐색 트리(2)  (1) 2024.01.05
9장 맵과 딕셔너리(2)  (1) 2024.01.01
9장 맵과 딕셔너리(1)  (1) 2023.12.31
8장 우선순위 큐  (4) 2023.12.31

관련글

티스토리툴바