[자료구조] 이진 트리

단순 연결 리스트는 각 노드마다 그 노드와 다른 한 노드를 연결하는 링크를 포함한다. 트리 역시 노드 기반 자료 구조이지만 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.

 

다음은 간단한 트리를 그림으로 표현한 것이다.

예제의 각 노드에는 다른 두 노드로 이어지는 링크가 있다. 실제 링크를 모두 표시하지 않고도 간결하게 트리를 그림으로 표현할 수 있다.

트리에는 세 가지 고유한 용어가 있다.

• 가장 상위 노드("j")를 root라고 부른다. 루트는 트리의 꼭대기다.
• "j"를 "m"과 "b"의 부모라고 하고, 반대로 "j"의 자식이라고 한다.
• 트리에는 레벨이 있다. 위 트리는 세 레벨이다.

트리 기반 자료 구조는 종류가 다양하지만 우선 이진트리는 다음의 규칙을 따른다.

• 각 노드의 자식은 0개나 1개, 2개다.
• 한 노드에 자식이 둘이면 한 자식은 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야 한다.

다음은 2진 트리 예제다.

코드로 간단하게 표현하면 아래와 같다.

class CBTreeNode
{
public:
	CBTreeNode(int _value, CBTreeNode* left = nullptr, CBTreeNode* right = nullptr)
	{
		value = _value;
		lnode = left;
		rnode = right;
	}

	int value;
	CBTreeNode* lnode;
	CBTreeNode* rnode;
};

int main()
{
	CBTreeNode* node1 = new CBTreeNode(1);
	CBTreeNode* node2 = new CBTreeNode(10);
	CBTreeNode* root = new CBTreeNode(5, node1, node2);
	return 0;
}

---

검색

이진트리를 검색하는 알고리즘은 root node부터 시작한다.

1. node의 값을 확인한다.
2. 찾고 있는 값이면 좋다.
3. 찾고 있는 값이 현재 node보다 작다면 왼쪽 하위 트리를 검색한다.
4. 찾고 있는 값이 현재 node보다 크다면 오른쪽 하위 트리를 검색한다.

위 검색 규칙을 C++로 구현하면 다음과 같다.

CBTreeNode* search(int value, CBTreeNode* node)
{
	if (node == nullptr || node->value == value)
		return node;
	else if (value < node->value)
		search(value, node->lnode);
	else
		search(value, node->rnode);
}

61을 검색해보자. 이 과정을 그림으로 따라가 보면 알 수 있다. 원하는 값을 찾는 데 까지 4단계가 걸림을 알 수 있다. 

---

삽입

새 값을 이진 트리에 삽입하려면 새로운 node를 붙일 새로운 node를 찾아야 한다. 루프부터 쭉 검색해서 내려가 가장 마지막 단계의 node에 도달하게 되면 새로운 node가 삽입될 곳을 찾을 수 있다.

45를 삽입한다고 하면 40을 가지고 있는 node의 오른쪽 값으로 저장하면 된다. 예제는 삽입에 5단계를 사용하였다. 삽입은 항상 검색에 한 단계 더 추가된다. 이진트리는 검색과 삽입 모두 O(log N)이므로 데이터를 많이 변경할 애플리케이션에서 중요하다.

 

void insert(int value, CBTreeNode* node)
{
	if (value < node->value)
	{
		if (node->lnode == nullptr)
		{
			CBTreeNode* newNode = new CBTreeNode(value);
			node->lnode = newNode;
		}
		else
			insert(value, node->lnode);
	}
	else if (value > node->value)
	{
		if (node->rnode == nullptr)
		{
			CBTreeNode* newNode = new CBTreeNode(value);
			node->rnode = newNode;
		}
		else
			insert(value, node->rnode);
	}
	else
		cout << "duplicated value." << endl;
}

한 가지 유의해야 할 점은 무작위로 정렬된 데이터로 트리를 생성해야 대개 균형 잡힌 트리가 생성된다는 점이다. 정렬된  데이터를 트리에 삽입하면 불균형이 심하고 덜 효율적일 수 있다. 이러한 이유로 정렬된 배열을 이진트리로 변환하고 싶을 때는 먼저 데이터 순서를 무작위로 만드는 것이 좋다.

---

삭제

삭제는 이진트리에서 가장 어려운 연산이며 주의 깊게 실행해야 한다. 삭제 시 최하위 node를 삭제 시에는 간단히 삭제를 하면 되지만 중간 node를 삭제하게 될 경우에는 주의가 필요하다.

 

node 삭제의 규칙은 다음과 같다.

• 삭제할 노드에 자식이 없으면 그냥 삭제한다.
• 삭제할 노드에 자식이 하나면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 위치에 넣는다.

• 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다. 후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.

후속자 값을 어떻게 찾을까? 다음과 같은 알고리즘을 사용할 수 있다. 삭제된 값의 오른쪽 자식을 방문해 그 자식의 왼쪽 자식을 따라 계속해서 방문하여 더 이상 왼쪽 자식이 없을 때까지 내려간다. 그 바닥 값이 후속자 node가 된다.

마지막으로 고려해야 하는 상황은 후속자 node에 오른쪽 자식이 있을 때다. 

• 만약 후속자 노드에 오른쪽 자식이 있으면 후속자를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.

CBTreeNode* lift(CBTreeNode* node, CBTreeNode* delete_node)
{
	if (node->lnode != nullptr)
	{
		node->lnode = lift(node->lnode, delete_node);
		return node;
	}
	else
	{
		delete_node->value = node->value;
		return node->rnode;
	}
}

CBTreeNode* deleteNode(int value, CBTreeNode* node)
{
	if (node == nullptr)
		return nullptr;
	else if (value < node->value)
	{
		node->lnode = deleteNode(value, node->lnode);
		return node;
	}
	else if (value > node->value)
	{
		node->rnode = deleteNode(value, node->rnode);
		return node;
	}
	else if (value == node->value)
	{
		if (node->lnode == nullptr)
			return node->rnode;
		else if (node->rnode == nullptr)
			return node->lnode;
		else
		{
			node->rnode = lift(node->rnode, node);
			return node;
		}
	}
}

---

전체 코드

#include <vector>
#include <iostream>
using namespace std;

class CBTreeNode
{
public:
	CBTreeNode(int _value, CBTreeNode* left = nullptr, CBTreeNode* right = nullptr)
	{
		value = _value;
		lnode = left;
		rnode = right;
	}

	int value;
	CBTreeNode* lnode;
	CBTreeNode* rnode;
};

CBTreeNode* search(int value, CBTreeNode* node)
{
	if (node == nullptr || node->value == value)
		return node;
	else if (value < node->value)
		search(value, node->lnode);
	else
		search(value, node->rnode);
}

void insert(int value, CBTreeNode* node)
{
	if (value < node->value)
	{
		if (node->lnode == nullptr)
		{
			CBTreeNode* newNode = new CBTreeNode(value);
			node->lnode = newNode;
		}
		else
			insert(value, node->lnode);
	}
	else if (value > node->value)
	{
		if (node->rnode == nullptr)
		{
			CBTreeNode* newNode = new CBTreeNode(value);
			node->rnode = newNode;
		}
		else
			insert(value, node->rnode);
	}
	else
		cout << "duplicated value." << endl;
}

CBTreeNode* lift(CBTreeNode* node, CBTreeNode* delete_node)
{
	if (node->lnode != nullptr)
	{
		node->lnode = lift(node->lnode, delete_node);
		return node;
	}
	else
	{
		delete_node->value = node->value;
		return node->rnode;
	}
}

CBTreeNode* deleteNode(int value, CBTreeNode* node)
{
	if (node == nullptr)
		return nullptr;
	else if (value < node->value)
	{
		node->lnode = deleteNode(value, node->lnode);
		return node;
	}
	else if (value > node->value)
	{
		node->rnode = deleteNode(value, node->rnode);
		return node;
	}
	else if (value == node->value)
	{
		if (node->lnode == nullptr)
			return node->rnode;
		else if (node->rnode == nullptr)
			return node->lnode;
		else
		{
			node->rnode = lift(node->rnode, node);
			return node;
		}
	}
}

int main()
{
	CBTreeNode* node3_1 = new CBTreeNode(4);
	CBTreeNode* node3_2 = new CBTreeNode(11);
	CBTreeNode* node3_3 = new CBTreeNode(30);
	CBTreeNode* node3_4 = new CBTreeNode(40);
	CBTreeNode* node3_5 = new CBTreeNode(52);
	CBTreeNode* node3_6 = new CBTreeNode(61);
	CBTreeNode* node3_7 = new CBTreeNode(82);
	CBTreeNode* node3_8 = new CBTreeNode(95);
	CBTreeNode* node2_1 = new CBTreeNode(10, node3_1, node3_2);
	CBTreeNode* node2_2 = new CBTreeNode(33, node3_3, node3_4);
	CBTreeNode* node2_3 = new CBTreeNode(56, node3_5, node3_6);
	CBTreeNode* node2_4 = new CBTreeNode(89, node3_7, node3_8);
	CBTreeNode* node1_1 = new CBTreeNode(25, node2_1, node2_2);
	CBTreeNode* node1_2 = new CBTreeNode(75, node2_3, node2_4);
	CBTreeNode* root = new CBTreeNode(5, node1_1, node1_2);

	if (nullptr != search(45, root))
		cout << "search success!! [45]" << endl;
	else
		cout << "search failed!! [45]" << endl;
	insert(45, root);
	cout << "insert [45]" << endl;
	if (nullptr != search(45, root))
		cout << "search success!! [45]" << endl;
	else
		cout << "search failed!! [45]" << endl;
	deleteNode(45, root);
	cout << "delete [45]" << endl;
	if (nullptr != search(45, root))
		cout << "search success!! [45]" << endl;
	else
		cout << "search failed!! [45]" << endl;
	return 0;
}