[C++] BTree

구현 완료

• Insert
  • split
• delete
  • merge
• search

미구현
 iterate
잠이 오긴 하지만 잠시 생각 해보자.
Btree는 iteration이 상당히 까칠하다. 그럼 list를 추가하면 될듯한데..그럼 키는 트리에 유지하고 값만 리스트에 저장 하면 되겠군. 그런데 문제는 트리가 다시 밸런스를 맞추면서인데..예를 들어 2:2가 들어 오고 3:3이 들어 오고 1:1이 들어 오면 3이야 뒤에 추가 하면 되니 아무런 문제가 없지만 1:1은 2보다 작다는 것을 알 수 있으니까 2의 iterator 앞에 넣어 주면 되겠군. 대충 돌아 갈 수 있을 것 같구먼
 erase

소스 코드 :

티스토리 버그인지 모르겠으나 코드 라인 정렬이 계속 깨져 파일을 따로 업로드 한다.

BTree.h

0.01MB

#pragma once

#pragma pack(push,8)
#pragma warning(push,3)
#include <functional>

#define DEGREE 5

template <
    class _Key,
    class _Data,
    class _Compare = std::less<_Key>,
    class _Alloc = std::allocator<std::pair<const _Key, _Data> > >
class BTree {
public:
	typedef _Key key_type;
	typedef _Data data_type;
	typedef std::pair<key_type, data_type> value_type;
	typedef value_type* pointer;
	typedef value_type& reference;
	typedef _Compare key_compare;
	typedef unsigned int size_type;
	
	struct NODE;
	struct iterator {
		iterator() : m_pNode(NULL), m_index(-1) {
		}
		NODE* m_pNode;
		int m_index;
		
		pointer operator->() const
		{	// return pointer to class object
			if(NULL == m_pNode) {
				return NULL;
			}
			return &(m_pNode->m_values[m_index]);
		}
		iterator& operator = (const iterator& i) {
			m_index = i.m_index;
			m_pNode = i.m_pNode;

			return (*this);
		}
	};

	struct NODE {
		NODE() {
			Init();
		}
		int 		m_count;
		value_type	m_values[DEGREE];
		NODE* 		m_children[DEGREE+1];
		NODE* 		m_parent;
		/**
			init
		*/
		void Init()	{
			m_count = 0;
			m_parent = NULL;
			memset(m_children, 0, sizeof(NODE*)*(DEGREE+1));
		} 
		/**
			중복 키 허용하지 않음.
			중복 되는 키가 있다면 이전 키에 대한 데이터는 덮어 써짐
		*/
		void insert(const value_type& x, int index) {
			key_compare compare_functor;
			if(compare_functor(x.first, m_values[index].first) || compare_functor(m_values[index].first, x.first)) {
				for(int i=m_count; i>index; --i) {
					m_values[i] = m_values[i-1];
					m_children[i+1] = m_children[i];
				}
				if(index <= m_count) {
					m_children[index+1] = m_children[index];
				}
				m_count += 1;
			}
			m_values[index] = x;
		}
		
		/**
			Finds an element whose key		
		*/
		std::pair<int, bool> find(const key_type& key) const {
			key_compare compare_functor;
			int index = 0;
			for(index=0; index<m_count; ++index) {
				if(compare_functor(key, m_values[index].first)) {
					return std::make_pair(index, false);
				}
				else if(!compare_functor(m_values[index].first, key)) {
					return std::make_pair(index, true);
				}
			}
			return std::make_pair(m_count, false);
		}

		/**
			키의 삭제
			키의 삭제는 항상 leaf에서만 일어 나므로 자식에 대한 걱정은 하지 않아도 됨
		*/																										    
		void erase(int index) {
			m_count -= 1;
			for(int i=index; i<m_count; ++i) {
				m_values[i] = m_values[i+1];
			}
		}
		/**
			키의 successor를 리턴
			leaf일 경우에는 NULL리턴
		*/
		NODE* findSuccessor(int index) {
			NODE* curNode = m_children[index+1];
			NODE* retNode = NULL;
			while(NULL != curNode) {
				retNode = curNode;
				curNode = curNode->m_children[0];
			}

			return retNode;
		}
	};

	NODE* m_root;
	size_type m_size;
public :
	BTree() : m_root(NULL), m_size(0) {
	}
	iterator begin() {
	}
	iterator end() {
	}     
	size_type size() const {
		return m_size;
	}     
	bool empty() const {
		return (0 == m_size) ? true : false;
	}

	/**
		Inserts x into the map.
	*/
	std::pair<iterator, bool> insert(const value_type& x) {
		if(NULL == m_root) {
			m_root = new NODE;
		}    		
		return insertWithoutOverwrite(m_root, x);
	}
	/**
		Finds an element whose key is k. 
	*/
	iterator find(const key_type& k) {
		std::pair<iterator, bool> ret = find(m_root, k);
		if(true == ret.second) {
			return itr;
		}
		itr.m_pNode = NULL;
		itr.m_index = -1;
		return itr;						 
	}
	void erase(iterator pos) {
		m_size--;
		iterator leafItr;
		leafItr.m_pNode = pos.m_pNode->findSuccessor(pos.m_index);
		if(NULL == leafItr.m_pNode) {	// m_root가 leaf다
			pos.m_pNode->erase(pos.m_index);
			leafItr.m_pNode = pos.m_pNode;
		}
		else { // leaf와 swap 후 
			value_type tmpValue = leafItr.m_pNode->m_values[0];
			leafItr.m_pNode->m_values[0] = pos.m_pNode->m_values[pos.m_index];
			pos.m_pNode->m_values[pos.m_index] = tmpValue;
			leafItr.m_pNode->erase(0);
		}

		while(DEGREE/2 > leafItr.m_pNode->m_count && NULL != leafItr.m_pNode->m_parent) {
			iterator parentItr, sibilingItr;

			findSibilingAndParent(leafItr, sibilingItr, parentItr);
			
			leafItr.m_pNode->insert(parentItr.m_pNode->m_values[parentItr.m_index], leafItr.m_index);
		
			if(DEGREE/2 < sibilingItr.m_pNode->m_count) {
				parentItr.m_pNode->m_values[parentItr.m_index] = sibilingItr.m_pNode->m_values[sibilingItr.m_index];				
				correctChildrenLinks(leafItr, sibilingItr);
				sibilingItr.m_pNode->erase(sibilingItr.m_index);
			}
			else {
				NODE* left = parentItr.m_pNode->m_children[parentItr.m_index];
				NODE* right = parentItr.m_pNode->m_children[parentItr.m_index+1];
		
				/**
					위의 과정에서 insert하면서 뒤로 밀려났던 자식 노드들에 대한 링크를 다시 한칸씩 앞으로..-_-;;
				*/
				if(left == leafItr.m_pNode) {
					for(int i=leafItr.m_index; i<left->m_count; i++) {
						left->m_children[i] = left->m_children[i+1];
						left->m_children[i+1] = NULL;
					}
				}

				leafItr.m_pNode = merge(left, right);

				parentItr.m_pNode->m_children[parentItr.m_index+1] = NULL;
                     				
				parentItr.m_pNode->erase(parentItr.m_index);
				for(int i=parentItr.m_index+1; i<parentItr.m_pNode->m_count+1; ++i) {
					parentItr.m_pNode->m_children[i] = parentItr.m_pNode->m_children[i+1]; 
				}
			}

			if(leafItr.m_pNode->m_parent == m_root && 0 == m_root->m_count) {
				delete leafItr.m_pNode->m_parent;
				leafItr.m_pNode->m_parent = NULL;
				m_root = leafItr.m_pNode;
				break;
			}
          	leafItr.m_pNode = leafItr.m_pNode->m_parent;
		}
	}

	/**
		1. leaf노드이면 그냥 삭제
		2. internal 노드이면 successor를 찾아서 swap 후 삭제
		
		삭제 후 키의 갯수가 모자를 때
		1. 부모에게서 얻어 온다.
		2. 부모에게서 얻어 왔는데 부모가 모자라면 형제의 것을 부모로 올린다.
		3. 형제가 부모로 올릴 형편이 안되는 경우에는 부모의 적절한 키와 두 형제를 합병한다.
	*/
	size_type erase(const key_type& k) {
		if(NULL == m_root) {
			return 0;
		}
		std::pair<iterator, bool> ret = find(m_root, k);
		if(true == ret.second) { // 지울 키가 있다
			erase(ret.first);	
			return 1;
		}
		return false; // fail to remove the key
	}

	void erase(iterator first, iterator last) {
	}						

	void print() {
		retrival(m_root);
	}
	void retrival(NODE* node) {
		if(NULL == node) {
			return;
		}
		std::cout << "[";
		for(int i=0; i<node->m_count; i++) {
			std::cout << node->m_values[i].first << " ";
		}
		std::cout << "]";
		for(int i=0; i<=node->m_count; i++) {
			if(NULL != node->m_children[i]) {
				retrival(node->m_children[i]);
			}
		}
	}
	void correctChildrenLinks(iterator& cur, iterator& sibiling) {
		if(0 == sibiling.m_index) { 
			cur.m_pNode->m_children[cur.m_pNode->m_count] = sibiling.m_pNode->m_children[sibiling.m_index];

			if(NULL != cur.m_pNode->m_children[cur.m_pNode->m_count]) {
				cur.m_pNode->m_children[cur.m_pNode->m_count]->m_parent = cur.m_pNode;
			}	
			for(int i=sibiling.m_index; i<sibiling.m_pNode->m_count; i++) {
				sibiling.m_pNode->m_children[i] = sibiling.m_pNode->m_children[i+1];
			}
		}
		else {
			cur.m_pNode->m_children[cur.m_index] = sibiling.m_pNode->m_children[sibiling.m_index+1];

			if(NULL != cur.m_pNode->m_children[cur.m_index]) {
				cur.m_pNode->m_children[cur.m_index]->m_parent = cur.m_pNode;
			}	
		}
	}
	void findSibilingAndParent(iterator& cur, iterator& sibiling, iterator& parent) {
		parent.m_pNode = cur.m_pNode->m_parent;
		for(int i=0; i<=parent.m_pNode->m_count; ++i) {
			if(parent.m_pNode->m_children[i] == cur.m_pNode) {
				if(i == parent.m_pNode->m_count) {
					parent.m_index = i-1;
					sibiling.m_pNode = parent.m_pNode->m_children[i-1];
					sibiling.m_index = sibiling.m_pNode->m_count-1;
					cur.m_index = 0;
				}
				else {
					parent.m_index = i;
					sibiling.m_pNode = parent.m_pNode->m_children[i+1];
					sibiling.m_index = 0;
					cur.m_index = cur.m_pNode->m_count;
				}
				break;
			}
		}
	}
	/** 
		원하는 키를 찾으면 true와 인덱스, 키가 위치한 노드를 리턴
		키를 찾지 못하면 false와 인서트 되어야 할 노드, 인서트 되어야 하는 인덱스 리턴
	*/
	std::pair<iterator, bool> find(const NODE* pNode, const key_type& key) {
		NODE* pTempNode = const_cast<NODE*>(pNode);
		iterator itr;
		while(NULL != pTempNode) {
			std::pair<int, bool> ret = pTempNode->find(key);
			itr.m_pNode = pTempNode;
			itr.m_index = ret.first;
			if(false == ret.second) {
				pTempNode = pTempNode->m_children[ret.first];
			}
			else {
				return std::make_pair(itr, true);
			}
		}
		return std::make_pair(itr, false);
	}

	/**
		키를 삽입. 만일 키의 중복이 있다면 덮어 쓰지 않고 false를 리턴한다.
	*/
	std::pair<iterator, bool> insertWithoutOverwrite(NODE* pNode, const value_type& x) {
		std::pair<iterator, bool> ret = find(pNode, x.first);
		if(false == ret.second) {
			ret.first.m_pNode->insert(x, ret.first.m_index);
			m_size++;
		}
		else {
			return std::make_pair(ret.first, false);
		}

		if(DEGREE == ret.first.m_pNode->m_count) {
			split(ret.first.m_pNode);
		}
		return std::make_pair(ret.first, true);
	}
	void split(NODE* pNode) {
		NODE* curNode = pNode;

		while(DEGREE == curNode->m_count) {
			NODE* parentNode = NULL;
			if(NULL != curNode->m_parent) {
				parentNode = curNode->m_parent;
			}
			else {
				parentNode = new NODE;
				m_root = parentNode;
				curNode->m_parent = parentNode;
			}

			NODE* sibilingNode = new NODE;
			sibilingNode->m_parent = parentNode;

			std::pair<int, bool> ret = parentNode->find(curNode->m_values[DEGREE/2].first);
			parentNode->insert(curNode->m_values[DEGREE/2], ret.first);

			for(int i=(curNode->m_count/2+1), j=0; i<curNode->m_count; i++, j++) {
				sibilingNode->m_values[j] = curNode->m_values[i];
				sibilingNode->m_children[j] = curNode->m_children[i];
				if(NULL != sibilingNode->m_children[j]) {
					sibilingNode->m_children[j]->m_parent = sibilingNode;
				}
				curNode->m_children[i] = NULL;
			}
			sibilingNode->m_count = curNode->m_count/2;
			sibilingNode->m_children[sibilingNode->m_count] = curNode->m_children[curNode->m_count];
			if(NULL != sibilingNode->m_children[sibilingNode->m_count]) {
				sibilingNode->m_children[sibilingNode->m_count]->m_parent = sibilingNode; 
			}
			curNode->m_children[curNode->m_count] = NULL;

			curNode->m_count = sibilingNode->m_count;

			parentNode->m_children[ret.first] = curNode;
			parentNode->m_children[ret.first+1] = sibilingNode;

			curNode = parentNode;
		}
	}  
	NODE* merge(NODE* left, NODE* right) {
		for(int i=0; i<right->m_count; ++i) {
			left->m_values[left->m_count+i] = right->m_values[i];
		}
		
		for(int i= ((NULL != left->m_children[left->m_count]) ? 1 :0); i<=right->m_count; ++i) {
			left->m_children[left->m_count+i] = right->m_children[i];
			if(NULL != right->m_children[i]) {
				right->m_children[i]->m_parent = left;
			}
		}
		left->m_count += right->m_count;
		delete right;
		return left;
	}

	void clear() {
	}

	data_type& operator[](const key_type& k) {
		NODE* outNode;
		int index;
		if(false == findKeyInNode(m_root, k, &outNode, index)) {
			value_type value;
			value.first = k;
			insert(value);
		}
		
		return outNode->m_values[index];
	}
};