이진 트리

1. 트리 개념

---

• 노드, 간선으로 이루어진 구조
• 코딩테스트에서는 이진 트리만 알고 있으면 충분하다.

출처 : https://namu.wiki/jump/9h0D5P7BJaiIIm01ckQXDHzpfBe46lu4VabFpPInhgnNsalhBmHSfFWyCssB5Zjw

 

 

2. 이진 트리 표현하기

---

2 - 1. 배열로 표현하기

• 루트를 인덱스 1로 시작
• 왼쪽 자식은 부모 노드의 인덱스 x2
• 오른쪽 자식은 부모 노드의 인덱스 x2 + 1

• 이 방식의 단점은 배열의 공간이 조금 낭비된다는 점이다.
• 그러나 매우 간단하기 때문에, 많이 사용하는 방식이다.

 

2 - 2. 이진 트리 순회하기

현재 노드를 부모 노드로 생각했을 때

• 전위 순회 : 부모 -> 왼쪽자식 -> 오른쪽 자식 
• 중위 순회 : 왼쪽 자식 -> 부모 노드 -> 오른쪽 자식
• 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모 노드

위에서 그린 그림을 기반으로 예를 들어보자

더이상 갈 곳이 없거나, 우선순위가 자기 노드인 경우 방문하는 식으로 동작한다.

• 전위 순회
  • 현재 노드(1) : 1 -> 4 -> 8 / 1 방문
  • 현재 노드(4) : 4 -> 3- >5 / 4 방문
  • 현재 노드(3) : 3 -> 2 / 3 방문
  • 현재 노드(2) : 더 방문할 곳이 없으므로 3으로 / 2 방문
  • 현재 노드(3) : 더 방문할 곳이 없으므로 4로
  • 현재 노드(4): 4 -> 3 -> 5 
  • 현재 노드(5) : 더 방문할 곳이 없으므로 1까지 올라감 / 5 방문
  • 현재 노드(1) : 1- > 4- > 8
  • 현재 노드(8) : 8 -> 7 / 8 방문
  • 현재 노드(7) : 7 -> 6 / 7 방문
  • 현재 노드(6) : 끝 / 6 방문
  • 1 -> 4 -> 3 -> 2 -> 5 -> 8 ->7 -> 6
• 중위 순회
  • 현재 노드(1) : 4 -> 1 -> 8
  • 현재 노드(4) : 3 -> 4 -> 5
  • 현재 노드(3) : 3 -> 2
  • 현재 노드(2) : 더 방문할 곳이 없으므로 3으로 / 2 방문
  • 현재 노드(3) : 더 방문할 곳이 없으므로 4로 / 3 방문
  • 현재 노드(4) : 3- > 4 -> 5 / 4 방문
  • 현재 노드(5) : 더 방문할 곳이 없으므로 4로 / 5 방문
  • 현재 노드(4) : 더 방문할 곳이 없으므로 1로
  • 현재 노드(1) : 4 -> 1 -> 8 / 1 방문
  • 현재 노드(8): 8 -> 7 / 8 방문
  • 현재 노드(7) : 6 ->7
  • 현재 노드(6) : 더 방문할 곳이 없으므로 7로 / 6 방문
  • 현재 노드(7): 끝 / 7 방문
  • 2 -> 3 -> 4 -> 5 -> 1 -> 8 -> 6 -> 7
• 후위 순회
  • 현재 노드(1) : 4 -> 8 -> 1
  • 현재 노드(4) : 3-> 5 -> 4
  • 현재 노드(3) : 2 -> 3
  • 현재 노드(2) : 더 방문할 곳이 없으므로 3으로 / 2 방문
  • 현재 노드(3) : 더 방문할 곳이 없으므로 4로 / 3 방문
  • 현재 노드(4) : 3 -> 5 -> 4
  • 현재 노드(5) : 더 방문할 곳이 없으므로 4로 / 5 방문
  • 현재 노드(4) : 더 방문할 곳이 없으므로 1로 / 4 방문
  • 현재 노드(1) : 4 -> 8 -> 1 
  • 현재 노드(8) : 7 -> 8 
  • 현재 노드(7) : 6 -> 7 
  • 현재 노드(6) : 더 방문할 곳이 없으므로 7로 / 6 방문
  • 현재 노드(7) : 더 방문할 곳이 없으므로 8로 / 7 방문
  • 현재 노드(8) : 더 방문할 곳이 없으므로 1로 / 8 방문
  • 현재 노드(1) : 끝 / 1 방문
  • 2 -> 3 -> 5 -> 4 -> 6 ->7 ->8 -> 1

 

2 - 3. 포인터로 표현하기

• 각 노드가 왼쪽/오른쪽 자식 노드를 가리키는 포인터, 값 이렇게 값을 가진 구조로 이루어져 있다.
• 이 방식은 구현은 까다롭지만, 배열로 구현한 방식처럼 공간의 낭비는 없다.

struct Node
{
    Node* leftChild;
    Node* rightChild;
    int value;
}

 

2 - 4. 인접 리스트로 표현하기

• 특정 노드를 찾기 위해 연결 노드를 따라가야 한다는 단점이 있다.

 

3. 이진 트리 탐색하기

 

---

이진 트리에서 가장 중요한 것은 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것이다.

• 그렇게 하기 위해서 이진 트리를 구축할 때, 데이터의 값이 작으면 왼쪽 자식으로, 값이 크면 오른쪽 자식으로 연결하는 방식을 사용한다.

• 위처럼 구성된 경우 특정 값을 찾기 위해서 "평균적으로" O(lgN) 만 비교를 해도 원하는 값을 찾을 수 있다.
• 이진 트리도 한쪽으로 치우치게 구성된 경우 배열과 같이 탐색의 시간 복잡도가 "최악" O(N)가 될 수도 있다.
• 그러므로 균형잡인 이진트리를 구성하는 것이 중요한데, AVL이나 레드블랙 트리 등이 균형잡힌 이진트리여서 O(lgN)의 복잡도를 유지하게 해준다.

 

 

4. 코드

---

• 트리 순회

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

string preorder(vector<int> nodes, int idx)
{
	if (idx < nodes.size())
	{
		string res = to_string(nodes[idx]) + " ";
		res += preorder(nodes, idx * 2 + 1); //왼쪽 
		res += preorder(nodes, idx * 2 + 2); //오른쪽
		return res;
	}
	return "";
}

string inorder(vector<int> nodes, int idx)
{
	if (idx < nodes.size())
	{
		string res = inorder(nodes, idx * 2 + 1); //왼쪽 
		res += to_string(nodes[idx]) + " ";
		res += inorder(nodes, idx * 2 + 2); //오른쪽
		return res;
	}
	return "";
}

string postorder(vector<int> nodes, int idx)
{
	if (idx < nodes.size())
	{
		string res = postorder(nodes, idx * 2 + 1); //왼쪽 
		res += postorder(nodes, idx * 2 + 2); //오른쪽
		res += to_string(nodes[idx]) + " ";
		return res;
	}
	return "";
}

vector<string> solution(vector<int>nodes)
{
	vector<string> answer;

	string pre = preorder(nodes, 0);
	answer.push_back(pre);
	string in = inorder(nodes, 0);
	answer.push_back(in);
	string post = postorder(nodes, 0);
	answer.push_back(post);

	return answer;
}

int main()
{
	vector<int>nodes = { 1,2,3,4,5,6,7 };

	vector<string> ans = solution(nodes);

	for (const auto& a : ans)
	{
		cout << a << "\n";
	}
}

• 이진 탐색 트리 구현

#include <iostream>
#include <vector>
using namespace std;
 
class Node
{
public:
	Node(int _value)
		:left(nullptr)
		, right(nullptr)
		, value(_value)
	{}
public:
	Node* left;
	Node* right;
	int value;
};

class BST
{
public:
	BST()
		:root(nullptr)
	{

	}
	void Insert(int _value)
	{
		root = InsertNode(root, _value);
	}
	bool Search(int _value)
	{
		return SearchNode(root, _value);
	}

private:
	Node* InsertNode(Node* node, int _value)
	{
		if (!node)
			return new Node(_value);		

		if (node->value > _value)
			node->left = InsertNode(node->left, _value);
		else
			node->right = InsertNode(node->right, _value);

		return node;
	}

	bool SearchNode(Node* node, int _value)
	{
		if (!node)
			return false;

		if (node->value == _value)
			return true;

		return node->value > _value ? SearchNode(node->left, _value) : SearchNode(node->right, _value);
	}

private:
	Node* root;
};

vector<bool> solution(vector<int> lst, vector<int>search_lst)
{
	BST bst;
	vector<bool> answer;

	for (const int& l : lst)
	{
		bst.Insert(l);
	}
	for (const int& sl : search_lst)
	{
		answer.push_back(bst.Search(sl));
	}
	return answer;
}

int main()
{
	vector<int> lst = { 5,3,8,4,2,1,7,10 };
	vector<int> search_lst = { 1,2,5,6 };

	vector<bool> ans = solution(lst, search_lst);

	for (auto a : ans)
		cout << a << " ";
}