이진탐색트리

내부노드에 키,원소 쌍 저장하는 적정 이진트리
어떤 원소 v에 대해
key(v.left) <= key(v) <= key(v.right)

중위순회 하면 키가 증가하는 순서로 방문함.

성능

n개 항목이 있다고 하면

• 높이 h : 최악의 높이 O(n), 최선의 높이 O(logn)
• 공간사용 : O(n)
• 탐색 삽입 삭제 : O(h) ** 높이

공간은 O(n)

탐색

Alg findElement(k)
1. w ← treeSearch(root(), k)
2. if(isExternal(w))
     return NoSuchKey    # 외부노드에는 데이터 저장하지 않음
   else
     return element(w)
------------------
Alg treeSearch(v, k)
1. if(isExternal(v))
     return v
2. if(k=key(v))
     return v
   elseif(k<key(v)
     return treeSearch(v.left, k)
   else
     return treeSearch(v.right, k)

삽입

Alg insertItem(k, e)
1. w ← treeSerach(root(), k)
2. if(isInternal(w))
     return
   else
     set node w to (k, e)
     expandExternal(w)
     return

삭제

Alg removeElement(k)
1. w ← treeSearch(root(), k)
2. if(isExternal(w))
     return
3. e ← element(w)
   z ← w.left
4. if(!isExternal(z))
     z ← w.right
5. if(isExternal(z))
     reduceExternal(z)
   else
     y ← inOrderSucc(w)  # w의 오른쪽 부트리의 가장 왼쪽노드
     z ← y.left
     set node w to (key(y), element(y))
     reduceExternal(z)
6. return e 

AVL트리

모든 내부노드의 자식들의 좌우높이 차이가 1을 넘지 않는 이진탐색트리

• 높이균형 속성을 만족한다. 이 속성은 각 노드에 저장한다.

자신의 높이가 5일 때
왼쪽자식 높이 4, 오른쪽자식 높이 3 ---> 4-3 = 1이므로 AVL맞음
왼쪽자식 높이 1, 오른쪽자식 높이 4 ---> 4-1 = 3이므로 AVL아님.

삽입, 삭제를 하면 AVL트리의 높이균형이 깨질 수 있다.
이를 복구하는 것을 '개조한다'고 한다.

성능

n개 항목이 있다고 하면

• 높이 h : O(logn)
• 탐색 : O(logn)
• 개조 : O(1)
• 삽입 삭제 O(logn)

공간은 O(n)

삽입

Alg insertItemToAVL(k, e)
1. w ← treeSearch(root(), k)
2. if(isInternal(w))
     return
   else
     set node w to (k, e)
     expandExternal(w)
     searchAndFixAfterInsertion(w)
     return

---------------------------------
Alg searchAndFixAfterInsertion(w)
1. z ← w부모로 계속 올라가면서 처음 만나는 불균형노드
   y ← z의 높은 자식
   x ← y의 높은 자식. 높이가 같으면 y와 같은 쪽의 자식
2. b ← restructure(x, y, z)
3. return

삭제

Alg removeElementFromAVL(k)
1. w ← treeSearch(root(), k)
2. if(isExternal(w))
     return NoSuchKey
3. e ← element(w)
   z ← w.left
4. if(!isExternal(z))
     z ← w.right
5. if(isExternal(z))
     zs ← reduceExternal(z)
   else
     y ← inOrderSucc(w)  # w의 오른쪽 부트리의 가장 왼쪽노드
     z ← y.left
     set node w to (key(y), element(y))
     zs ← reduceExternal(z)
6. searchAndFixAfterRemoval(parent(zs))
7. return e 
--------------------------
Alg searchAndFixAfterRemoval(w)
1. z ← w부모로 계속 올라가면서 처음 만나는 불균형노드
   y ← z의 높은 자식
   x ← y의 높은 자식. 높이가 같으면 y와 같은 쪽의 자식
2. b ← restructure(x, y, z)
3. searchAndFixAfterRemoval(b.parent)

개조

Alg restructure(x, y, z)
1. x, y, z의 중위순회 방문 순서의 나열은 a, b, c
2. x, y, z밑의 4개 부트리의 중위순회 방문 순서 나열은 T0 T1 T2 T3
3. z를 루트로 하는 부트리를 b를 루트로 하는 부트리로 대체
4. a 왼쪽 부트리 T0, 오른쪽 부트리 T1
5. c 왼쪽 부트리 T2, 오른쪽 부트리 T3
6. b 왼쪽자식 a, 오른쪽자식 c
7. return b  # 새로운 가장높은 노드