jws rbtree 분석(작성중..)

Python 의 RBTree에 대해 파악하다 http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx 를 알게되었습니다.

유용한 내용이 많아 찬찬히 업데이트 합니다.

1. Left, Right 대신 0, 1

left, right 표현 대신 0, 1을 쓰는 저자의 코드도 흥미롭네요.

/* Classic binary search tree insertion */
struct cbt_node *cbt_insert(struct cbt_node *root, int data)
{
    if (root == NULL)
    {
        root = make_node(data);
    }
    else if (data < root->data)
    {
        root->left = cbt_insert(root->left, data);
    }
    else
    {
        root->right = cbt_insert(root->right, data);
    }

    return root;
}

/* Julienne Walker's binary search tree insertion */
struct jsw_node *jsw_insert(struct jsw_node *root, int data)
{
    if (root == NULL)
    {
        root = make_node(data);
    }
    else
    {
        int dir = root->data < data;

        root->link[dir] = jsw_insert(root->link[dir], data);
    }

    return root;
}

가독성을 조금 희생시킨 것 같지만 라인수를 많이 줄여줍니다. 내용을 이해한다면 사실 가독성이 많이 떨어진다고 하기도 애매하네요 ㅎㅎ

python에서도 무리 없이 써먹을 수 있을 것 같습니다.

가령

>>> (1>0) == (True)
True
>>> (1<0) == (False)
True
>>> (1>0) == (1)
True
>>> (1>0) == (0)
False
>>> (1<0) == (0)
True
>>> (1<0) == (1)
False

좋네요