검색트리(SearchTree)

treeInsert

Contents

이진 검색 트리(BST)에서 주어진 입력에 대하여 다음과 같이 treeInsert 함수로 원소를 재귀적으로 삽입 할 때 treeInsert 함수가 호출 되는 횟수를 출력하라. 

treeInsert(r, x){

   if(t = NIL)

      ket[r] = x; left[r] = NIL; right[r] = NIL;

      return r;

   if(x < ket[t]) 

      left[t] = treeInsert(left[t], x); 

      return t

   else

      right[t] = treeInsert(right[t], x);

      return t;

    

}

Input

첫 줄에는 BST에 삽입해야 하는 원소의 개수 n(1<=n<=100)이 들어 온다. 

그 다음 줄에는 n개의 임의의 양의 정수가 들어 온다. 

Output

모든 원소를 삽입할 때 treeInsert 함수가 호출 되는 총 횟수를 출력한다.

Sample Input

8

10 5 3 2 8 6 13 15

Sample Output

22

=================================================================

treeDelete

 

Contents

주어진 입력으로 이진 탐색 트리(BST)를 형성하고, 주어진 원소 x를 삭제 한 후, BST를 조건에 맞는 순회를 하고 그 결과를 출력하라.

※ 삭제할 원소 x가 왼쪽 자식과 오른쪽 자식을 모두 가지고 있다면, 오른쪽 서브트리에서 가장 작은 노드를 선택한다.

 

Input

첫 줄에는 BST에 삽입될 원소의 개수 n(1<=n<=100)가 들어 온다. 

다음 줄에는 n개의 임의의 양의 정수가 들어온다. 순차적으로 BST에 삽입 한다. 

그 다음 줄에는 삭제할 원소의 개수 k(<=n)가 들어 온다.

다음 k 줄에는 p와 삭제할 원소 x가 한 줄씩 들어온다. 삭제할 원소는 BST에 있다고 가정한다.

p는 순회할 연산의 종류에 해당 한다.

p가 0인 경우 전위 순회, 1인 경우 중위 순회, 2인 경우 후위 순회이다.

 

Output

BST에서 한 원소를 삭제 하고 난 뒤, BST를 조건에 맞게 순회하면서 각 원소를 한 줄에 출력한다. 

각 원소는 빈칸으로 구별 한다.

 

Sample Input

8

10 5 3 2 8 6 13 15

3

0 13

1 5

2 3

Sample Output

10 5 3 2 8 6 15

2 3 6 8 10 15

2 8 6 15 10

=================================================================

BinarySearchTree

Contents

소년 빌게이츠는 조별 과제로 BinarySearchTree 클래스를 구현해야 했다. 조원인 스티븐 잡스와 성공적인 코딩을 위해서 인터페이스에 대한 약속을 하고 main 함수를 작성 하였다. 약속한 클래스 인터페이스는 다음과 같다. 

<cNode.h>

template <typename T>

class cBinarySearchTree;

 

template <typename T>

class cNode{

friend class cBinarySearchTree<T>;

public:

    cNode();

    cNode(T t){key = t; left = right = 0;}

private:

    cNode<T>* left;

    cNode<T>* right;

    T key;

};

<cBinarySearchTree.h>

#include "cNode.h"

#include <iostream>

using namespace std;

 

template <typename T>

class cBinarySearchTree{

friend class cNode<T>;

public:

    cBinarySearchTree();

    ~cBinarySearchTree();

    void treeInsert(T x);

    void treeDelete(T x);

    void treePrint();

private:

    cNode<T>* treeInsert(cNode<T>* t, T x);

    void treeDelete(cNode<T>* t, cNode<T>* r, cNode<T>* p);   

    cNode<T>* deleteNode(cNode<T>* r);

    void treePrint(cNode<T>* t, int step);

    cNode<T>* root;

};

cBinarySearchTree에서 각 연산은 다음과 같다. 각 연산의 알고리즘은 교재에 나온 알고리즘과 같다.

treeInsert(T x) : x를 tree에 삽입 한다. treeInsert(t, x)를 다음과 같이 호출

        template <typename T>

void cBinarySearchTree<t>::treeInsert(T x){

    root = treeInsert(root, x);

}

treeDelete(T x) : x를 tree에서 삭제 한다. treeDelete(t, r, p)를 다음 방식으로 호출

        template <typename T>

void cBinarySearchTree<T>::treeDelete(T x){

    cNode<T>* r = root;

    cNode<T>* p = 0;

 

    // r의 부모를 찾아 p에 저장

 

    if(r)       treeDelete(root, r, p);

}

        

treePrint() : 다음과 같은 방식으로 트리의 모든 원소를 출력한다

한 줄에 하나의 노드만을 출력한다. 이때, 노드의 출력은 노드 값의 출력을 의미한다.

자식 노드는 부모 노드보다 공백 4개 만큼 들여서 출력한다.

DFS 방식으로 순회한다.

여러분이 할일은 cBinarySearchTree를 구현하여 main 소스가 제대로 동작하게 해야 하는 것이다. 

업로드 해야 하는 파일 : cNode.h, cBinarySearchTree.h

Input

첫 줄에는 작업 명령에 대한 라인수 n이 들어온다. 

다음 n 줄에는 다음 작업 명령이 들어 온다. 

I x : x 를 BST에 삽입한다.

D x : x를 BST에서 삭제한다.

Output

작업 명령이 끝난 후에 트리를 조건에 맞게 출력한다.

Sample Input

10

I 10

I 5

D 10

I 3

I 2

D 5

I 6

I 13

D 6

I 15

Sample Output

 

3

    2

    13

        15

main source code

#include "cBinarySearchTree.h"

#include <iostream>

using namespace std;

 

int main(){

    char cmd;

    int n, x;

    cBinarySearchTree<int> tree;

    cin>>n;

    for(int i = 0; i<n; i++){

        cin>>cmd>>x;

        switch(cmd){

        case 'I':

            tree.treeInsert(x);

            break;

        case 'D':

            tree.treeDelete(x);

            break;

        }

    }

    tree.treePrint();

    return 0;

}

=================================================================

RedBlackTree

Contents

이번에는 레드 블랙 트리(RBT)를 구현해야 한다. 다음은 레드 블랙 트리를 구현하기 위한 인터페이스 양식이다. 

<cNode.h>

//자유롭게 수정 되어도 된다.

const int RED = 0;

const int BLACK = 1;

class cRedBlackTree;

class cNode{

friend class cRedBlackTree;

public:

    cNode();

    cNode(int t){key = t; left = right = 0; color = RED;}

private:

    cNode* left;

    cNode* right;

    int key;

    int color;

};

<cRedBlackTree.h>

#include "cNode.h"

#include <iostream>

using namespace std;

class cRedBlackTree{

public:

    //이부분의 양식은 반드시 지켜져야한다.

    cRedBlackTree();

    ~cRedBlackTree();

    void treeInsert(int d);

    void treeDelete(int d);

    void treePrint();

private:

    cNode* root;

    cNode* nil;

 

        //public에 있는 멤버 함수를 위해 자유롭게 구현한다. 

};

</iostream>

treeInsert(int d) : x를 트리에 삽입한다. 레드 블랙 트리 조건을 위배해선 안된다.

treeDelete(int d) : 트리에서 x를 삭제 한다. 삭제 후에도 트리는 레드 블랙 트리 조건을 충족해야한다.

treePrint() : 다음과 같은 방식으로 트리의 모든 원소를 출력한다. (전위 탐색)

한 줄에 하나의 노드만을 출력한다. 이때 노드의 색상을 출력하고 빈칸 하나를 들인 다음에 노드의 값을 출력한다. 색상은 빨간색이면 RED, 검정색이면 BLACK으로 출력한다. ex) RED 1

자식 노드는 부모 노드보다 공백 4개 만큼 들여서 출력한다.

<cRedBlackTree.cpp>

#include "cRedBlackTree.h"

//cRedBlackTree를 구현한다.

업로드 해야 하는 파일 : cNode.h, cRedBlackTree.h, cRedBlackTree.cpp

Input

첫 줄에는 작업 명령에 대한 라인수 n이 들어온다. 

다음 n 줄에는 다음 작업 명령이 들어 온다. 

I x : x 를 RBT에 삽입한다.

D x : x를 RBT에서 삭제한다.

Output

작업 명령이 끝난 후에 트리를 조건에 맞게 출력한다.

Sample Input

10

I 10

I 9

D 10

I 8

I 7

I 6

D 7

I 5

I 4

D 4

Sample Output

BLACK 8

    BLACK 5

        RED 6

    BLACK 9

<main source code>

#include "cRedBlackTree.h"

#include <iostream>

using namespace std;

int main(){

    char cmd;

    int n, x;

    cRedBlackTree rbt;

    cin>>n;

    for(int i = 0; i<n; i++){

        cin>>cmd>>x;

        switch(cmd){

        case 'I':

            rbt.treeInsert(x);

            break;

        case 'D':

            rbt.treeDelete(x);

            break;  

        }

    }

    rbt.treePrint();

    return 0;

}