13 Red-black Trees Problems - 13-1 Persistent Dynamic Sets, 13-2 Join operation on red-black trees

Problems

13-1 Persistent dynamic sets

알고리즘 수업 동안, 우리는 가끔씩, dynamic set이 업데이트 될 때, dynamic set의 이전 versions들을 유지할 필요가 있다는 것을 발견한다. 우리는 그러한 set을 persistent하다고 부른다. persistent set을 구현하는 한 방법은 그것이 수정될 때 마다, 전체 set을 복사하는 것이지만, 이 접근법은 프로그램을 느리게할 수 있고, 또한 많은 공간을 소비한다. 가끔씩, 우리는 더 잘할 수 있다.

operations INSERT, DELETE, and SEARCH를 가진 persistent set S를 고려해라. 그리고 우리는 그림 13.8(a)에서 보여지듯이 binary sear h trees를 사용하여 그것을 구현한다. 우리는 그 집합은 모든 version에 대해 별개의 root를 유지한다. key 5를 그 집합에 넣기위해, 우리는 key 5를 가진 새로운 노드를 생성한다. 이 노드는 key 7를 가진 새로운 노드의 left child가 된다. 왜나하면, 우리는 key 7를 가진 존재하는 노드를 수정할 수 없기 때문이다. 유사하게, key 7를 가진 새 노드는 key8를 가진 새로운 노드의 왼쪽 자식이 된다. key 8를 가진 노드의 오른쪽 자식은 key 10를 가진 존재하는 노드이다. key 8를 가진 새로운 노드는 이제 차례대로 key 4를 가진 새로운 root $r'$의 오른쪽 자식이 되고, 그 key 4를 가진 것의 left child는 key 3를 가진 것의 존재하는 노드이다. 우리는 따라서, 그 트리의 일 부분만을 복사하고, 원래 트리로 그 노드들의 일부를 공유한다. 그림 13.8(b)에서 보여지는 것처럼.

각 tree node가 attributes key, left, and right를 가지지만, parent가 없다고 가정하자. (Exercise 13.3-6을 보아라.)

a. 일반적인 persistent binary search tree에 대해, key k를 넣거나 node y를 제거하기 위해 우리가 바꿀 필요가 있는 노드들을 확인해라.

b. procedure PERSISTENT-TREE-INSERT procedure를 작성해라. persistent tree T와 넣을 key k가 주어진다면, T에 k를 삽입하는 결과인 새로운 persistent tree T'를 반환하는 절차이다.

c. 만약 persistent binary search tree T의 height가 h라면, PERSISTENT-TREE-INSERT의 구현에 대한 시간과 공간 요구사항은 무엇인가? (그 공간 요구사항은 할당된 새로운 노드들의 개수와 비례한다.)

d. 우리가 각 노드에 parent attribute를 포함했다고 가정하자. 이 경우에, PERSISTENT-TREE-INSERT는 추가적인 복사를 수행할 필요가 있을 것이다. PERSISTENT-TREE-INSERT가 그러고나서 $\Omega(n)$ time과 space를 요구할 것이라는 것을 증명해라. 여기에서 n은 tree에서 노드들의 개수이다.

e. worst-case running time과 space가 insertion또는 deletion마다 $O(lg \;n)$이 되도록 보장하기 위해 어떻게 red-black trees를 사용하는지를 보여라.

 

13-2 Join operation on red-black trees

join operation은 두 개의 dynamic sets $S_1$과 $S_2$, 그리고 $x_1 \in S_1$, $x_2 \in S_2$인 element $x$를 가지는데, 우리는 $x_1.key \leq x.key \leq x_2.key$를 가진다. 이것은 $S = S_1 \cup \{ x\} \cup S_2$인 한 집합을 반환한다. 이 문제에서, 우리는 red-black trees에서 그 join operation을 어떻게 구현할지를 조사하다.

a. red-black tree T가 주어진다면, 우리가 그것의 black-height를 새로운 attribute $T.bh$로 저장하자. RB-INSERT와 RB-DELETE가 tree의 노드에서 추가 storage를 요구하지 않고, asymptotic running times을 증가시키지 않고, 그 bh attribute를 유지할 수 있다는 것을 주장해라. T를 내려가면서, 우리는 방문된 노드마다 $O(1)$ time에 우리가 방문하는 각 노드의 black-height를 결정할 수 있다는 것을 보여라.

​x
// count black height of this tree when inserting
{
    x = m_root;
​
    // we don't count root color,
    // but root is always black color
    // so set it at first as -1
    int black_height = -1;  
​
    // goto a leaf node
    while (x != m_nil)
    {
        if (x->color == e_color_black)
            ++black_height;
​
        if (x->left != m_nil)
            x = x->left;
        else if (x->right != m_nil)
            x = x->right;
        else
            x = m_nil;
    }
​
    m_black_height = black_height;
}
​
// count black height of this tree when deleting
{
​
    if (m_node_count > 1)
    {
        x = m_root;
​
        // we don't count root color,
        // but root is always black color
        // so set it at first as -1
        int black_height = -1;
​
        // goto a leaf node
        while (x != m_nil)
        {
            if (x->color == e_color_black)
                ++black_height;
​
            if (x->left != m_nil)
                x = x->left;
            else if (x->right != m_nil)
                x = x->right;
            else
                x = m_nil;
        }
​
        m_black_height = black_height;
    }
    else
    {
        // m_node_count will be 0
        // so just set it as 0
        m_black_height = 0;
    }
}

우리는$RB-JOIN(T_1, X, T_2)$ 를 구현하고 싶다. 이것은 $T_1$과 $T_2$를 파괴하고, $T = T_1 \cup \{x\} \cup T_2$인 red-black tree를 반환한다. n이 $T_1$과 $T_2$에 있는 노드들의 총 개수라고 하자.

 

b. $T_1.bh \geq T_2.bh$라고 가정하자. black-height가 $T_2.bh$인 것들 중에서, $T_1$에서 가장 큰 key를 가진 black node y를 찾는 $O(lg \; n)$ time algorithm을 설명해라.

Answer : T1의 black height가 T2의 black height보다 크다면, T1의 right child로 계속 가는 것은 가장 큰 key들을 만나게 해줄 것이고, 모든 leaf로 가는 path는 같은 black height를 가지므로, T2와 같은 black height를 가진 노드를 만난다. red black tree의 height는 $O(lg\;n)$이므로, 이 알고리즘은 $O(lg\;n)$이다.

 

c. $T_y$가 y를 root로 하는 subtree라고 하자. $T_y \cup \{x\} \cup T_2$가 어떻게 $T_y$를 $O(1)$ time에 binary-search tree property를 파괴하지 않고 $T_y$를 교체할 수 있는지 설명해라.

Answer : $x$가 $T_y$의 keys보다 더 크고, $T_2$의 키보다 작다면, x를 root로 하고 왼쪽 child에는 $T_y$를 오른쪽 child에는 $T_2$를 달면 $O(1)$ time에 binary-search tree property를 파괴하지 않고 $T_y$를 교체할 수 있다.

 

d. red-black properties 1, 3, 그리고 5가 유지되기 위해서 우리는 x를 무슨 color로 만들어야 하는가? $O(lg\;n)$ time에 properties 2와 4를 어떻게 만드는지를 설명해라.

Answer : 일단 $T_1$과 $T_2$를 join하는데 있어서 위의 상황을 유지하는데 있어서, $T_1$의 모든 keys가 $x$의 keys보다 작고, $T_2$의 어떤 key가 x의 key보다 클 때,

1, 3은 그냥 유지가 되는데 5를 유지하기 위해서는 x가 red가 되어야 한다. 왜냐하면 black이였을 때 다른 것을 건드릴 수 있기 때문이다. 그리고 2, 4를 만족시키기 위해, x의 노드가 red이기 때문에, x의 parent노 red라면 RB-INSERT-FIXUP를 호출시켜서 고쳐준다. RB-INSERT-FIXUP은 $O(lg\;n)$이 걸린다.

 

e. part (b)의 가정을 하여서 어떠한 일반성도 손실되지 않는다고 주장해라. $T_1.bh \leq T_2.bh$일 때 발상하는 대칭 상황을 설명해라.

Answer :

규칙을 다시 보자면, $RB-JOIN(T_1, X, T_2)$에서 $T = T_1 \cup \{x\} \cup T_2$인 상황에서, $T_1$의 모든 key는 $x$보다 작거나 같고, $T_2$의 모든 key는 $x$보다 크거나 같다. $T_1.bh \geq T_2.bh$일 땐, $T_1$에서 $T_2.bh$의 black height를 가지면서 가장 큰 key를 찾아서 그것을 $x$로 설정하고, left child에 $T_1$의 그 노드를, right child를 $T_2$로 해서 Join Operation을 했다. $T_1.bh \leq T_2.bh$에는 어떻게 해야 할까. $T_1$의 가장 큰 keys들 중에서 찾았는데, 이번엔 $T_2$에서 가장 작은 노드들 중에서 찾는게 좋다. 어쨋든, black height가 높은 곳으로 join을 시킨다. 그리고 나서 같은 작업을 해준다.

 

f. RB-JOIN의 작동시간이 $O(lg\;n)$이라고 주장해라.

RB-INSERT-FIXUP을 호출시키기 때문에 $o(lg\;n)$이다.

 

구현

xxxxxxxxxx
static chan_rb_tree<rb_t_key, rb_t_value> join(const chan_rb_tree<rb_t_key, rb_t_value>& left, const node& x, const chan_rb_tree<rb_t_key, rb_t_value>& right)
{
    // keys of left tree are smaller than x
    // keys of right tree are greater than x
    int left_black_height = left.get_black_height();
    int right_black_height = right.get_black_height();
​
    chan_rb_tree<rb_t_key, rb_t_value> result;
    if (left_black_height > right_black_height)
    {
        // join right into left
        result = left;
​
        int black_height = -1;
        node* largest_node_with_right_black_height = result.m_root;
        while (largest_node_with_right_black_height != result.m_nil)
        {
            if (largest_node_with_right_black_height->color == e_color_black)
                ++black_height;
​
            if (black_height == right_black_height)
            {
                node* largest_node_parent = largest_node_with_right_black_height->parent;
​
                node* new_x_node = result.allocate_node(x.key, x.value, e_color_red);
                new_x_node->parent = largest_node_parent;
                new_x_node->left = largest_node_with_right_black_height;
                new_x_node->right = copy_from_other_red_black_tree_recursive(result.m_nil, new_x_node->right, right.m_root, right.m_nil);
​
                if (largest_node_parent->left == largest_node_with_right_black_height)
                {
                    largest_node_parent->left = new_x_node;
                }
                else
                {
                    largest_node_parent->right = new_x_node;
                }
​
                result.rb_insert_fixup(new_x_node);
                result.update_tree_black_height();
                result.m_node_count = left.m_node_count + 1 + right.m_node_count;
                break;
            }
            else
            {
                largest_node_with_right_black_height = largest_node_with_right_black_height->right;
            }
        }
    }
    else
    {
        //join left into right
        result = right;
​
        int black_height = -1;
        node* smallest_node_with_left_black_height = result.m_root;
        while (smallest_node_with_left_black_height != result.m_nil)
        {
            if (smallest_node_with_left_black_height->color == e_color_black)
                ++black_height;
​
            if (black_height == left_black_height)
            {
                node* smallest_node_parent = smallest_node_with_left_black_height->parent;
​
                node* new_x_node = result.allocate_node(x.key, x.value, e_color_red);
                new_x_node->parent = smallest_node_parent;
                new_x_node->left = copy_from_other_red_black_tree_recursive(result.m_nil, new_x_node->left, left.m_root, left.m_nil);
                new_x_node->right = smallest_node_with_left_black_height;
​
                if (smallest_node_parent->left == smallest_node_with_left_black_height)
                {
                    smallest_node_parent->left = new_x_node;
                }
                else
                {
                    smallest_node_parent->right = new_x_node;
                }
​
                result.rb_insert_fixup(new_x_node);
                result.update_tree_black_height();
                result.m_node_count = left.m_node_count + 1 + right.m_node_count;
​
                break;
            }
            else
            {
                smallest_node_with_left_black_height = smallest_node_with_left_black_height->left;
            }
        }
    }
​
    return result;
}