[c++] tree가 valid한 Red-Black Tree 확인하는 알고리즘

과제 중에 root node를 input으로 받아

root로부터 연결된 tree가

red black tree의 속성을 모두 준수하고있는지

확인하는 코드를 작성해야했다

 

우선 red black tree에 대한 강의내용정리는

다음 링크에 접속하면 볼 수 있다

https://think0905.tistory.com/entry/computer-science-Red-Black-Tree

[computer science] Red-Black Tree

 

자세한 설명이 보고싶다면 위 게시글을 참고하고

지금은 코드를 짜기 위해서 간단하게만 red black tree에 대해 살펴보자

 

red black tree는 기본적으로 Binary Search Tree(BST)구조이며

단순 Binary Search Tree는 unbalanced 할 때 효율적이지 못하다는

단점을 극복하기위해 만들어진 tree로

스스로 balance를 맞추는 tree이고, self balance tree라고도 불린다

 

tree는 binary search tree와 기본적으로 같지만

각 node는 red 혹은 black이라는 색을 가지고 있다

 

red black tree의 속성은 다음과 같다

 

1. binary search tree의 구조여야한다

2. root node는 무조건 black이어야 한다

3. leaf node들은 모두 무조건 black이어야 한다

4. 부모 node와 자식 node가 동시에 red일 수 없다 (연속으로 red node가 나올 수 없다)

5. root로부터 모든 leaf node로 가는 path에서 black node의 개수는 모두 같아야한다

 

과제 안내에는 다음과 같이 나와있다

 

 

이에 따라 우선 hpp파일에 node와 함수를 정의해줬다

 

struct Node {
    int key;
    bool isRed;
    Node* left;
    Node* right;
    Node* parent;
};

 

 

key는 node의 값

isRed 가 true이면 해당 node는 빨간색, false이면 검은색이다

left, right, parent는 각 node의 pointer를 갖고있다

 

 

그리고 Node*인 root를 input으로 넣으면

만약 해당 tree가 red-black tree의 속성을 모두 만족하면 true를 반환하고

그렇지 않으면 false를 반환하는 validateRedBlackTree(Node* root) 함수를 정의해줬다

 

bool validateRedBlackTree(Node* root);

 

---

 

차례차례 경우를 생각하며 코드를 작성해줬다

 

1. 우선 첫 번째로는 root가 없는 경우 tree가 없는 경우인데

이럴 때는 true를 반환해준다

(아예 없는 것도 valid로 치는 듯 했다 .. 그냥 tradition인듯?)

 

bool validateRedBlackTree(Node* root) {
    if (!root) {
        return true;
    }
}

 

따라서 우선 첫 번째 줄에 위와 같은 코드를 추가해줬다

 

2. 그 다음으로는 root가 존재하는데 그 색이 red일 경우

red-black tree의 규칙에 어긋나므로 false를 반환해야한다

 

bool validateRedBlackTree(Node* root) {
    if (!root) {
        return true;
    }

    if (root->isRed) {
        return false;
    }
}

 

따라서 root->isRed가 true일 경우 false를 반환하도록 코드를 추가했다

 

이제 stack을 사용해서 tree를 순회하며

여러 가지 red black tree들의 속성을 검사하려고한다

 

3. 그래서 우선 stack을 정의해준다

stack에 담을 자료구조는 pair형식으로 저장하는데

순회하는 node와 현재 black tree의 개수를 저장하는 int변수를 담는다

 

따라서 stack<pair<Node*, int>>의 데이터타입으로 stack을 할당해준다

 

4. stack을 할당한 다음, root node를 처음 element로 넣어주는데

pair타입이기 때문에, root를 넣어주고

root는 black node이기 때문에 black tree의 개수를 저장하는 int에는 1을 넣어준다

 

bool validateRedBlackTree(Node* root) {
    if (!root) {
        return true;
    }

    if (root->isRed) {
        return false;
    }

    stack<pair<Node*, int> > nodeStack;
    nodeStack.push({root, 1});
}

 

이제 while문을 이용해서 stack을 순회하며

깊이우선탐색으로 tree를 탐색할 것이다

 

5. 그리고 순회하면서 blackNode의 개수를 저장할 int 변수를

while문 밖에 선언하고 -1로 초기화를 한다

변수명은 나중에 node들의 black node count값과 비교해야하는 대상이되므로

expectedBlackHeight로 해준다

int expectedBlackHeight = -1;

 

참고로 우리가 구현할 red-black tree에서는

가장 마지막에 있는 nullptr를 leaf node로 간주하고

이는 모두 black node로 간주한다

이 내용은 위의 과제 instruction에 나와있다

 

따라서, stack을 돌면서 leaf node까지 갔을 때

black node count가 모두 동일한지를 검사해야하는데

이 때 현재 leaf node에 왔는지를 알려면

현재 탐색 중인 node가 nullptr인지를 검사하면 된다

 

leaf node가 아닌 이상 탐색 중인 노드가 nullptr일 수는 없기 때문이다

 

따라서 현재 노드가 nullptr(leaf node)인데

만약 expectedBlackHeight가 -1이라면

가장 첫 leaf node에 도달했다는 의미이므로

6. expectedBlackHeight를 현재 탐색 중인 leaf node의

black node count로 할당해준다

 

그러고 만약 expectedBlackHeight의 값이 -1이 아닌데

현재 leaf node의 black node count값과 expectedBlackHeight이 다르다면

이는 모든 path들의 black node count가 같아야한다는

red black tree의 속성을 지키지 못한것이다

7. 그러므로 false를 return해야한다

 

stack<pair<Node*, int> > nodeStack;
nodeStack.push({root, 1});

int expectedBlackHeight = -1;

while (!nodeStack.empty()) {
    Node* currNode = nodeStack.top().first;
    int currBlackHeight = nodeStack.top().second;
    nodeStack.pop();

    if (!currNode) {
        if (expectedBlackHeight == -1) {
            expectedBlackHeight = currBlackHeight;
        } else if (expectedBlackHeight != currBlackHeight) {
            return false;
        }
        continue;
    }
}

 

지금까지의 내용을 코드로 구현하면 위와 같다

 

 

이렇게 하면 모든 path마다 black node의 개수가 같아야 한다는

red black tree의 속성은 검사를 한 것이다

 

이제 다른 속성들을 검사해보는 로직을 구현해보도록하자

 

 

우선 parent와 child가 모두 red 일 수 없다

8. 이를 위해 parent가 red일 때 자기 자신도 red이면 false를 반환하도록 하자

if (currNode->isRed && currNode->parent && currNode->parent->isRed) {
    return false;
}

 

 

그 다음, red black tree도 기본적으로

binary search tree의 구조를 가지고 있어야한다는

조건을 검사하기 위해서

9. 현재 node의 값이 left child의 값보다 작거나

현재 node의 값이 right child의 값보다 큰 경우

false를 반환하도록 해주자

if (currNode->left && currNode->left->key > currNode->key) {
    return false;
}
if (currNode->right && currNode->right->key < currNode->key) {
    return false;
}

 

이제 마지막으로 tree를 깊이우선탐색으로 순회하기 위해서

stack에 다음 node들을 push해야한다

 

node들을 push할 때 현재까지의

black node의 개수를 계산해서 함께 push해야하는데

stack의 top에서 가져온 현재까지의 black node 개수에서

만약 현재 node가 black이라면 1을 증가시켜준 뒤

stack에 push해주면 된다

 

10. 따라서 현재 node가 black이라면

black node count를 증가시키는 코드를 작성한 뒤

깊이우선탐색으로 left, right node를

stack에 push하는 부분을 작성해주자

if (!currNode->isRed) {
    currBlackHeight++;
}

nodeStack.push({currNode->left, currBlackHeight});
nodeStack.push({currNode->right, currBlackHeight});

 

 

처음에 코드를 작성할 때

지금까지 깊이우선탐색으로 tree를 탐색하던 습관때문에

currNode에서 left가 있을 때만 push하고

currNode에서 right가 있을 때만 push하도록 해줬는데

원하는 결과가 나오지 않아서 꽤나 고민을 했었다

 

하지만 우리는 위에서 nullptr일 때

이를 leaf node로 간주하고 red black tree의 조건을

검사하는 코드를 작성했으므로

left나 right가 nullptr임에 관계없이 무조건 push를 해줘야했다

 

이렇게 하면 red-black tree의 유효성을 검사하는

함수 작성이 완료된다

 

전체 코드는 아래와 같다

#include <iostream>
#include <stack>
#include "prob1.hpp"

using namespace std;

bool validateRedBlackTree(Node* root) {
    if (!root) {
        return true;
    }

    if (root->isRed) {
        return false;
    }

    stack<pair<Node*, int> > nodeStack;
    nodeStack.push({root, 1});

    int expectedBlackHeight = -1;

    while (!nodeStack.empty()) {
        Node* currNode = nodeStack.top().first;
        int currBlackHeight = nodeStack.top().second;
        nodeStack.pop();

        if (!currNode) {
            if (expectedBlackHeight == -1) {
                expectedBlackHeight = currBlackHeight;
            } else if (expectedBlackHeight != currBlackHeight) {
                return false;
            }
            continue;
        }

        if (currNode->isRed && currNode->parent && currNode->parent->isRed) {
            return false;
        }

        if (currNode->left && currNode->left->key > currNode->key) {
            return false;
        }
        if (currNode->right && currNode->right->key < currNode->key) {
            return false;
        }

        if (!currNode->isRed) {
            currBlackHeight++;
        }

        nodeStack.push({currNode->left, currBlackHeight});
        nodeStack.push({currNode->right, currBlackHeight});

    }

    return true;
}