1. 트리
* 비선형 문제 *
-선형 자료구조로 표현할 수 없는 계층적 문제, 순환 종속성 문제를 풀기 위한 방법 = 트리
-트리: 중심이 되는 노드를 루트 노드라 하고, 이 노드는 보통 가장 맨 위에 있다.
1) 이진 트리 기본 구성
#include <iostream>
#include <queue>
struct Node
{
std::string mData;
Node* mLeft;
Node* mRight;
};
class org_tree
{
Node* mRoot;
public:
static org_tree createLoot(const std::string& value, Node* pLeft=nullptr, Node* pRight = nullptr)
{
org_tree tree;
tree.mRoot = new Node{value, pLeft, pRight};
return tree;
}
static Node* find(Node* root, const std::string& value)
{
if (root == nullptr)
return nullptr;
if (root->mData == value)
return root;
auto leftFound = find(root->mLeft, value);
if (leftFound != nullptr)
return leftFound;
return find(root->mRight, value);
}
bool addSubOrdinate(const std::string& manager, const std::string& subordinate)
{
auto managerNode = find(mRoot, manager);
if (!managerNode)
{
std::cout << manager << "을(를) 찾을 수 없습니다." << std::endl;
return false;
}
if (managerNode->mLeft && managerNode->mRight)
{
std::cout << manager << "아래에 " << subordinate << "을(를) 추가할 수 없습니다." << std::endl;
return false;
}
if (!managerNode->mLeft)
managerNode->mLeft = new Node{ subordinate, nullptr, nullptr };
else
managerNode->mRight = new Node{ subordinate, nullptr, nullptr };
std::cout << manager << "아래에 " << subordinate << "을(를) 추가했습니다." << std::endl;
return true;
}
}
-이진 트리 클래스에 순회 함수 추가
① 전위 순회(preOrder traversal) - 재귀 함수
: 현재 노드를 먼저 방문하고, 그 다음 현재 노드의 왼쪽 하위 노드를, 마지막으로 현재 노드의 오른쪽 하위 노드를 방문하는 순회 방법
(전위의 뜻: 상위 노드를 하위 노드보다 먼저 방문한다는 뜻)
② 중위 순회(inOrder traversal) - 재귀 함수
: 왼쪽 노드 방문 -> 현재 노드 방문 -> 오른쪽 노드 방문
③ 후위 순회(postOrder traversal) - 재귀 함수
: 두 자식 노드를 먼저 방문 -> 현재 노드 방문
④ 레벨 순서 순회(levelOrder traversal) - 재귀를 사용하지 않는 것이 더 쉬움
: 루트 노드부터 레벨별로 방문(1레벨 모두 출력, 2레벨 모두 출력...)
-현재 노드에 직접 연결되지 않은 노드로 이동함
-제일 처음 노드를 큐에 추가
-큐에 원소가 있다면 while문 안에서 큐의 첫 번째 원소를 분석
-만약 첫 번째 원소에 하위 노드가 있으면 큐에 추가 (만약 1레벨 원소를 분석하면 2레벨 원소를 큐에 넣을 수 있음)
-마지막 레벨이면 큐에 들어갈 원소가 없기 때문에 끝나게 됨
static void preOrder(Node* start)
{
if (!start)
return;
std::cout << start->mData << ", ";
preOrder(start->mLeft);
preOrder(start->mRight);
}
static void inOrder(Node* start)
{
if (!start)
return;
inOrder(start->mLeft);
std::cout << start->mData << ", ";
inOrder(start->mRight);
}
static void postOrder(Node* start)
{
if (!start)
return;
postOrder(start->mLeft);
postOrder(start->mRight);
std::cout << start->mData << ", ";
}
static void levelOrder(Node* start)
{
if (!start)
return;
std::queue<Node*> level;
level.push(start);
while (!level.empty())
{
int size = level.size();
for (int i = 0; i < size; i++)
{
auto temp = level.front();
level.pop();
std::cout << temp->mData << ", ";
if (temp->mLeft)
level.push(temp->mLeft);
if (temp->mRight)
level.push(temp->mRight);
}
std::cout << std::endl;
}
}
2) 이진 검색 트리(Binary Search Tree)
부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 되어 검색 및 삽입 시 검색 범위가 절반으로 줄어들어 이진트리보다 효율적이다.
① 삽입 함수 – 재귀
하위 노드로 이동하며 삽입할 위치의 부모 노드를 찾음. 부모 노드가 하위 노드를 가지고 있지 않으면
바로 삽입하고, 하위 노드를 이미 가지고 있으면 다시 삽입 함수를 재귀 호출해 하위 노드가 없을 때까지 내려감
#include <iostream>
struct Node
{
int mData;
Node* mLeft;
Node* mRight;
};
class BST
{
Node* mRoot;
public:
BST(Node* root = nullptr) : mRoot(root) {}
~BST() {}
int GetRoot()
{
return mRoot->mData;
}
Node* find(int value)
{
return find_impl(mRoot, value);
}
private:
Node* find_impl(Node* current, int value)
{
if (!current)
{
return nullptr;
}
if (current->mData == value)
{
std::cout << value << "을(를) 찾았습니다." << std::endl;
return current;
}
if (value < current->mData)
{
std::cout << current->mData << "에서 왼쪽으로 이동->";
return find_impl(current->mLeft, value);
}
std::cout << current->mRight << "에서 오른쪽으로 이동->";
return find_impl(current->mRight, value);
}
}② 후속 노드를 찾는 함수 ★중요 -> 노드 삭제에 이용
후속 노드란? 현재 노드 다음으로 큰 숫자를 가진 노드
즉, 현재 노드의 오른쪽 서브 트리로 이동 후 가장 작은 노드를 찾기 위해 제일 왼쪽 노드로 이동하면 됨
Node* successor(Node* start)
{
auto current = start->mRight;
while (current && current->mLeft)
current = current->mLeft;
return current;
}
③ 노드 삭제 함수
public:
void deleteValue(int value)
{
mRoot = delete_impl(mRoot, value);
}
private:
Node* delete_impl(Node* start, int value)
{
if (!start)
return nullptr;
if (value < start->mData)
start->mLeft = delete_impl(start->mLeft, value);
else if (value > start->mData)
start->mRight = delete_impl(start->mRight, value);
else
{
if (!start->mLeft) // 자식노드가 없거나 왼쪽 노드가 없음
{
auto tmp = start->mRight;
delete start;
return tmp;
}
if (!start->mRight) // 오른쪽 노드가 없는 경우
{
auto tmp = start->mLeft;
delete start;
return tmp;
}
// 자식 노드가 둘 다 있는 경우 - 후속노드의 수를 루트 노드에 삽입
auto succNode = successor(start);
start->mData = succNode->mData;
// 오른쪽 서브 트리에서 후속 노드를 삭제
start->mRight = delete_impl(start->mRight, succNode->mData);
}
return start;
}
④ 중위 순회 함수 – 이진 검색 트리에서 데이터를 오름차순으로 출력하게 할 수 있음
public:
void inOrder()
{
inOrder_impl(mRoot);
}
private:
void inOrder_impl(Node* start)
{
if (!start)
return;
inOrder_impl(start->mLeft);
std::cout << start->mData << " ";
inOrder_impl(start->mRight);
}
3) 균형 트리
-원소 검색의 시간 복잡도 최적화를 위해서는 트리의 양쪽 서브 트리 길이가 비슷한 것이 좋다
-> 트리의 높이가 최적화 되어야 함 = 트리의 균형 잡기
균형 잡힌 트리의 예시: AVL 트리(트리 회전을 통해 수행), 레드-블랙 트리
4) N-항 트리
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 책을 읽고 공부하며 정리한 글입니다