[WIL] Day12 (기말준비 Day3)

<알고리즘>

 

Binary search tree:

하나의 노드에는 key포인터, left, right, parent을 가지고 있다. 

Binary search tree는 같은 키들을 가지고 있어도 그 형태가 다양할 수가 있다. 

 

In order walk으로 정렬을 진행가능함. 

If x != NIL then

  Inorder-Walk(left[X])

  Print key[x]

  Inorder-Walk(right[x])

In order walk의 시간복잡도는 O(n). 하나씩 찾아가야해서. 

 

search의 수도코드

Seach(k):

If x!= NIL then 

   If key[x] = k then return x

   If k < key[x] then return Search(left[x])

   If k > key[x] then return Seach(right[x])

   Else return NIL

 

successor라는건 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드. 

predecessor라는건 해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드. 

 

Search’이라는 함수를 변형해서 만들수가 있다. 언제 쓰이냐면 키값을 찾는데 키값이 정확히 뭔지 모를때 k의 근사값을 입력으로 사용을 해서 서치하고 가까운 값을 찾는것. 이값이 successor와 predecessor. 

 

Nearest neghbor를 찾을 때는 successor와 predecessor를 찾으면 됨. (k는 트리에 없다고 가정을 할때)

 

INSERT 수도 코드:

INSERT(z):

  Y <- NIL

  X <- root

  While x != NUL do

    Y <- x

    If key[z] < key[x]

    Then x <- left[x]

    Else x <- right[x]

  p[z] <- y

  If key[z] < key[y]

  Then left[y] <- z

  Else right[y] <- z

 

삭제를 할때는 먼저 삭제할 노드를 탐색. 자녀가 둘인 노드를 삭제를 할때에는 삭제될 노드의 오른쪽 서브트리에서 제일 값이 작은 노드가 삭제될 노드를 대체한다. 

수업때는 제일 값이 작은 노드를 해당 키값의 successor라고 표현(굿) 

삭제할때의 케이스3개:

case1: z의 child가 존재하지 않을때

Case2: z의 child가 하나 존재할때.

Case3: z의 child가 두개일때. 

케이스1,2는 쉽고 케이스3은 어려움….

(전체 수도코드 시험전에 한번 다시 보기)

 

레드블랙트리는 BST에 color필드가 필요함. 

삽입할때 O(log n) 걸린다, 그리고 항상 O(log n) hegith를 가지고 있다. 

height가 O(log n)인 이유는 블랙트리만 보았을 때 height가 logn을 가지고 있고 레드는 최대로 해도 2logn이여서 O(log n)이다. 

 

레드블랙트리 5가지 특징:

1. 모든 노드는 red 혹은 black이다. 
2. 루트 노드는 black이다.
3. 모든 nill 노드는 black이다.
4. red의 자녀들은 black이다. 
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black수는 같다.

 

 

hegith가 최대 2log(n+1)인것을 증명하는게 좀 어렵다. 총 3가지 특징을 알아야한다.

1. 높이가 h인 노드의 bh는 bh>=h/2이다. 이게 특징4번때문에 레드 노드가 전체 트리의 많아봤자 절반이여서 그렇다. 이게 바로 intuition하게 와닿지가 않으면 그냥 한번 직접 그려보면 아 대충 이렇구나 하고 넘어갈수 있을 정도임.
2. 두번째 특징은 노드 x를 root로 하는 임의의 서브트리는 적어도 2^bh(x) -1이다. 이 식은 어디서 나왔는지 모르겠지만 어차피 레드 블랙트리는 일정한 형태를 가진 그래프니까 이런식이겠구나 해서 누군가가 식으로 만든 형태이겠지? 어쨌든 수업때는 수학적 귀납법으로 해당 식을 증명하였다. 이때 bh(x)값이 노드가 red일때와 black일때를 구분해야 한다.
3. 마지막으로는 n개의 내부 노드를 갖는 red-black tree의 높이는 2log(n+1)이하이다. 

       해당 특징의 증명은 특징 1,2를 적용해서 알수가 있다. 한 트리의 총 노드 갯수를 n이라고 가정을 하면 n는 2^bh(n)-1보다 크거나 같고 특징1에 따라서 bh값이 치환가능하고, 이를 통해서 2log(n+1)로 유도가능하다.

참고: https://blogshine.tistory.com/102

 

RB deletion을 할때에 지워야하는 노드가 검은색일때 특징 5개중, 1,3을 제외하고 2,4,5를 위반하게 됨.