Skip List

Skip list

= 정렬된 linked list에 대해 적용하는 알고리즘으로 빠른 검색 및 삽입 삭제를 가능하게 해줌 !

- dictionary ADT를 위함

- 평균적으로 O(log n)의 복잡도 가짐 (검색시간)

- Randomized Data structure 임 ! = 랜덤성을 기초로 알고리즘을 구현하는 것. 

 

Perfect skip list

-> 레벨이 정해져있음 -> 현재 레벨 원소개수의 절반을 다음 레벨에 추가!

-> 레벨 1에서 하나더 올리는ㅇ ㅐ들은 레벨 1애들의 절반! 2의배수인애들올림(2번째노드마다 레벨1추가)

-> 레벨2에서 하나더 올리는애들은 레벨2의 절반! 4의배수인 애들올림 (4번째 노드마다 레벨 1추가) !!이러캐!

현

2번째 노드 -> 레벨 1에 (한칸 올라감) (2n. ->2,6, 10 .. )

4번째 노드 -> 레벨 2에

8번째 노드 -> 레벨 3에

16번째 노드 -> 레벨 4에

...

- search -> O(log n)

 

Randomized skip list

- perfect는 insert(delete) 힘들다 !! complete restructuring이 필요하므로 !

-> level을 랜덤하게 배정 !

low level에 두고 coin던졌을 때 앞면이면 레벨을 하나 높인다; 이거반복한다 (뒷면 나올때 stay ~) 

동전을 여러번 던져서 윗면 나온 횟수 셈 (뒷면나오기전까지겟지)

(만약에 skip list 길이보다 커지면 skip list 높이를 i+1로 올려주면 됨)

-> 레벨 1에 잇는 노드 기댓값은 n/2 (맨아래에서 위로 올라올 확률 x1/2이니까). 레벨 2는 n/4

 

Search

최상단 list의 첫번째 위치에서 시작.

** 작거나 같은 노드 찾긔 ** *!!

현재 위치의 다음 element가 찾으려는거보다 크다 -> 해당 노드에서 아래 레벨로 내려감

작다 -> 해당 노드로 이동

(쭉가기 가능)

이걸 반복 !

( 크다 -> stay, 내려감 / 작다 -> 이동, 내려감 ) x 반복 ~~

 

Implementation

struct skip_node {
    element_type element; //담을 값
    init level; //층
    struct skip_node **forward; //
} *p; // 애초에 포인터로 선언하네

p=(skip_node*)malloc(sizeof(struct skip_node)); // p에 노드할당함 -> 주소반환 ~ 그거저장
p->forward = (skip_node**)malloc(sizeof(skip_node*)*(k+1)); //?

다음 노드가 이중포인터인 이유? // ??

노드의 자료형을 포인터로할꺼임

근데 가리키는 노드를 바꿔줘야하니까 포인터의 포인터가 된다

저거 아님~

 

실습코드 외우기

* headnode는 데이터 가지는 노드가 아니라 각 레벨의 첫노드들을 가리키는 포인터인듯

// 데이터 찾는 함수
void search (node* headNode, int data){
    int pos=maxlevel-1; //젤위레벨 ! 근데 0부터니까 -1해줌
    //노드 찾아갈 임시 노드를 만들어서 함!
    node* temp=headNode->next[pos]; // 이게 첫 노드
    
    //현재 레벨에 속한 노드가 없거나 해당 노드의 data값이 더 크다 -> 레벨 하나 내려감 -> 이거 다하면 앞에는 더 작은 값들만 남게됨
    while(temp==NULL || temp->data>data)
        temp=temp->next[--pos]; //바로 레벨 하나 내려야하므로 --를 앞에 붙임
    
    while(temp->data!=data){ // 같으면 바로 나옴.
        // 
        if
        
        
        꺼져

// insert 함수
/*
1. temp노드를 생성하여 넣을 직전 노드를 찾는다
2. coin flip을 통해 추가할 노드의 level을 지정한다
3. temp와 생성한 새 노드를 연결한다~
*/

void insert(node** headNode, int data){
    // 직전노드 찾기
    
    //추가할 노드의 최대 레벨 계산
    while(rand()%2){ //랜덤 넘버 만든게 2나눳을때 나머지가 1일때를 성공으로 본다 (coin filp성공)
        level++;
        if(level>=MAX_LEVEL){ // 최대 레벨 되면 망해요
            break;
        }
    }
    //추가할 노드 동적할당 및 초기화
    node* newNode=(node*)malloc
    node->level=level;
    node->data=data;
    //일단 null로 next연결
    for(int i=0; i<MAX_LEVEL;i++)
        node->next=NULL;
    //직전 노드와 잘 연결^^
    for (int i=new->level-1; i>=0; i--){ //근데왜 level-1일까..? 해당 레벨 위로는 연결필요없어서 ok 이지만 왜 -1..??
        new->next[i]=temp[i]->next[i];
        temp[i]->next[i]=new; // temp는 왜또 [i]로 되어잇는가 ?!?!?!?!
    }
}

 

---

Equivalence Classes

= 연관이 있는 원소들을 한 집합으로 묶은 것 -> 그래프에서 연결된 노드들을 군집화할 때 사용

-> linked list로 구현

 

* 같다 ( ≡ )  = equivalece ! 이려면

1. x = x : reflexive

2. x = y , y = x : symmetric (대칭)

3. x=y, y=z, (이면) x=z : transitive 

이어야 한다 !

- 그래프로 연결됨 -> 동치이다 ! equivalent 하다 ≡ 

 

구현

각 노드와 linked list로 연결됨 -> 동치라고 판단 

0≡3 이면 0에도 3이 연결되어 있어야 하고 3에도 0이 연결되어 있어야 함

 

그래프에서 연결된 노드를 한번씩 방문하면 동치인 모든 원소를 알 수 있음 !

-> 노드에 방문하면 그거랑 연결된 노드들을 방문할 노드에 기록해놓음

-> 이미 방문 예정 목록에 잇거나 이미 방문 했으면 추가 안함

-> 그리고 예정 목록 맨 첨부터 하나씩 방문하면 됨 순서대로

 

코드이해

int out[] 배열은 인덱스(0~n)에 해당하는 노드들을 검색 했는지 안했는지 true/false 를 담아둔다

nodePointer seq[] 배열은 인덱스에 해당하는 노드가 가리키는 동치인 노드들을 순차적으로 담아둔다

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 24
#define FALSE 0
#define TRUE 1

typedef struct node* nodePointer;
typedef struct node{
    int data;
    nodePointer link;
};

int main(int argc, const char * argv[]) {
    int out[MAX_SIZE]; // 1로 초기화. 나머지는 0이겟지요
    nodePointer seq[MAX_SIZE]; // null로 초기화
    nodePointer x,y,top;
    int i, j, n;
    
    printf("Enter the size (<= %d)", MAX_SIZE); // 사이즈는 헤드 포함인듯 ! 5이면 pair 4개 받음
    scanf("%d", &n);
    for (i=0; i<n;i++){
        out[i]=TRUE;
        seq[i]=NULL;
    }
    printf("Enter a pair of numbers (-1 -1 to quit): ");
    scanf("%d%d", &i, &j);
    while(i>=0){ // 입력 계속 받겠다는 뜻!
        x=(nodePointer)malloc(sizeof(struct node));
        x->data=j;
        x->link=seq[i];
        seq[i]=x;
        
        x=(nodePointer)malloc(sizeof(struct node));
        x->data=i;
        x->link=seq[j];
        seq[j]=x; // 순서 그대로 !! 중요 ~~
        
        printf("Enter a pair of numbers (-1 -1 to quit): ");
        scanf("%d%d", &i, &j);
    }
    
    for(i=0;i<n;i++){
        if(out[i]){
            printf("\nNew Class: %5d", i);
            //out은 해당 노드 차례차례가면서 해당 노드 검색햇으면 False로저장하고 아직 안햇음 true로 저장해두는 편의용 배열
            out[i]=FALSE;
            x=seq[i];
            top=NULL;
            for(;;){
                while(x) //x가 존재할 때까지
                {
                    j=x->data;
                    
                    if(out[j]){ //검색 되지 않앗다면 검색시행. 위치저장합니당
                        printf("%5d", j);
                        out[j]=FALSE;
                        y=x->link;
                        x->link=top;
                        top=x;
                        x=y;
                    }
                    else
                        x=x->link;
                }
                if( !top )
                    break;
                x=seq[top->data];
                top=top->link;
            }
        }
    }
    printf("\n");
}

 

~ 알고리즘 핵심 포인트 ~

1. 데이터 받는 부분

x에 malloc하고

x->data=j 로 데이터를 받는다

x->link=seq[i] 하면 해당 인덱스 값에 대해 이어져있는 다음 노드(링크)가 이 노드에 이어짐

seq[i]=x 해서 해당 인덱스 값에 이 노드 이어줌 !!

중요 ~~~

 

2. equivalence class 알아내는 부분

if(out[i]) 하면서 i클래스에 대한 검색 시작

seq[i]에 대해 밑으로 내려가면서 원소들 출력

- 이때, seq[i]밑에 저장되어있는 원소들중에서 out[]배열 값이 true인 원소들의 seq리스트도 검색해줘야함

-> seq[i]탐색이 끝난 후 해당 seq[j]로 이동하여 탐색할 것임 -> 담아놔야함 -> 링크드리스트형태의 stack 이용!

 

for(int i=0; i<n; i++){ //=모든 원소에 대해서 할 것이다

       if(!out[i]) contiue; 스킵! //!!중요!! 해당 원소가 탐색되지 않았다면 !! 해야함 (다른클래스에 속해잇어서 이미 탐색되엇을가능성 농후)

        printf("New calss : %d", i);

        out[i]=False; //false처리 필수 !!

        x=seq[i]; top=NULL; //x은 seq의 첫 노드 ^^ , top은 앞으로 다른 seq에도 가야대니까 그거 저장해둘 스택느낌

        for(;;){

            while(x){ // x노드가 존재할 때까지

                j=x->data; 

                if(out[j]){ // 만약 그 노드가 아직 탐색(출력)되지 않았다면 -> 일단 출력하고 해당 값을 스택에 저장해둬야함!

                                    (머 seq[j]없으면 알아서 저장안하고 걍 출력만 하고 끝나겟지요)

                    printf("j ^^");

                    //스택에 x를 넣을꺼임 !!

                    y=x->link; 

 

                    x->link=top; //걍 대충이어준다고생각

 

                    top=x; // 이게 핵심 !! 저장해둠

                    x=y; //seq[i]를 x로 만듦. 담에 탐색하려공~

 

                }else  

                        x=x->link; //해당 노드 이미 검색됐으면 어쩔수없싱 ㅠㅠ 다음 노드 검색함^^

          } // while문 끝 ! while문에서는 해당 노드 다 검색과 스택에 넣기를 한다

          if(!top)

                break; // 현재 클래스 다 검색했다 ; 해당 노드 검색도 햇고 스택에 들어잇는 검색해야할 노드도 없어서 이제 끝낫다 ~

          x=seq[top->data]; // 스택에 잇으면 스택 젤위에잇는 노드에 대해 위 반복while문 다시 돈다~ 똑같이 검색

          top=top->link; // 그리고 다음 노드로 이동!

}}

 

 

http://contents.kocw.or.kr/KOCW/document/2015/yeungnam/jeongbonggyo/12.pdf