알고리즘...63

B 트리 검색 구현

다진 검색 트리인 B 트리의 검색을 구현한다.

 

BTree::Exists

/// <summary>
/// B 트리를 확인하여 주어진 값이 트리에 존재하는지 여부를 반환한다.
/// </summary>
/// <param name="data">확인할 값</param>
/// <returns>존재 여부</returns>
bool BTree::Exists(int data)
{
	BTreeNode* node{ _root };
	while (node != nullptr)
	{
		for (int i = 0; i < BTreeNode::TotalKeyCount; i++)
		{
			if (node->keys[i].value == data)
			{
				return true;
			}

			if (data < node->keys[i].value)
			{
				node = node->keys[i].left;
				break;
			}

			if (node->keys[i].value < data)
			{
				int nextKeyIdx{ i + 1 };
				if (nextKeyIdx < BTreeNode::TotalKeyCount && node->keys[i + 1].isSet)
				{
					if (data < node->keys[i + 1].value)
					{
						node = node->keys[i].right;
						break;
					}
				}
				else
				{
					node = node->keys[i].right;
					break;
				}
			}
		}
	}
	
	return false;
}