자료구조 - 트리
트리라는 것은 노드들이 나무처럼 연결되어 있는 계층적인 자료구조이다.
트리에서 가장 위의 노드를 루트노드라고 하고, 제일 밑의 노드를 리프 노드라고 한다.
그리고 A노드와 B노드가 서로 연결되어 있을 때 상위에 있는 노드를 부모 노드라고 하고, 하위에 있는 노드를 자식 노드라고 한다.
트리에서 부모는 반드시 하나이고 child는 여러 개여도 된다.
이때 자식의 수가 많아야 2개이면 binary tree라고 한다.
트리에서 루트에서 다른 노드까지의 연결된 길을 path라고 하는데 트리는 다른 노드와의 path가 유일해야 한다.
부모를 포함해서 자신보다 위에 있는 노드를 ancestor라고 하고, 자식을 포함해서 자신보다 아래에 있는 노드를 descendant라고 한다.
루트노드를 depth(level)가 0이라 하고 루트노드의 자식들을 depth가 1이라고 한다.
이렇게 해서 전체 트리의 depth의 수를 트리의 height라고 하는데 상황에 따라서는 가장 아래의 노드의 depth를 height라고 하는 경우도 있지만 편의를 위해 height는 전체 트리의 depth의 수로 정의하겠다.
Full tree는 모든 리프 노드가 아닌 노드는 자식 노드를 2개씩 가지고 있는 노드를 의미한다.
Tree의 시간 복잡도
Full tree일 때 이진트리가 가질 수 있는 depth가 최소이기 때문에 전체 노드의 수가 N개라고 했을 때 height는 $2^h - 1 = N$ 즉, $h = \log_2 (N + 1)$ 이므로 시간 복잡도는 $O(\log_2 N)$로 이때가 가장 적고, 시간 복잡도가 가장 큰 형태는 N개의 노드가 각각 자식 노드 1개씩 가지고 있는 형태로 이때는 시간 복잡도가 $O(N)$이다.
Insert
이진 트리에 원소를 저장할 때 현재 노드의 값과 비교하여 왼쪽에 저장해야 할지 오른쪽에 저장해야 할지 정할 수 있어야 한다.
만약 현재의 노드의 값보다 큰 값이 입력되면 오른쪽 path로 이동하고, 작은 값이 입력되면 왼쪽 path로 이동하여 만약 해당 방향의 path가 존재하지 않으면 그 부분에 새로운 노드를 삽입하여 트리에 insert를 한다.
이때 tree를 reference type으로 넘겨줘야 한다. 왜냐하면 현재 노드에서 새로운 노드를 연결해 줘야 하는데 reference로 하지 않으면 원본 tree가 같이 수정되지 않기 때문이다.
이러한 방식으로 원소들을 분류하여 트리로 구성하기 때문에 트리에서 특정 원소를 탐색할 때 모든 노드를 다 확인하지 않고 노드에서 어떤 path로 나아가야 할지를 확인할 수 있다.
이러한 아이디어로 트리를 구현해 보면 노드에서 info로 어떤 값을 저장하는지 표현해줘야 하고 left node를 가리키는 포인터와 right node를 가리키는 포인터를 포함해야 한다.
노드 탐색
트리의 노드들을 출력하거나, 트리를 지우거나, 트리를 복사할 때 트리의 있는 모든 노드들을 탐색을 해야 한다.
이때 리스트에서는 모든 노드들이 일렬로 연결되어 있기 때문에 앞에서부터 차례대로 탐색을 하면 되었지만 트리의 경우 하나의 방향으로 연결되어있지 않기 때문에 기존과 다른 탐색 방법을 고안해야 한다.
탐색 방법으로는 Inorder Traversal, Postorder Traversal, Preorder Traversal로 3가지가 있는데 각각 자기 자신을 언제 탐색하는지 차이가 있다.
Inorder Traversal는 재귀함수를 통해 노드에서 왼쪽 서브트리를 탐색하고 자기 자신을 탐색한 뒤 오른쪽 서브트리를 탐색하는 방식이다.
트리에서 Inorder Traversal이 사용된 경우는 트리의 모든 노드를 출력할 때로 다음과 같이 출력이 된다.
Postorder Traversal는 자기 자신을 가장 마지막에 탐색하는 방식으로 재귀함수를 통해 노드에서 왼쪽 서브트리를 탐색하고 오른쪽 서브트리를 탐색한 뒤 자기 자신을 탐색하는 방법이다.
소멸자와 같이 모든 노드를 지워줄 때는 항상 하위 노드를 먼저 제거하고 나서 상위 노드를 제거해야 하기 때문에 Postorder Traversal방식을 사용하여 탐색해야 한다.
마지막으로 Preorder Traversal은 자기 자신을 가장 먼저 탐색하는 방식으로 현재 노드를 탐색한 뒤 재귀함수를 통해 노드에서 왼쪽 서브트리를 탐색하고 오른쪽 서브트리를 탐색한다.
트리에서 Preorder Traversal이 상용되는 경우는 트리를 복사하여 새로운 트리를 만들 때인데 상위 노드가 있어야 해당 노드를 연결하여 하위 노드를 생성할 수 있기 때문에 이러한 방식을 사용해야 한다.
이와 같이 트리를 탐색할 때 각각의 방식에 따라 탐색하게 되는 순서가 다른 것을 볼 수 있다.
LengthIs
트리에서 전체 노드의 수를 구하는 방법은 간단히 현재 노드에서 왼쪽 트리의 노드의 총 합 + 오른쪽 트리의 노드의 총 합 + 1(자신)으로 해주면 된다.
따라서 이 식을 재귀를 통해 LengthIs를 구현하면 전체 노드의 수를 알 수 있다.
Delete
트리에서 가장 큰 문제는 특정 노드를 제거할 때이다.
만약 제거하려는 노드가 리프노드일 경우 해당 노드만 제거해 주면 되기 때문에 큰 문제가 없지만 하나의 혹은 그 이상의 자식 노드가 있는 경우 해당 노드만 제거하게 되면 그 밑의 자식 노드들과 트리의 연결이 끊기기 때문에 따로 처리를 해줘야 한다.
만약 자식 노드가 한 개라면 Linked List에서 delete를 한 방식과 동일하게 제거해야 할 노드 이전 노드에서 제거할 노드 다음 노드를 연결하고 노드를 제거해 주면 된다.
하지만 자식 노드가 두 개인 경우는 왼쪽 혹은 오른쪽 노드를 같은 방법으로 연결한다고 했을 때 새롭게 만들어진 트리가 모든 노드에서 왼쪽 자식 노드는 현재 노드보다 작은 값이고, 오른쪽 자식 노드는 현재 노드보다 큰 값을 만족한다고 보장할 수 없게 된다.
따라서 왼쪽 또는 오른쪽 노드가 아닌 왼쪽 서브 트리에서 가장 큰 값 혹은 오른쪽 서브 트리에서 가장 작은 값으로 삭제해야 할 노드의 값을 대체하면 된다.
이제 위에서 다룬 내용을 바탕으로 tree를 구현하면 다음과 같이 짤 수 있다.
enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };
class TreeType {
TreeNode* root;
public:
TreeType();
~TreeType();
TreeType(const TreeType& originalTree);
void operator=(const TreeType& originalTree);
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
int LengthIs() const;
void RetrieveItem(ItemType& item, bool& found);
void InsertItem(ItemType item);
void DeleteItem(ItemType item);
void ResetTree(OrderType order);
void GetNextItem(ItemType& item, OrderType order, bool& finished);
void Print(std::ofstream& outFile) const;
};
struct TreeNode {
ItemType info;
TreeNode* left;
TreeNode* right;
};
TreeType::TreeType() {
root = NULL;
}
void Destroy(TreeNode*& tree) {
if (tree != NULL) {
Destroy(tree->left);
Destroy(tree->right);
delete tree;
}
}
TreeType::~TreeType() {
Destroy(root);
}
void CopyTree(TreeNode*& copy, const TreeNode* originalTree) {
if (originalTree == NULL)
copy = NULL;
else {
copy = new TreeNode;
copy->info = originalTree->info;
CopyTree(copy->left, originalTree->left);
CopyTree(copy->right, originalTree->right);
}
}
TreeType::TreeType(const TreeType& originalTree) {
CopyTree(root, originalTree.root);
}
void TreeType::operator= (const TreeType& originalTree) {
if (&originalTree == this)
return;
Destroy(root);
CopyTree(root, originalTree.root);
}
void TreeType::MakeEmpty() {
Destroy(root);
root = NULL;
}
bool TreeType::IsEmpty() const {
return root == NULL;
}
bool TreeType::IsFull() const {
TreeNode* location;
try {
location = new TreeNode;
delete location;
return false;
}
catch (std::bad_alloc exception) {
return true;
}
}
int CountNodes(TreeNode* tree) {
if (tree == NULL)
return 0;
else
return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}
int TreeType::LengthIs() const {
return CountNodes(root);
}
void Retrieve(TreeNode* tree, ItemType& item, bool& found) {
if (tree == NULL)
found = false;
else if (item < tree->info)
Retrieve(tree->left, item, found);
else if (item > tree->info)
Retrieve(tree->right, item, found);
else {
item = tree->info;
found = true;
}
}
void TreeType::RetrieveItem(ItemType& item, bool& found) {
Retrieve(root, item, found);
}
void Insert(TreeNode*& tree, ItemType item) {
if (tree == NULL) {
tree = new TreeNode;
tree->right = NULL;
tree->left = NULL;
tree->info = item;
}
else if (item < tree->info)
Insert(tree->left, item);
else
Insert(tree->right, item);
}
void TreeType::InsertItem(ItemType item) {
Insert(root, item);
}
void GetPredecessor(TreeNode* tree, ItemType& data{
while (tree->right != NULL)
tree = tree->right;
data = tree->info;
}
TreeNode* PtrToSuccessor_Recursive(TreeNode* tree) {
if (tree->left != NULL) {
PtrToSuccessor_Recursive(tree->left);
}
else {
TreeNode* tempPtr = tree;
tree = tree->right;
return tempPtr;
}
}
TreeNode* PtrToSuccessor_NonRecursive(TreeNode* tree) {
while (tree->left != NULL) {
tree = tree->left;
}
TreeNode* tempPtr = tree;
tree = tree->right;
return tempPtr;
}
void DeleteNode(TreeNode*& tree) {
ItemType data;
TreeNode* tempPtr;
tempPtr = tree;
if (tree->left == NULL) {
tree = tree->right;
delete tempPtr;
}
else if (tree->right == NULL) {
tree = tree->left;
delete tempPtr;
}
else {
TreeNode* imSuccessor = PtrToSuccessor_NonRecursive(tree->right);
tree->info = imSuccessor->info;
delete imSuccessor;
}
}
void Delete(TreeNode*& tree, ItemType item) {
if (item < tree->info)
Delete(tree->left, item);
else if (item > tree->info)
Delete(tree->right, item);
else
DeleteNode(tree);
}
void TreeType::DeleteItem(ItemType item) {
Delete(root, item);
}
void PreOrder(TreeNode* tree, QueType& preQue) {
if (tree != NULL) {
preQue.Enqueue(tree->info);
PreOrder(tree->left, preQue);
PreOrder(tree->right, preQue);
}
}
void InOrder(TreeNode* tree, QueType& inQue) {
if (tree != NULL) {
InOrder(tree->left, inQue);
inQue.Enqueue(tree->info);
InOrder(tree->right, inQue);
}
}
void PostOrder(TreeNode* tree, QueType& postQue) {
if (tree != NULL) {
PostOrder(tree->left, postQue);
PostOrder(tree->right, postQue);
postQue.Enqueue(tree->info);
}
}
void TreeType::ResetTree(OrderType order) {
switch (order) {
case PRE_ORDER: PreOrder(root, preQue);
break;
case IN_ORDER: InOrder(root, inQue);
break;
case POST_ORDER: PostOrder(root, postQue);
break;
}
}
void TreeType::GetNextItem(ItemType& item, OrderType order, bool& finished) {
finished = false;
switch (order) {
case PRE_ORDER: preQue.Dequeue(item);
if (preQue.IsEmpty())
finished = true;
break;
case IN_ORDER: inQue.Dequeue(item);
if (inQue.IsEmpty())
finished = true;
break;
case POST_ORDER: postQue.Dequeue(item);
if (postQue.IsEmpty())
finished = true;
break;
}
}
void PrintTree(TreeNode* tree, std::ofstream& outFile) {
if (tree != NULL) {
PrintTree(tree->left, outFile);
outFile << tree->info;
PrintTree(tree->right, outFile);
}
}
void TreeType::Print(std::ofstream& outFile) const {
PrintTree(root, outFile);
}
파이썬으로 구현하면 다음과 같이 쓸 수 있다.
class NodeType:
def __init__(self, data):
self.info = data
self.left = None
self.right = None
class IterBST():
def __init__(self):
self.root = None
self.order_list = []
def insert(self, data):
parent = self.find_node(self.root, data)
if self.root == None:
self.root = NodeType(data)
elif data < parent.info:
parent.left = NodeType(data)
else:
parent.right = NodeType(data)
def find(self, key):
return self.find_node(self.root,key)
def find_node(self, root, key):
found = False
current = NodeType(key)
while root != None and not found:
current = root
if key > root.info:
root = root.right
elif key < root.info:
root = root.left
else:
found=True
return current
def delete(self, key):
self.root = self.delete_node(self.root, key)
def delete_node(self, node, key):
if node is None:
return None
if node.info > key:
node.left = self.delete_node(node.left, key)
return node
elif node.info < key:
node.right = self.delete_node(node.right, key)
return node
else:
if node.left is None and node.right is None:
return None
elif node.left is None:
return node.right
elif node.right is None:
return node.left
else:
data = self.get_predecessor(node.left)
node.info = data.info
node.left = self.delete_node(node.left, data.info)
return node
def inorder(self, node):
if node != None:
self.inorder(node.left)
self.order_list.append(node.info)
self.inorder(node.right)
def preorder(self, node):
if node != None:
self.order_list.append(node.info)
self.preorder(node.left)
self.preorder(node.right)
def postorder(self, node):
if node != None:
self.postorder(node.left)
self.postorder(node.right)
self.order_list.append(node.info)
def get_predecessor(self, data):
while data.right != None:
data = data.right
return data