[자료구조] L08. Binary Search Tree

• toc {:toc}

Binary Tree

• Property1 : 각 노드들은 최대 2개의 자식을 갖는다.

• Property2 : 루트부터 다른 노드까지 유일한 길을 갖는다.

• 포화 이진 트리(Perfect Binary Tree) : 리프 노드가 아닌 모든 노드들은 2개의 자식을 가지고 모든 리프 노드가 차 있는 트리를 말한다.

  • i 레벨에서 최대 노드 :

• 이진 검색 트리

  • 모든 노드들은 겹치지 않는 고유한 데이터 값을 가진다고 가정한다.
  • 키값은 크고 작고를 비교할 수 있다.
  • 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리로 이동한다.

• 검색 시간

  • 최악의 경우 - O(N)
  • 최선의 경우 - O(logN)

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& item, bool& found);
	void InsertItem(ItemType);
	void DeleteItem(ItemType);
	void ResetTree(OrderType);
	void GetNextItem(ItemType&, OrderType, bool&);
	void PrintTree(ofstream&) const;
private:
	TreeNode<ItemType>* root;
};

• 노드 개수 카운트

int CountNodes(TreeNode* tree){
	if (tree == NULL)
		return 0;
	else
		return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}

• 노드 존재하는지 찾기

void RetrieveItem(ItemType& item, bool& found){
	Retrieve(root, item, found);
}
 
void Retrieve(TreeNode* tree, ItemType& item, bool& found){
	if (tree == NULL)
		found=false;
	else if (tree->info > item)
		Retrieve(tree->left, item, found);
	else if (tree->info < item)
		Retrieve(tree->right, item, found);
	else{
		found = true;
	}
}

• 노드 삽입

void Insert(TreeNode*& tree, ItemType item){
	if (tree == NULL){
		tree = new TreeNode;
		tree->right = NULL;
		tree->left = NULL;
		tree->info = item;
	}
	else if (tree->info > item)
		Insert(tree->left, item);
	else
		Insert(tree->right, item);
}

• 노드 삽입은 위치를 찾아가서 포인터 조정을 해준다.

• 또한, 이전 Sorted List와 같이 포인터의 주소를 지정해준다. 즉, 만약 tree→info > item 인 경우 tree→left를 파라미터로 넘겨주는데, 이때 tree→left에 new로 동적 할당받기 때문에 부모와의 포인터 연결을 tree == NULL 조건에서 해주지 않아도 된다.

• 노드 삭제

  • 자식이 없는 경우
  • 자식이 하나만 있는 경우
  • 자식이 두 개 있는 경우

void DeleteItem(ItemType item){
	Delete(root, item);
}
 
void Delete(TreeNode*& tree, ItemType item){
// 해당 item이 있는 위치까지 이동한다.
 
    if (tree == NULL){
        return;
    }
    
    if (item < tree->info){
        Delete(tree->left, item);
    }
    else if (item > tree->info){
        Delete(tree->right, item);
    }
    else{ // 찾으면 DeleteNode를 한다.
        DeleteNode(tree);
    }
}
 
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{
        while(tree->right != NULL){ // 왼쪽 서브트리의 맨 오른쪽 리프 찾기
	        tree = tree->right;
        }
		data = tree->info;
 
		tree->info = data;         // 리프 노드 지운자리로 이동
        Delete(tree->left, data);  // 찾은 리프 지우기
    }
}

Recursive Print

Inorder

• LDR (Left, Data, Right) 순서
• 크기 순서대로 출력하는 경우 inorder 방식을 사용한다.

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

Preorder

• DLR (Data, Left, Right) 순서
• Constructor를 만들 때 루트 노드부터 만들어야 하기 때문에 preorder를 사용한다.
• DFS와 같다.

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

Postorder

• LRD (Left, Right, Data) 순서
• Destructor를 만들 때 리프 노드부터 삭제해야 하기 때문에 postorder 방식을 사용한다.

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

Iterative Method

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;
	}
}
 
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;
}
 
void TreeType::DeleteItem(ItemType item)
{
	TreeNode* nodePtr;
	TreeNode* parentPtr;
	FindNode(root, item, nodePtr, parentPtr);
	if (nodePtr == root)
		DeleteNode(root);
	else
		if (parentPtr->left == nodePtr)
			DeleteNode(parentPtr->left);
		else 
			DeleteNode(parentPtr->right);
}