2-1. 비선형 문제, 순환 종속성, 트리

서론

이전까지는 다양한 유형의 선형 자료 구조를 구현하여 데이터를 저장하고 관리하는 방법에 대해 알아봤다. 

선형 구조에서는 최대 두 가지 방향(순방향과 역방향)으로 자료를 순회할 수 있다. 

그러나 이러한 구조는 매우 제한적이어서 복잡한 문제에는 적용하기 어렵다. 

그러므로 이전 장에서 배웠던 자료 구조를 확장하여 비선형 데이터를 표현할 수 있는 복잡한 자료 구조를 만들어볼 것이다. 

 

비선형 문제

선형 자료 구조로 표현할 수 없는 대표적인 문제로는 계층적 문제(hierarchical problem)와 순환 종속성(cyclic dependency) 문제가 있다. 

 

계층적 문제

위 그림은 어떤 회사의 조직도이다. 

이러한 조직 구성은 계층적으로 표현되며, 이는 배열, 벡터, 연결 리스트 같은 자료 구조로는 표현하기 어렵다. 

위 형태의 데이터가 주어지면 다양한 유형의 연산을 수행할 수 있어야 한다. 예를 들면, 마케팅 부장은 어떤 팀장들을 관리하는지 알아낼 수 있어야 한다. 

이러한 문제를 풀기 위해서는 트리(tree)라고 부르는 자료 구조를 이용해야 한다. 

데이터가 저장된 부분들을 노드(node)라고 부르고, 노드와 노드 사이를 잇는 선을 에지(edge, 간선)라고 한다. 

 

 

순환 종속성

비선형 구조를 사용하는 것이 더 좋은 시나리오를 하나 더 보자. 

다음은 몇몇 사람들의 친구 관계를 나타낸 그림이다. 

위와 같은 구조를 그래프(graph)라고 한다. 

이 그래프에서는 사람 이름(원소)이 노드에 해당하고, 사람들 사이의 관계는 에지로 표현한다. 

이러한 구조는 SNS에서 사람들과의 친구 관계를 나타내는 용도로 자주 사용된다.

위 그림에서 앨리스는 찰리의 친구이고, 찰리는 에드워드의 친구이고, 에드워드는 그레이스의 친구임을 알 수 있다.  

또 다른 그래프 구조 예로는 도시와 도시를 잇는 도로망을 들 수 있다. 

 

 

트리: 상하 반전된 형태

트리는 노드와 노드 사이를 연결하는 에지를 이용하여 계층을 구성한다. 

트리의 계층 구조를 화면에 도식적으로 나타내려면 말 그댈 나무 형태로 나타낼 수 잇으며, 이때 에지는 나뭇가지처럼 표현된다. 

트리의 중심이 되는 노드를 루트 노드(root node)라고 부르고, 이 노드는 보통 가장 맨 위에 나타낸다. 

즉, 트리 구조를 그림으로 나타낼 때는 실제 나무와는 반대로 뿌리가 맨 위에 나타나는 상하 반전된 형태로 표현한다. 

 

//이진트리 구현
#include <iostream>
#include <queue>

struct node
{
	std::string position;   //조직도상의 직책(position)
    node* first;
    node* second;
};

//프로그램 코드에서 node 구조체를 직접 조작 X
//org_tree라는 이름의 구조를 새로 정의
struct org_tree
{
	node* root;
    
    //루트노드를 생성하는 함수. 새로운 트리를 만드는 정적 함수(static function)이다
    static org_tree create_org_structure(const std:: string& pos)
    {
    	org_tree tree;
        tree.root = new node {pos, NULL, NULL};
        return tree;
    }
    
    //특정 직책 이름에 해당하는 노드를 찾아서 반환하는 함수
    static node* find(node* root, const std::string& value)
    {
    	if(root == NULL)
        	return NULL;
        if(root->position == value)
        	return root;
        
        auto firstFound = org_tree::find(root->first, value);
        
        if(firstFound != NULL)
         	return firstFound;
            
        return org_tree::find(root->second, value);
    }
    
    //새로운 원소(부하 직원)를 추가하는 삽입 함수. find() 함수 활ㅇ용
    bool addSubordinate(const std::string& manager, const std::string& subordinate)
    {
    	auto managerNode = org_tree::find(root, manager);
        
        //managerNode가 존재하지 않음
        if(!managerNode)
        	return false;
        
        //managerNode의 자식노드가 꽉차있음
        if(managerNode->first && managerNode->second)
        	return false;
            
        if(!managerNode->first)
        	managerNode->first = new node {subordinate, NULL, NULL};
        else
        	managerNode->second = new node {subordinate, NULL, NULL};
        return true;
    }
    };
    
    int main()
    {
    	auto tree = org_tree::create_org_structure("CEO")'
        tree.addSubordinate("CEO", "부사장");
        ....
    }

 

 

트리 순회

트리가 구성되어 있다면, 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 있다. 

다양한 순회 방법에 대해 알아보자

 

1. 전위 순회(preorder traversal) 

이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문한다. 

여기서 '전위(pre)'는 상위 노드를 하위 노드보다 먼저 방문한다는 뜻이다. 

 

위 트리를 전위 순회 방식으로 탐색하면 다음과 같다. 

CEO, 부사장, IT부장, 보안팀장, 앱개발팀장, 마케팅부장, 물류팀장, 홍보팀장

 

전위 순회는 다음과 같이 구현할 수 있다. 

static void preOrder(node* start)
{
    if(!start)
        return;

    std::cout << start->position << ",";
    preOrder(start->first);
    preOrder(start->second);
}

 

2. 중위 순회(in-order traversal)

중위 순회 방법은 왼쪽 노드를 먼저 방문하고, 그다음에는 현재노드, 마지막으로 오른쪽 노드를 방문한다. 

위 트리를 중위 순회로 방문하면 다음과 같다. 

보안팀장, IT부장, 앱개발팀장, 부사장, 물류팀장, 마케팅부장, 홍보팀장, CEO

중위 순회는 다음과 같이 구현할 수 있다.

static void inOrder(node* start)
{
    if(!start)
        return;
        
    inOrder(start->first);
    std::cout << start->position << ", ";
    inOrder(start->second);
}

 

3. 후위 순회(post-order traversal)

후위 순회 방법은 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문한다.

위 트리를 후위 순회로 방문하면 다음과 같다. 

보안팀장, 앱개발팀장, IT부장, 물류팀장, 홍보팀장, 마케팅부장, 부사장, CEO

후위 순회는 다음과 같이 구현할 수 있다.

static void postOrder(node* start)
{
	if(!start)
    	return;
    
    postOrder(start->first);
    postOrder(start->second);
    std::cout << start->position << ", "
}

4. 레벨 순서 순회(level order traversal)

레벨 순서 순회 방법은 트리의 맨 위 레벨부터 아래 레발까지, 왼쪽 노드에서 오른쪽 노드 순서로 방문한다.

즉, 트리의 루트 노드부터 단계별로 차례대로 나열하는 것과 같다. 

위 그림의 트리를 레벨 순서 순회로 방문하면 다음과 같다. 

 

CEO,

부사장,

IT부장, 마케팅부장,

보안팀장, 앱개발팀장, 물류팀장, 홍보팀장

레벨 순서 순회를 구현해보자. 다른 트리 순회 방법과는 달리 레벨 순서 순회는 현재 노드에 직접 연결되지 않는 노드로 이동한다. 

이러한 경우 재귀를 사용하지 않고 구현하는 것이 더 쉽다. 

 

static void levelOrder(node* start)
{
	if(!start)
    	return;
        
    std::queue<node*> q;
    q.push(start);
    
    while(!q.empty())
    {
    	int size = q.size();
        for(int i=0; i<size; i++)
        {
        	auto current = q.front();
            q.pop();
            
            std::cout << current->position<< ", ";
            if(current->first)
            	q.push(current->first);
            if(current->second)
            	q.push(current->second);
        }
        
       std::cout << std::endl;
   }
}

위 소스 코드는 먼저 루트 노드를 방문하고, 그 다음에 자식 노드를 방문한다. 

자식 노드를 방문할 때 해당 노드의 자식 노드를 모두 큐에 추가한다. 

그래서 현재 레벨의 모든 노드 방문이 끝나면 큐에 저장된 노드를 꺼내어 방문한다. 

즉, 현재 레벨의 노드를 방문할 때 다음 레벨 노드를 미리 큐에 추가하는 방식이다. 

이러한 작업을 큐가 완전히 빌 때까지 반복하면 레벨 순서 순회가 완료된다. 

 

//메인함수 호출
org_tree::levelOrder(tree.root);

 

 

다양한 트리 구조

지금까지 주로 이진 트리에 대해 알아봤다. 

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리이며, 가장 널리 사용되는 트리 중 하나이다. 

그러나 평범한 이진 트리의 효용성은 그리 높지 않다. 

이번에는 이진 검색 트리라고 부르는 특별한 형태의 이진 트리에 대해 알아보자. 

 

이진 검색 트리

이진 검색 트리(BST, Binary Search Tree)는 널리 사용되는 형태의 이진 트리이다. 

BST는 다음과 같은 속성이 있다

• 부모 노드의 값 >= 왼쪽 자식 노드의 값
• 부모 노드의 값 <= 오른쪽 자식 노드의 값

즉, (왼쪽 노드 <= 부모 노드 <= 오른쪽 노드)의 관계를 가진다. 

 

이러한 관계식은 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 된다. 

따라서 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어든다. 

 

BST가 마지막 레벨을 제외한 모든 노드에 두 개의 자식 노드가 있을 경우, 이 트리의 높이는 log2N이 된다. 여기서 N은 원소의 개수를 나타낸다. 

이로 인해 BST의 검색 및 삽입 동작은 O(log N)의 시간 복잡도를 갖는다. 

이러한 형태의 이진 트리를 완전 이진 트리(complete binary tree)라고 한다. 

 

 

BST에서 원소 삭제하기

BST에서의 원소 검색과 삽입은 간단하므로 따로 정리하지 않는다. 

BST에서 원소를 삭제하는 작업은 단순히 노드를 삭제하는 것으로 끝나는 것이 아니라, 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 다른 적절한 노드로 삭제된 노드를 대체해야 하기 때문에 삽입보다 좀 더 복잡하다. 

 

첫 번째 단계는 삭제할 노드를 찾는 것이다. 그 후에는 다음과 같은 세 가지 경우를 따져봐야 한다. 

• 자식 노드가 없는 경우 : 단순히 해당 노드를 삭제하면 된다
• 자식 노드가 하나만 있는 경우 : 노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정한다
• 자식 노드가 두 개 있는 경우 : 노드 삭제 후, 현재 노드를 후속 노드(successor)로 대체한다. 

여기서 후속 노드란 현재 노드 다음으로 큰 숫자를 가진 노드를 말한다. 

즉, 현재 원소보다 큰 원소들 중에서 가장 작은 원소를 의미한다. 

따라서 현재 노드의 오른쪽 서브 트리로 이동한 후, 여기서 가장 작은 값의 노드를 찾으면 된다. 가장 작은 노드를 찾으려면 서브 트리에서 가장 왼쪽에 위치한 노드로 이동하면 된다. 

 

위 트리에서 루트노드 10을 삭제하려고 한다. 

10의 오른쪽 서브트리는 루트가 13인 트리이고, 여기서 시작해서 왼쪽 자식 노드로 이동하면 12가 나온다. 

즉, 10의 후속 노드는 12가 된다. 

 

10을 12로 교체하려면, 먼저 10을 지우고 후속노드의 값 12로 덮어쓴다. 

그런 다음, 원래 12가 있던 후속 노드를 삭제한다. 

위 그림에서는 후속노드 12가 오른쪽 자식이 없으므로, 그냥 삭제해주면 된다. 

만약 오른쪽 자식 노드를 가진다면, 12 위치에 오른쪽 자식 노드를 옮겨주면 된다. 

후속 노드는 왼쪽 자식 노드를 가질 수 없다. 오직 오른쪽 자식 노드 하나만 가질 수 있다. 만약 왼쪽 자식이 있었다면, 후속 노드는 12가 아닌 왼쪽 자식노드였을 것이다. 

 

 

트리 연산의 시간 복잡도

트리 연산의 시간 복잡도에 대해 알아보자. 

검색의 경우 이론적으로 매번 검색 범위가 절반으로 줄어든다고 할 수 있다. 

그러므로 N개의 노드를 가지고 있는 BST에서 검색에 필요한 시간은 T(N) = T(N/2) + 1 수식으로 표현할 수 있다. 

이 수식을 시간 복잡도로 표현하면 T(N) = O(log N)이다. 

 

그러나 여기에 함정이 있다. 삽입 함수를 잘 분석해보면 트리의 모양이 원소 삽입 순서에 따라 결정된다는 점을 알 수 있다. 그리고 검색 범위가 앞서 사용한 수식처럼 T(N/2) 형태로 줄어드는 것도 항상 성립하지는 않는다. 

그러므로 시간 복잡도가 O(log N)이라는 것도 항상 정확하다고 볼 수 없다. 

이후 균형 트리 부분에서 이 문제와 해결책에 대해 좀 더 살펴보고, 더불어 시간 복잡도를 좀 더 정확하게 계산하는 방법도 알아보자. 

 

 

BST 구현하기

BST를 구성하고, 원소 검색을 위한 find() 함수를 만들어보자. 또, 원소 삽입과 삭제 기능도 만들어보자.

#include <iostream>
using namespace std;

struct node
{
	int data;
    node* left;
    node* right;
};

struct bst
{
	node* root = nullptr;
    
    node* find(int value)
    {
    	return find_impl(root, value);
    }
    
    //원소 검색은 재귀적으로 동작하기 때문에 실제 구현은 findImpl() 함수에 따로 작성했고, 
    //private으로 지정하여 외부에서 직접 호출할 수 없도록 설정
    private:
    	node* find_impl(node* current, int value)
        {
        	if(!current)
            	return NULL;
            
            if(current->data == value)
            	return current;
            
            if(value < current->data)
            	return find_impl(current->left, value);
            
            return find_impl(current->right, value);
        }
        
    public:
    	void insert(int value)
        {
        	if(!root)
            	root = new node {value, NULL, NULL};
            else
            	insert_impl(root, value);
        }
    private:
    	void insert_impl(node* current, int value)
        {
        	if(value < current->data{
            	{
                	if(!current->left)
                    	current->left = new node {value, NULL, NULL}
                    else
                    	insert_impl(current->left, value);
                }
            else
            	{
                	if(!current->right)
                    	current->right = new node {value, NULL, NULL}
                    else
                    	insert_impl(current->right, value);
                }
        }
    
    public:
    	void inorder()
        {
        	inorder_impl(root);
        }
        
    private:
    	void inorder_impe(node* start}
        {
        	if(!start)
            	return;
            inorder_impl(start->left);
            cout << start->data << " ";
            inorder_impl(start->right);
        }
        
    public:
    	node* successor(node* start)
        {
        	auto current = start->right;
            while(current && current->left)
            	current = current -> left;
            return current;
        }
        
        void deleteValue(int value)
        {
        	root = delete_impl(root, value);
        }
    
    private:
    	node* delete_impl(node* start, int value)
        {
        	if(!start)
            	return NULL;
            if(value < start->data)
            	start->left = delete_impl(start->left, value);
            else if(value > start->data_
            	start->right = delete_impe(start->right, value);
            else
            {
            	if(!start->left)  //자식 노드가 전혀 없거나, 왼쪽 자식 노드만 없는 경우
                {
                 	auto tmp = start->right;
                    delete start;
                    return temp;
                }
                if(!start->right)  //오른쪽 자식 노드만 없는 경우
                {
                	auto tmp = start->left;
                    delete start;
                    return tmp;
                }
                
                //자식 노드가 둘 다 있는 경우
                auto succNode = successor(start);
                start->date = succNode->date;
                
                //오른쪽 서브 트리에서 후속(successor)을 찾아 삭제
                start->right = delete_impl(start->right, succNode->date);
                }
                
                return start;
            }
        };

 

원소 삭제 구현 함수(delete_impl)에 대해 설명해보자.

특정 노드를 삭제하면, 해당 노드의 부모 노드 포인터를 조정해야 한다. 

그래서 삭제 구현 함수는 부모 노드 포인터가 새로 가리켜야 할 노드의 주소를 반환하도록 설정했다. 

 

BST의 중위 순회는 왼쪽 서브 트리를 먼저 방문하고, 그다음에 현재 노드, 다음에 오른쪽 서브 트리를 방문한다. 

그러므로 BST의 속성에 따라 현재 노드보다 작은 값을 먼저 방문하고, 그 다음에 현재 노드, 현재 노드보다 큰 값을 방문하게 된다. 

이러한 과정이 재귀적으로 반복되기 때문에 결국 모든 데이터가 오름차순으로 정렬되어 나타나게 된다.

 

 

균형 트리

오른쪽 트리는 전체 트리가 왼쪽으로 편향되어 있는 것을 확인할 수 있다. 

이 상태의 트리에서 find() 함수를 사용하여 bst.find(10) 코드를 실행하면, 비교 횟수가 원소 갯수가 거의 같아진다. 

 

왼쪽 트리는 편향되지 않은 상태이며, 이러한 트리를 균형이 잡혔다고 한다. 

find() 함수 실행시에도 O(logN) 시간을 가진다. 

즉, find() 함수의 시간 복잡도는 단순히 원소 개수에만 영향을 받는 것이 아니라 트리의 형태에 대해서도 영향을 받는다. 

 

검색 단계를 살펴보면, 항상 트리의 아래쪽으로 한 단계씩 나아가는 것을 알 수 있다. 

그리고 결국에는 더이상 자식 노드가 없는 리프 노드(leaf node)에서 끝나게 된다. 

여기서 찾고자 하는 원소를 발견하면 해당 노드를 반환하고, 없으면 NULL을 반환한다. 

따라서 검색에 필요한 단계의 수는 BST의 최대 레벨 수보다는 작다. BST의 레벨수를 BST의 높이(height)라고 부르기 때문에 원소 검색의 실제 시간 복잡도는 O(높이)로 표현할 수 있다. 

 

결국 원소 검색의 시간 복잡도를 최적화하려면 트리의 높이가 최적화되어야 한다. 

이러한 작업을 트리의 균형 잡기라고 한다. 

트리의 균형을 잡기 위해서는 원소 삽입 또는 삭제 후에 트리 구성을 조정해야 한다. 

이렇게 조정되어 편향성이 줄어든 이진 검색 트리를 높이-균형 BST(height-balanced BST)라고 한다. 

 

트리의 균형을 잡는 방법은 여러 가지가 있으며, 이를 통해 AVL트리, 레드-블랙 트리 같은 다양한 트리를 만들 수 있다. 

AVL 트리의 기본 아이디어는 BST 속성을 유지하면서 트리 높이의 균형을 잡기 위해 약간의 회전을 수행하는 것이다. 

 

자세한 내용은 따로 정리할 예정이다. 

 

 

N-항 트리

지금까지는 주로 이진 트리에 대해 살펴봤다. 

이번에 살펴볼 N-항 트리는 각 노드가 N개의 자식을 가질 수 있다. N은 임의의 양수이므로 N개의 자식 노드는 벡터를 이용하여 저장할 수 있다. 그러므로 N-항 트리는 다음과 같이 구현할 수 있다. 

 

struct nTree
{
	int data;	
    std::vector<nTree*> children;
};

위 코드에서 각각의 노드는 임의 개수의 자식을 거느릴 수 있다. 

N-항 트리를 사용하는 대표적인 예는 다음과 같다

• 컴퓨터 파일 시스템 구조
• 컴파일러