[Data Structure] B-Tree 구현 - 탐색, 삽입(1)

B-Tree 의 기초 개념은 아래에서 확인하면 된다.

2022.09.11 - [Data Structure/Tree] - [Data Structure] B-Tree 기초

[Data Structure] B-Tree 기초

---

이번에는 B-Tree 의 탐색과정과 노드 추가 과정을 코드로 구현해보려고 한다.

B-Tree 도 역시 클래스를 이용하여 구현하였다. 

 

B-Tree 헤더 파일

• 기본적으로 b-tree 구조체와 클래스, 클래스 맴버 함수 등을 선언해 놓은 파일이다.
• BTREE_ERROR_CODE_DEFIE 이라는 enum 변수는 에러 처리를 위해 추가한 내용이다.
• BTREE 구조체에는 다음과 같은 값이 정의되어 있다.
  • iData[]: 숫자를 저장 할 배열. 노드에 저장되는 값을 의미한다.
  • pChild[]: 해당 노드의 자식 노드 배열
  • bIsLeaf: leaf node 여부
  • iDataCnt: 해당 노드에 저장된 데이터의 수
  • iChildCnt: 해당 노드의 자식 노드 수

#pragma once

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <math.h>

// b-tree 차수
#define BTREE_DEGREE		3
// b-tree 노드의 최대 데이터 개수
#define BTREE_MAX_KEY		BTREE_DEGREE - 1
// b-tree root node 와 leaf node를 제외한 모든 노드의 최대 개수
#define BTREE_MAX_CHILD		BTREE_DEGREE
// b-tree 노드의 최소 데이터 개수
#define BTREE_MIN_KEY		(int)(floor(BTREE_DEGREE / 2.0) - 1)

enum BTREE_ERROR_CODE_DEFINE
{
	BTREE_SUCCESS	=	0,
	BTREE_FUNCTION_FAIL,
	BTREE_MEMORY_ALLOC_FAIL	
};

// b-tree 노드 구조체
struct BTREE
{
	// node의 데이터 배열
	int iData[BTREE_MAX_KEY + 1];
	// node의 자녀 포인터 배열
	BTREE* pChild[BTREE_MAX_CHILD + 1];
	// leaf 노드 여부
	bool bIsLeaf;
	// Data 개수
	int iDataCnt;
	// 자식 노드 개수
	int iChildCnt;
};

class CBTree 
{
public:
	CBTree();
	~CBTree();

public:
	void PrintTree(BTREE** pNode, int iNum);
	void Print();
	int Insert(int iData);
	int SortData(BTREE* pNode);
	BTREE* SearchBTree(BTREE* pNode, int iData, BTREE* pParentNode);
	BTREE* AddNode(BTREE* pNode, BTREE* pParentNode, int iData);
	BTREE* SplitNode(BTREE* pNode, BTREE* pParentNode);

private:
	BTREE* m_Root;
};

B-Tree 탐색

• BST의 탐색 과정과 유사하다.
• 최상위 노드의 데이터부터 비교하여 진행한다.
• 탐색하려는 값이 현재 노드의 값 보다 작을 경우, 왼쪽 서브 트리를 탐색한다.
• 탐색하려는 값이 현재 노드의 값 보다 클 경우, 오른쪽 서브 트리를 탐색한다.

2022.09.05 - [Data Structure/Tree] - [Data Structure] Tree 이진 탐색 트리(BST) 구현

[Data Structure] Tree 이진 탐색 트리(BST) 구현

탐색 과정의 예시를 보이자면, 아래와 같다.

우선, 탐색하고자 하는 값은 '9' 다.

 

1. 먼저 루트 노드에서부터 시작을 한다. 루트 노드의 4, 8 값과 비교를 한다.

탐색 시작

2. 9 는 8 보다 크기 때문에 루트 노드의 오른쪽 서브 트리로 이동한다.

오른쪽 서브 트리 이동

3. 이동한 노드의 값은 10 이고, 9는 10 보다 작기 때문에 왼쪽 서브 트리로 이동한다.

     탐색하고자 하는 9를 찾았다.

9 탐색 완료

 

해당 과정을 수행하는 코드는 아래와 같다.

BTREE* CBTree::SearchBTree(BTREE* pNode, int iData, BTREE* pParentNode)
{
	if (NULL == pNode || NULL == pParentNode)
		return NULL;

	BTREE* pRetNode = NULL;

	int iIndex = 0;
	
	pRetNode = pNode;

	// tree 탐색 시작
	while (pRetNode)
	{
    	// node가 가질 수 있는 데이터 최대 개수 만큼 탐색
		for (iIndex = 0; iIndex < BTREE_MAX_KEY; iIndex++)
		{
			if (iData < pRetNode->iData[iIndex])
				break;
			else if (iData == pRetNode->iData[iIndex])
				return pRetNode;
		}
        // 해당 노드의 자식 노드 탐색을 위한 과정
		pParentNode = pRetNode;
		pRetNode = pRetNode->pChild[iIndex];
	}

	return pRetNode;
}

B-Tree 삽입

•