Lee Jeongan

Development & Study Blog

🔎 AVL 트리

AVL트리란, 트리 T의 모든 모든 내부노드 v에 대해 차이가 1을 넘지 않는 이진탐색트라를 말한다. 즉, 높이균형속성을 지니고 있다.

  • 모든 노드에 자신의 높이(균형)에 대한 정보가 저장된다.
  • AVL트리의 부트리 조차 AVL트리의 속성을 지닌다.

따라서 트리가 편향되지 않게 만들어지기 때문에 높이가 o(log n)이 보장된다. 따라서 findElement()또한 o(log n)이 보장된다.

  • 삽입이나 삭제작업은 BST(이진탐색트리)의 작업과 유사하다.

하지만 갱신 작업은 균형을 맞춰야 하기 때문에 다르다.

삽입

위에서 말했듯이 삽입 자체의 기능은 이진탐색트리와 똑같다. 하지만 각 노드가 가지고 있는 높이 정보를 업데이트해줘야함

  • 높이 정보를 업데이트하고 본다면 AVL트리가 균형을 잃을 수 있다. 따라서 개조과정 즉, 리빌딩 과정이 들어가야 한다.
Alg insertItem(k, e) // key그리고 원소값을 집어넣는 알고리즘
  input AVL tree T, key k, element e
  output none

1. w <- treeSearch(root(), k); //이진탐색을 통해 위치를 찾음
2. if(isInteranl(w)) //내부노드라면 종료
    return
  else 
    set node w to (k,e) //노드로 만들어주고
    expandExternal(w) // 외부노드 연결
    searchAndFixAfterinsertion(w) //리빌딩 실행
    return

Alg searchAndFixAfterinsertion(n)
  input internal node w
  output none

1. w노드에서 루트를 향해 올라가며 처음 만나는 불균형 노드(자식간의 높이 차이가 2이상)를 z라고한다. 만약 z가 없다면 종료
2. z의 높은 자식을 y라고 한다.(높이값이 높은 자식) 작업 수행 후 y는 w의 조상이 되는 것을 생각해야함
3. y의 높은 자식을 x라고 한다. 작업 수행 후 z와 w가 동일할 수 있으며 x는 z의 손자임을 생각해야함 y의 높이는 그의 형제 높이보다 2가 많다.
4. restructure(x,y,z) 수행 후, 이제 b를 루트로 하는 부트리의 모든 노드는 균형을 유지한다. x,y,z에 대한 높이균형속성은 지역적, 전역적으로 복구된다.  
5. return

개조(restructure / rotation)

3노드개조라고 불리기도 하며 단일회전(대칭 2개), 이중회전(대칭 2개) 총 4개지의 경우의 수를 제공한다.

  • 3대 직계 노드 x,y,z (y는 x의 부모, z는 y의 부모) 중위순회 순서 a,b,c를 순서로 회전축으로 하여 수행

단일 회전

  • 만약 b = y라면 y축을 중심으로 회전 z을 회전

이중 회전

  • 만약 b = x라면 x를 중심으로 y를 회전 후 다시 x를 중심으로 z를 회전
Alg restructure(x,y,z)
 input a node x of a binary
    search tree T that has both a 
    parent y and a grandparent z
 output tree T after restructuring
    involving nodes x, y and z

1. x,y,z의 중위순회 방문 순서의 나열을 (a,b,c)라고 하자
2. x,y,z의 부트리 가운데 x,y,z를 루트로 하는 부트리를 제외한 4개의 부트리들의 중위순회 방문순서를 나열(T0,T1,T2,T3)이라고 한다면
3. z를 루트로 하는 부트리 b를 루트로 하는 부트리로 대체 
4. T0와 T1을 각각a의 왼쪽 및 오른쪽 부트리로 만든다.
5. T2와 T3를 각각c의 왼쪽 및 오른쪽 부트리로 만든다. 
6. a와 c를 각각 b의 왼쪽 오른쪽 자식으로 만든다.
7. return b

삭제

동일하게 이진탐색트리와 똑같은 알고리즘으로 삭제가 이루어진다. 하지만 높이에 대한 업데이트와 삽입과 반대로 개조는 반대편에서 이루어진다.

Alg removeElement(k)
  input AVL tree T, key k
  output element with key k

1. w <- treeSearch(root(), k)
2. if (isExternal(w))
    return NoSuchKey

3. e <- element(w)
4. z <- leftChild(w)
5. if (!isExternal(z))
  z <- rightChild(w)
6. if (isExternal(z))     {case 1}
  zs <- reduceExternal(z) //zs는 반대편으로 넘어가기 위해
 else        {case 2}
  y <- inOrderSucc(w)
  z <- leftChild(y)
  Set node w to (key(y), element(y))
  zs <- reduceExternal(z)
7. searchAndFixAfterRemoval(parent(zs))
8. return e


Alg searchAndFixAfterRemoval(w)
 input internal node w
 output none

1. w에서 T의 루트로 향해  올라가다가 처음 만나는 불균형 노드를 z라 하자 (그러한 z가 없다면 exit).
2. z의 높은 자식을 y라 하자. {수행 후, y는 w의 조상이 아닌 z의 자식이 되는 것에 유의}
3. 다음과 같이 하여 y의 자식 중 하나를 x라 하자. y의 두 자식 중 어느 한쪽이 높으면 높은 자식을 x라 하고, 두 자식의 높이가  같으면 둘 중 y와 같은 쪽의 자식을 x로 선택.

🔎 해시테이블

지금까지 다룬 알고리즘에선 key의 값을 그대로 이용했지만 key값을 변형하여 구하는 방식을 해시라고한다.

해시테이블이란, 키-주소 매핑에 의해 구현된 사전 ADT를 말한다.

  • 해시테이블 = 버켓배열 + 해시함수

항목들의 키를 주소(즉, 첨자배열)로 매핑함으로서 1차원 배열에 사전항목들을 저장

  • 성능 탐색,삭제,삽입의 경우 o(n)의 최악시간을 가지지만, 기대시간은 o(1)의 상수값을 가진다.

버켓배열

해시테이블을 위한 버켓배열은 크기가 M인 베열 A이다.

  • A의 각 셀을 버켓(키와 원소를 담는 그릇)으로 본다.

M은 배열의 욜량을 정의하며 키 k를 가진 원소 e는 A[k]에 삽입된다.
또한, 전체의 배열은 키가 일치하지 않아 값이 들어오지 않는 것을 고려하여 Nosuchkey로 초기화한다.

분석

그렇다면 키가 유일한 정수이며 [0, M-1]범위에 잘 분포되어 있다고 가정할 때 삽입, 삭제, 검색의 기능은 O(1)의 최악의 시간을 소요 (key로 바로 접근하면 되기 때문)

  • 하지만 M이 n에 비해 공간이 매우 크다면 공간적 측면에서는 매우 큰 낭비, 범위내에 유일한 정수여야 하지만 이는 비현실적

따라서 위의 문제점들을 좋은 방식으로 매핑하는 방법이 필요하다.

  • 바로 그 방법을 해시함수! 라고한다.

해시테이블 = 버켓배열 + 해시함수

해시함수

h: 주어진 형의 키를 고정범위[0,M-1]로 매핑 ex. h(x) = x%M

  • 정수 h(x)는 키 x의 해시값

따라서 해시테이블은 두가지로 구성된다.

  • 해시 함수 h
  • 크기가 M인 테이블(배열)

간단한 예로 전호번호의 뒷자리를 키로 잡아 10000의 배열에 저장하는 예시가 있다.

해시함수는 일반적으로 두함수의 복합체로 이루어 진다.

  • h(k) = h2(h1(k))

  • h1은 해시코드맵으로 들어온 key값을 연산을 위해 맞는 자료형으로 변환한다.(int)
  • h2는 압축맵으로 변환된 값으로 연산을 통해 [0~m-1]에 올바르게 매핑시켜야 한다.

좋은 해시함수가 되기위한 조건은 키들을 무작위하게 분산시켜야 하고, 계산이 빠르고 간결해야 한다.

해시코드 맵

  • 메모리 주소

키 개체의 메모리 주소를 정수로 재해석 일반적인 방법이나 수치 또는 문자열키에 적용곤란

  • 정수 캐스트

키의 비트값을 정수로 재해석 정수형에 할당된 비트수를 초과하지 않는 길이에 적당

  • 요소 합

키의 비트들을 고정길이의 요소들로 분활한 후 각 요소를 합한다. 하지만 문자의 순서에 의미가 있는 문자열은 키에는 부적합

  • 다항 누적

우의 요소 합에서 고정값을 사용하여 더하기 전에 나눠진 키값들에게 하나씩 전부 곱한 뒤 더해서 중복을 줄인다.

압축맵

  • 나누기
h2(k) = k % M

해시테이블의 크기 M은 일반적으로 소수를 채택함

  • 승합제
h2(k) = ak + b % M

a와 b는 음이 아닌 정수로 a % M != 0해야 한다 왜냐하면 a가 0일 경우 모든 정수가 동일한 값 b로 매핑됨

🔎 스플레이 트리

트리의 노드가 접근된 이후에 스플레이되는 이진탐색트리

  • 노트 x를 스플레이 -> 연속적인 재구성을 통해 노드 x를 루트로 이동시킴
  • 가장 깊은 내부노드를 스플레이

일종의 자기조정 이진탐색트리로 볼 수 있다.

  • AVL트리에 비해 단순
  • 삽입,삭제,탐색이 O(log n) 상각실행시간
  • 자기조정성을 가진다.

탐색 삽입 삭제

  • 탐색 시에는 키가 어떠한 내부노드에서 발견된다면 내부노드를 스플레이하고 실패한다면 실패한 외부노드의 부모노드를 스플레이

  • 삽입 시에는 새로삽입한 내부노드를 스플레이

  • 삭제 시에는 실제로 삭제된 내부노드의 부모노드를 스플레이

Alg splay(x)
  input internal node x
  output none

1. if(isRoot(x))
  return
2. if(isRoot(parent(x)))
  if(x = leftchild(root()))
    rightRotate(x, root())
  else
    leftRotate(x, root())
  return
3. p <- parent(x)
4. g <- parent(p)
5. if(x = leftchild(leftchild(g)))
  rightRotate(p,g)
  rightRotate(x,p)
elseif(x = rightchild(rightchild(g)))
  leftRotate(p,g)
  leftRotate(x,p)
elseif(x = leftchild(rightchild(g)))
  rightRotate(x,p)
  leftRotate(x,g)
else
  leftRotate(x,p)
  rightRotate(x,g);
splay(x);
  • 이 과정들은 AVL트리와 매우 유사하며 이 알고리즘으로 AVL트리 구현이 가능하다..!

따라서 스플레이 트리의 핵심은 접근빈도에 따라 트리의 형태가 저절로 변하게 된다.

이진탐색트리 중복키 공부하기!!

댓글남기기

참고