В методе цифры не выводятся на консоль. Ошибки не возникает.
template <typename A, size_t level>
void BTree<A, level>::printTree(Node<A, level>* currentNodeToPrint)
{
////print parent's elements
//for (int u = 0; u < currentNodeToPrint->elements.size(); u++)
//{
// std::cout << currentNodeToPrint->elements[i] << std::endl;
//}
//print child's elments
for (int t = 0; t < currentNodeToPrint->childNodes.size(); t++) {
if (currentNodeToPrint->childNodes[t] != nullptr) {
for (int i = 0; i < currentNodeToPrint->childNodes[1]->elements.size();i++)
{
std::cout << currentNodeToPrint->elements[i] << std::endl;
}
std::cout << " ";
}
}
}
b-tree.cpp
namespace BTrees {
template <class T, size_t level>
struct Node
{
std::vector<Node<T, level>*> childNodes;
std::vector<T> elements;
Node<T, level>* parentNode;
};
// [] [] [] [] []
// / \ \ \ \
//// [] 1 [] 2 [] 3 [] 4 []
// 1 2 4
template <class A, size_t level>
class BTree
{
private:
void InsertNode(A key, Node<A, level>* nodeForInsertion);
Node<A, level>* getNode(A key, Node<A, level>* nodeForSearchIn);
//function for inserting
void SortNodeWithAdding(Node<A, level>* nodeForSorting, A key, bool isAfterSplitting,
Node<A, level>* leftNode = nullptr, Node<A, level>* rightNode = nullptr) {
size_t indexOfNewNodeForSorting = -1;
size_t indexOfelement = -1;
bool isSorted = false;
if (nodeForSorting->elements.size() > 0) {
if (nodeForSorting->elements[0] > key)
{
isSorted = true;
nodeForSorting->elements.insert(nodeForSorting->elements.begin(), key);
//indexOfNewNodeForSorting = 0;
indexOfelement = 0;
}
else if (nodeForSorting->elements[nodeForSorting->elements.size() - 1] < key)
{
isSorted = true;
nodeForSorting->elements.insert(nodeForSorting->elements.begin() + nodeForSorting->elements.size(), key);
//indexOfNewNodeForSorting = nodeForSorting->elements.size();
indexOfelement = nodeForSorting->elements.size() - 1;
}
if (!isSorted) {
for (int i = 1;i < nodeForSorting->elements.size(); i++)
{
if (nodeForSorting->elements[i] > key && nodeForSorting->elements[i - 1] < key)
{
nodeForSorting->elements.insert(nodeForSorting->elements.begin() + i, key);
//indexOfNewNodeForSorting = i + 1;
indexOfelement = i;
break;
}
}
}
if (nodeForSorting->childNodes[indexOfelement] != nullptr)
{
if (nodeForSorting->childNodes[indexOfelement]->elements[0] > key)
{
nodeForSorting->childNodes.insert(nodeForSorting->childNodes.begin() + indexOfelement - 1, nullptr);
}
else
{
nodeForSorting->childNodes.insert(nodeForSorting->childNodes.begin() + indexOfelement, nullptr);
}
}
else
{
nodeForSorting->childNodes.insert(nodeForSorting->childNodes.begin() + indexOfelement, nullptr);
}
if (isAfterSplitting)
{
nodeForSorting->childNodes[indexOfelement] = leftNode;
nodeForSorting->childNodes[indexOfelement + 1] = rightNode;
}
}
else
{
nodeForSorting->childNodes.push_back(leftNode);
nodeForSorting->childNodes.push_back(rightNode);
nodeForSorting->elements.push_back(key);
}
}
//
//
//Some variable
size_t l = level;
Node<A, level>* root;
public:
BTree() {
root = new Node<A, level>;
root->parentNode = nullptr;
};
~BTree() { delete root; };
void printTree(Node<A, level>* root);
void Add(A key);
Node<A, level>* getRoot()
{
return root;
};
};
template <typename A, size_t level>
void BTree<A, level>::printTree(Node<A, level>* currentNodeToPrint)
{
////print parent's elements
//for (int u = 0; u < currentNodeToPrint->elements.size(); u++)
//{
// std::cout << currentNodeToPrint->elements[i] << std::endl;
//}
//print child's elments
for (int t = 0; t < currentNodeToPrint->childNodes.size(); t++) {
if (currentNodeToPrint->childNodes[t] != nullptr) {
for (int i = 0; i < currentNodeToPrint->childNodes[1]->elements.size();i++)
{
std::cout << currentNodeToPrint->elements[i] << std::endl;
}
std::cout << " ";
}
}
}
template <typename A, size_t level>
Node<A, level>* BTree<A, level>::getNode(A key, Node<A, level>* nodeForSearchIn)
{
Node<A, level>* currentNodeForSearch = nodeForSearchIn;
bool nodeIsFound = false;
size_t indexOfNextNodeForSearch = -1;
//here
if (currentNodeForSearch->elements.size() > 0) {
while (!nodeIsFound && currentNodeForSearch->elements.size() > 0)
{
//check if node for new element is current and
if (currentNodeForSearch->elements[0] > key) {
if (currentNodeForSearch->childNodes[0] == nullptr)
{
nodeIsFound = true;
}
else
{
indexOfNextNodeForSearch = 0;
}
}
if (currentNodeForSearch->elements[currentNodeForSearch->elements.size() - 1] < key) {
if (currentNodeForSearch->childNodes[currentNodeForSearch->elements.size()] == nullptr)
{
nodeIsFound = true;
}
else
{
indexOfNextNodeForSearch = currentNodeForSearch->elements.size();
}
}
if (!nodeIsFound) {
for (int i = 1; i < currentNodeForSearch->elements.size(); i++)
{
if (currentNodeForSearch->elements[i] > key && currentNodeForSearch->elements[i - 1] < key) {
if (currentNodeForSearch->childNodes[i] == nullptr)
{
nodeIsFound = true;
break;
}
else
{
indexOfNextNodeForSearch = i;
break;
}
}
}
}
//come to nextNode for searching
if (!nodeIsFound)
{
currentNodeForSearch = currentNodeForSearch->childNodes[indexOfNextNodeForSearch];
}
}
}
return currentNodeForSearch;
}
template <typename A, size_t level>
void BTree<A, level>::InsertNode(A key, Node<A, level>* nodeForInsertion)
{
Node<A, level>* splittedNode = nullptr;
Node<A, level>* currentNodeForInsertion = nodeForInsertion;
size_t indexOfSplittedElement = 0;
Node<A, level>* leftNodeOfSplittedElement = nullptr;
Node<A, level>* rightNodeOfSplittedElement = nullptr;
while (currentNodeForInsertion->elements.size() >= level - 1)
{
splittedNode = currentNodeForInsertion;
indexOfSplittedElement = currentNodeForInsertion->elements.size() / 2;
leftNodeOfSplittedElement = new Node<A, level>;
rightNodeOfSplittedElement = new Node<A, level>;
if (currentNodeForInsertion->parentNode == nullptr)
{
root = new Node<A, level>;
root->parentNode = nullptr;
leftNodeOfSplittedElement->parentNode = root;
rightNodeOfSplittedElement->parentNode = root;
}
else
{
leftNodeOfSplittedElement->parentNode = currentNodeForInsertion->parentNode;
rightNodeOfSplittedElement->parentNode = currentNodeForInsertion->parentNode;
}
//LEFT <---------------------
//Insert of elements
for (int i = 0; i < indexOfSplittedElement; i++)
{
//leftNodeOfSplittedElement->elements.push_back(currentNodeForInsertion->elements[i]);
SortNodeWithAdding(leftNodeOfSplittedElement, currentNodeForInsertion->elements[i],
true, currentNodeForInsertion->childNodes[i], currentNodeForInsertion->childNodes[i + 1]);
}
for (int i = 0; i < leftNodeOfSplittedElement->childNodes.size(); i++)
{
if (leftNodeOfSplittedElement->childNodes[i] != nullptr)
{
leftNodeOfSplittedElement->childNodes[i]->parentNode = leftNodeOfSplittedElement;
}
}
//RIGHT <---------------------
//Insert of elements
for (int i = indexOfSplittedElement + 1; i < currentNodeForInsertion->elements.size(); i++)
{
SortNodeWithAdding(rightNodeOfSplittedElement, currentNodeForInsertion->elements[i],
true, currentNodeForInsertion->childNodes[i], currentNodeForInsertion->childNodes[i + 1]);
}
for (int i = 0; i < rightNodeOfSplittedElement->childNodes.size(); i++)
{
if (rightNodeOfSplittedElement->childNodes[i] != nullptr)
{
rightNodeOfSplittedElement->childNodes[i]->parentNode = rightNodeOfSplittedElement;
}
}
if (currentNodeForInsertion->parentNode == nullptr) {
SortNodeWithAdding(
root, currentNodeForInsertion->elements[indexOfSplittedElement], true,
leftNodeOfSplittedElement, rightNodeOfSplittedElement);
delete splittedNode;
break;
}
else
{
SortNodeWithAdding(
currentNodeForInsertion->parentNode, currentNodeForInsertion->elements[indexOfSplittedElement], true,
leftNodeOfSplittedElement, rightNodeOfSplittedElement);
if (currentNodeForInsertion->parentNode->childNodes.size() >= level)
{
currentNodeForInsertion = currentNodeForInsertion->parentNode;
delete splittedNode;
}
else
{
delete splittedNode;
break;
}
}
}
currentNodeForInsertion = getNode(key, root);
SortNodeWithAdding(currentNodeForInsertion, key, false);
}
template <typename A, size_t level>
void BTree<A, level>::Add(A key)
{
Node<A, level>* nodeForNewElement = getNode(key, root);
InsertNode(key, nodeForNewElement);
}
}
main()
BTrees:BTree<int, 6> tree;
for (int i = 0; i < 100; i++)
{
tree.Add(i);
}
tree.printTree(tree.getRoot());
