괴짜 프로그래머의 일상사~@@

레드 블랙 트리 :: 2007/02/22 14:58

알고리즘 수업 레포트로 작성했던 레드 블랙 트리 자료입니다.
레드 블랙 트리가 별다를건 없지만 한 가지 특징이 있다면 주석이 참 친절하게 잘 달려 있습니다.
아마도 제가 이제껏 작업한 소스 중에 주석 젤 멋지게 단게 아니었나 하는 생각을 해봅니다. 궁금하신가요? ㅋㅋㅋ

주석 보기...

// n, n부모, n부모부모 노드로 리스트럭쳐링을 수행한다.
// 리스트럭쳐링 완료 후의 중간 노드를 반환한다.
template <class T>
CRBNode<T> *CRBTree<T>::_trirest(RBNode *n)
{
    RBNode    *l, *r;
    RBNode    *pn, *ppn;
    RBNode    *pppn;
    RBNode    *mid;

ASSERT(n != NULL);
    ASSERT(n->parent() != NULL);
    ASSERT(n->parent()->parent() != NULL);

pn = n->parent();
    ppn = pn->parent();
    pppn = ppn->parent();

// 다음과 같은 두 단계에 걸쳐서 트라이노드 리스트럭쳐링을 한다.
    // 
    // 1. 세 노드의 링크 기준을 판별하여, 적절하게 
    // 2. 세 노드중 부모노드가 된 mid의 부모를 연결한다.

// 1단계:
    // 트라이 노드 리스트럭쳐링에는 총 네가지 경우가 있다.

if(ppn->left() == pn)
    {

if(pn->left() == n)
        {
            // 1번 경우
            //     pp
            //    /
            //   p
            //  /
            // c
            ppn->left(pn->right());
            pn->right(ppn);
            mid = pn;
        }
        else
        {
            // 2번 경우
            //     pp
            //    /
            //   p
            //    \
            //     c

l = n->left();
            r = n->right();

n->left(pn);
            n->right(ppn);
            pn->right(l);
            ppn->left(r);
            mid = n;
        }
    }
    else
    {
        if(pn->left() == n)
        {
            // 3번 경우
            // pp
            //  \
            //   p
            //  /
            // c

l = n->left();
            r = n->right();

n->left(ppn);
            n->right(pn);
            ppn->right(l);
            pn->left(r);
            mid = n;
        }
        else
        {
            // 4번 경우
            // pp
            //  \
            //   p
            //    \
            //     c

ppn->right(pn->left());
            pn->left(ppn);
            mid = pn;
        }
    }

// 2단계:
    // 이 단계에서는 mid를 기준으로 아래와 같은 형태로
    // 리스트럭쳐링이 완료되었다.
    //
    //       mid
    //      /   \
    //    left   right
    //
    // 남은 작업은 pp의 부모노드의 링크를 mid로 연결 시켜주는 것이다.

if(pppn)
    {
        // ppp로 부모가 넘어온 경우
        // ppp의 자식 링크로 mid를 가리키도록 설정한다.
        if(pppn->right() == ppn)
            pppn->right(mid);
        else
            pppn->left(mid);
    }
    else
    {
        // ppp가 없는 경우 pp가 루트 였으므로
        // mid를 루트로 변경해 준다.
        _set_root(mid);
    }

return mid;
}

위의 화면은 인터랙티브 모드를 캡쳐한 것이고, 아래는 문서와 실행 파일과 소스입니다. 레드 블랙 트리가 궁금하거나 배우고 싶은 분들은 고고씽. ㅋㅋ 근데 사실 이런거 실제 밥벌어 먹는데서는 한 번도 써 본 적이 없네요. ㅠㅠ온니 학교용인것 같습니다. 학교에서는 트리를 어찌나 많이 만들던지 ㅋ

레드 블랙 트리 아이디어는 정말 참신합니다. ㅋ
만든 사람 참 똑똑할 것 같다는 ㅎ^^

rbtree_src.zip

rbtree_exe.zip

rbtree_doc.zip

스폰서	글타래 관련 글 Cool stuff (7452) 구글... (7452) 최근 글 블로그 옮겼습니다.(22807) 노무현 전 대통령님의 서거(20698) 정보처리기사(24107) 2주간 인기 글 2주간 인기글이 없습니다.

C++, 레드 블랙 트리, 레포트, 알고리즘, 트리

20281명이 보았고, 댓글 6개가 달렸습니다!!!
트랙백 3개,

Trackback Address :: http://jiniya.net/tt/trackback/444

portable fish finder

Tracked from fish finder reviews | 2018/08/15 03:05 | DEL

괴짜 프로그래머의 일상사~@@ - 레드 블랙 트리

best fish finder

Tracked from fish finder reviews | 2018/08/15 07:49 | DEL

괴짜 프로그래머의 일상사~@@ - 레드 블랙 트리

best fish finder

Tracked from fish finder reviews | 2018/08/25 08:31 | DEL

괴짜 프로그래머의 일상사~@@ - 레드 블랙 트리

rockenrollz | 2007/02/22 18:16 | PERMALINK | EDIT/DEL | REPLY

깔끔하고 눈에 딱 들어오는 주석... ^^

rockenrollz | 2007/02/24 17:37 | PERMALINK | EDIT/DEL | REPLY

행님 저 대학원갈려구요...
취직은 2010년 7월경에 할꺼 같은데... ^^
행님이 저좀 데려가세요~ㅋ

rockenrollz | 2007/02/25 16:34 | PERMALINK | EDIT/DEL | REPLY

마음은 세탁을 하고싶은데...
그게 잘 안될꺼 같아요...
그놈에 성적이 왜그런지...^^ㅋ

Name
Password
Homepage

Secret

< PREV | 1| ... 233|234|235|236|237|238|239|240|241| ... 604| NEXT >

레드 블랙 트리 :: 2007/02/22 14:58

portable fish finder

best fish finder

best fish finder

Informed

Category

Photo Log

Tags

Recent Entries

Recent Comments

Recent Trackbacks

Calendar

Archive

Link Site

« 2018/09 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30