08. Binary Search Trees

dain·2024년 9월 25일

자료구조

목록 보기

8/8

Tree

계층 구조 표현하는 자료 구조

✏️ 트리는 그래프의 일종이다.
(순환하지 않는 그래프로, 루트로부터 어떤 노드로 가는 경로는 유일하다.)

용어
- Root
  - 트리가 시작되는, 트리의 최상단에 위치한 노드
  - 트리에서 루트는 오직 하나만 존재한다.
  - 루트의 부모는 존재하지 않는다.
- Leaf (= terminal)
  - 자식을 가지지 않는 노드
  - 리프의 자식은 존재하지 않는다.
  - 트리는 루트로부터 리프까지의 방향성을 가진다.
- Non-terminal
  - 트리에서 terminal 노드를 제외한 모든 노드들 (루트 포함)
- Parent
  - 어떤 노드의 predecessor 노드
  - 부모는 하나만 존재한다.
- Child
  - 어떤 노드의 successor 노드
  - 자식은 하나 이상 존재할 수 있다. (단, leaf 노드 제외)
    ✏️ 가능한 자식의 최대 수에 따라 트리를 구분할 수 있다.
    - 제한 X: 일반적인 트리
    - $2^n$ : binary tree
- Ancestor
  - 루트로부터 해당 노드까지의 경로에 있는 모든 노드
- Descendant
  - 해당 노드로부터 경로의 마지막 노드까지의 경로에 있는 모든 노드
- Subtress
  - 트리의 일부도 트리 구조를 만족한다.
- Level (=depth)
  - 루트로부터 해당 노드까지의 경로에 있는 edge의 개수
- Height
  - 레벨의 개수 (level + 1)

Binary Tree

이진 트리의 조건
1. 각 노드는 최대 두 개의 successor (자식) 노드를 갖는다
2. 루트로부터 어떤 노드까지의 경로는 유일하다.
Full Binary Tree
✏️ Full Tree와 Complete Tree
: 이진 트리의 특성을 나타내는 용어
- Full Tree
  : 모든 leaves가 같은 레벨에 있고, 모든 non-leaf 노드가 두 개의 자식을 갖는 이진 트리
- Complete Tree
  : 마지막 레벨을 제외한 모든 레벨에서는 노드가 완전히 채워져 있고, 마지막 레벨에서는 왼쪽부터 순서대로 노드가 채워진 이진 트리
- Height가 $h$ 인 Full Tree의 노드의 개수 $N$
- 노드의 개수가 $N$ 인 Full Tree의 Height $h$
- 모든 이진 트리에 대해 일반화
  - 노드가 $N$ 개인 이진 트리의 최대 높이 : $h = N$
    (연결 리스트 형태)
  - 노드가 $N$ 개인 이진 트리의 최소 높이 : $h = \log(N+1)$
    (완전 이진 트리 형태)

Binary Search Tree

이진 검색 트리

이진 검색 트리의 조건
- 이진 트리
- 각 노드는 고유한 서로 비교할 수 있는 키 값을 가지고 있다. 그리고 각 노드의 키는 오른쪽 서브 트리의 모든 키 값보다 작고, 왼쪽 서브 트리의 모든 키 값보다 크다.

트리의 노드 구조

template<class ItemType>
struct TreeNode {
	ItemType info;
	TreeNode* left;
	TreeNode* right;
};

: 포인터를 사용하는 동적 할당 구조

TreeType 클래스

#include <fstream.h>
#include <iostream.h>

template<class ItemType>
struct TreeNode;

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

template<class ItemType>
class TreeType {

public:
	TreeType(); // 생성자
	~TreeType(); // 소멸자
	TreeType(const TreeType<ItemType>&); // 복사 생성자
	void operator=(const TreeType<ItemType>&); // 대입 연산자
	void MakeEmpty();
	bool isEmpty() const;
	bool isFull() const;
	int LengthIs() const;
	void RetrieveItem(ItemType&, bool& found);
	void InsertItem(ItemType);
	void DeleteItem(ItemType);
	void ResetTree(OrderType);
	void GetNextItem(ItemType&, OrederType, bool&);
	void PrintTree(ofstream&) const;

private:
	TreeNode<ItemType>* root;
};

연산

IsFull & IsEmpty

bool TreeType::IsFull() const
{
  NodeType* location;
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

bool TreeType::IsEmpty() const
{
  return root == NULL;
}

CountNodes

이진 검색 트리 내의 노드의 개수를 세는 함수

코드

// CountNodes
int TreeType::LengthIs() const
{
	return CountNodes(root);
}

int CountNodes(TreeNode* tree)
{
	if (tree == NULL)
		return 0;
	else
		return CountNodes(tree->left) + CountNodes(tree->right) + 1;
		// 왼쪽 서브 트리의 노드 개수 + 오른쪽 서브 트리의 노드 개수
}

RetrieveItem

이진 검색 트리에서 어떤 아이템을 검색하는 함수
검색된 아이템에 대한 정보를 reference로 받아오기 때문에 의미가 있다!

코드

// RetrieveItem
// : wrraper 함수, 시작점을 루트로 설정하고 Retrieve 호출
void TreeType::RetrieveItem(ItemType& item, bool& found)
{
	Retrieve(root, item, found);
}

void Retrieve(TreeNode* tree, ItemType& item, bool& found)
{
	if (tree == NULL) // base case 1 
		found = false;
	else if (item < tree->info) // general case 1
		Retrieve(tree->left, item, found);
	else if (item > tree->info) // general case 2
		Retrieve(tree->right, item, found);
	else { // base case 2
 		item = tree->info;
		found = true;
	}
}

✏️ 만약 재귀가 아닌 반복(iteration)으로 구현한다면…

void FindNode(TreeNode* tree, ItemType item, TreeNode*& nodePtr, TreeNode*& parentPtr)
{
  nodePtr = tree;
  parentPtr = NULL;
  bool found = false;
  while (nodePtr != NULL && !found)
  { if (item < nodePtr->info)
    {
      parentPtr = nodePtr;
      nodePtr = nodePtr->left;
    }
    else if (item > nodePtr->info)
    {
      parentPtr = nodePtr;
      nodePtr = nodePtr->right;
    }
    else found = true;
	}
}

InsertItem

이진 검색 트리에 새로운 아이템을 삽입하는 함수
(이때 추가되는 아이템은 항상 트리의 적절한 위치에, 말단 노드(leaf)로서 삽입된다.)

코드

// 트리 클래스 내의 멤버 함수 
// wrapper 함수로 시작점을 루트로 설정하고 Insert 호출
void TreeType::InsertItem(ItemType item)
{
	Insert(root, item)
}

void Insert(TreeNode*& tree, ItemType item)
{
	if (tree == NULL) // insertion place found.
	{
		tree = new TreeNode;
		tree->right = NULL;
		tree->left = NULL;
		tree->info = tiem;
	}
	else if (item < tree->info)
		Insert(tree->left, item);
	else
		Insert(tree->right, item);
}

✏️ 만약 재귀가 아닌 반복으로 구현한다면…

void TreeType::InsertItem(ItemType item)
{
	TreeNode* newNode;
	TreeNode* nodePtr;
	TreeNode& parentPtr;

	newNode = new TreeNode;
	newNode->info = item;
	newNode->left = NULL;
	newNode->right = NULL;

	FindNode(root, item, nodePtr, parentPtr);

	if (parentPtr == NULL)
		root = newNode;
	else if (item < parentPtr->info)
		parentPtr->left = newNode;
	else
		parentPtr->right = newNode;
	}
}

DeleteItem

이진 검색 트리 내에 존재하는 특정 아이템을 삭제하는 함수
삭제할 노드(아이템)의 위치에 따른 세 가지 분류
1. leaf 노드를 삭제하는 경우
2. 자식이 하나인 노드를 삭제하는 경우
3. 자식이 둘인 노드를 삭제하는 경우
  : 삭제하고자 하는 노드를, 그 노드의 값(Q)보다 작은 값들 중 가장 큰 값(P)으로 대체한 후, 대체한 기존의 노드(P) 삭제

코드

void TreeType::DeleteItem(ItemType item)
{
	Delete(root, item);
}

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, item); // 삭제할 노드를 찾은 경우
}

void DeleteNode(TreeNode*& tree, ItemType data)
// tree: 삭제하고자 하는 노드를 가리키는 포인터 변수
{
	TreeNode* tempPtr;
	tempPtr = tree;

	// 삭제할 노드의 자식이 0 또는 1개인 경우 
	if (tree->left == NULL) { // 삭제할 노드의 오른쪽 자식만 존재하는 경우
		tree = tree->right; // 오른쪽 자식의 포인터 수정
		delete tempPtr // 삭제
	}
	else if (tree->right == NULL) // 삭제할 노드의 왼쪽 자식만 존재하는 경우
		tree = tree->left; // 왼쪽 자식의 포인터 수정
		delete tempPtr; // 삭제
	}
	// 삭제할 노드의 자식이 2개인 경우
	else  
	{
		GetPredecessor(tree->left, data);  // predecessor 설정
		tree->info = data; // 식제할 노드의 값, predecessor로 대체
		Delete(tree->left, data); // 기존의 predecessor 노드 삭제 
	}
}

void GetPredecessor(TreeNode* tree, ItemType& data)
{
	while (tree->right != NULL)
		tree = tree->right;
	data = tree->info;
}

✏️ 만약 재귀가 아닌 반복으로 구현한다면 (FindItem 사용)

<template class ItemType>
void TreeType::DeleteItem(ItemType item)
{
	TreeNode* nodePtr;
	TreeNode* parentPtr;
	
	FindNode(root, item, nodePtr, parentPtr) // item이 삽입될 위치 find

	if (nodePtr == root)
		DeleteNode(root);
	else 
	{
		if (parent->left == nodePtr)
			DeleteNode(parentPtr->left);
		else
			DeleteNode(parentPtr->right);
	}		
}

void PrintTree(TreeNode* tree, ofstream& outFile)
{
 	if (tree != NULL)
   	{
   		PrintTree(tree->left, outFile);
   		outFile << tree->info;
   		PrintTree(tree->right, outFile);
   	}
}

✏️ 트리 순회, inorder

left에 대해 재귀

자기 자신 처리

right에 대해 재귀

생성자

template<class ItemType>
TreeType<ItemType>::TreeType()
{
	root = NULL;
}

소멸자

template<class ItemType>
TreeType<ItemType>::~TreeType()
{
	Destroy(root);
}

void Destroy(TreeNode*& tree)
{
	if (tree != NULL)
	{
		Destroy(tree->left);
		Destroy(tree->right);
		delete tree;
	}
}

✏️ 트리 순회, post order

left 재귀 호출

right 재귀 호출

자기 자신(root 처리): 메모리 해제 delete

복사 생성자

TreeType::TreeType(const TreeType& originalTree)
{
	CopyTree(root, originalTree.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);
	}
}

✏️ 트리 순회, pre order

자기 자신 처리

left 재귀 호출

right 재귀 호출

트리 순회(Tree Traversal)

트리 순회

종류

In Order

void InOrder(TreeNode* tree, QueType& inQue)
{
	if (tree != NULL)
	{
		InOrder(tree->left, inQue);
		InQue.Enqueue(tree->info);
		InOrder(tree->right, inQue);
	}
}

Post Order

void PostOrder(TreeNode* tree, QueType& postQue)
{
	if (tree != NULL)
	{
		PostOrder(tree->left, postQue);
		PostOrder(tree->right, postQue);
		postQue.Enqueue(tree->info);
	}
}

Pre Order

void PreOrder(TreeNode* tree, QueType& preQue)
{
	if (tree != NULL)
	{
		preQue.Enqueue(tree->info);
		PreOrder(tree->left, preQue);
		PreOrder(tree->right, preQue);
	}
}

dain

자라나는 감자

이전 포스트

07. Programming with Recursion

1개의 댓글

SYiee

2024년 9월 26일

글이 너무 깔끔해요! 잘 읽고 갑니다~~

답글 달기