Помогите пожалуйста завершить внедрение b-tree. Я сделал дерево, но я не уверен, что оно работает правильно. И я тоже не понимаю, как выполнить балансировку и удаление элемента (с последующей ребалансировкой). Ниже приведен код.
Я не нашел много источников, где можно прочитать о реализации b-tree, поэтому я запутался в этом вопросе и не до конца понимаю, как выполняется балансировка, поиск элементов и их удаление. .
Скажите, пожалуйста, как правильно сбалансировать, найти элемент и удалить элемент в этом дереве. Было бы здорово, если бы вы предоставили код.
``` class BTree
{
private BtreeNode root;
private int T; //2T is the maximum number of childen a node can have
private int height;
public BTree(int t)
{
root = new BtreeNode(t);
T = t;
height = 0;
}
public void printHeight()
{
Console.WriteLine("Tree height is " + height);
}
public void insert(int newKey)
{
if (root.isFull())
{//Split root;
split();
height++;
}
root.insert(newKey);
}
public void print()
{
// Wrapper for node print method
// root.print();
}
public void printNodes()
{
// Wrapper for node print method
//root.printNodes();
}
public void split()
{
// Splits the root into three nodes.
// The median element becomes the only element in the root
// The left subtree contains the elements that are less than the median
// The right subtree contains the elements that are larger than the median
// The height of the tree is increased by one
//Console.WriteLine("Before splitting root");
//root.printNodes(); // Code used for debugging
BtreeNode leftChild = new BtreeNode(T);
BtreeNode rightChild = new BtreeNode(T);
leftChild.isLeaf = root.isLeaf;
rightChild.isLeaf = root.isLeaf;
leftChild.n = T - 1;
rightChild.n = T - 1;
int median = T - 1;
for (int i = 0; i < T - 1; i++)
{
leftChild.children[i] = root.children[i];
leftChild.key[i] = root.key[i];
}
leftChild.children[median] = root.children[median];
for (int i = median + 1; i < root.n; i++)
{
rightChild.children[i - median - 1] = root.children[i];
rightChild.key[i - median - 1] = root.key[i];
}
rightChild.children[median] = root.children[root.n];
root.key[0] = root.key[median];
root.n = 1;
root.children[0] = leftChild;
root.children[1] = rightChild;
root.isLeaf = false;
Console.WriteLine("After splitting root");
root.printNodes();
}
}
class BtreeNode
{
public BtreeNode[] children; // The child nodes
public int n;
private int T; // The Minimum Degree of the tree
public bool isLeaf { get; set; } // Is the current node a leaf or not?
public int[] key; // The list of keys
public BtreeNode(int t)
{
T = t;
isLeaf = true;
key = new int[2 * T - 1];
children = new BtreeNode[2 * T];
n = 0;
}
public Boolean isFull()
{
return n == (2 * T - 1);
}
public void insert(int newKey)
{
// Insert new key to current node
// We make sure that the current node is not full by checking and
// splitting if necessary before descending to node
//System.out.println("inserting " + newKey); // Debugging code
int i = n - 1;
if (isLeaf)
{
while ((i >= 0) && (newKey < key[i]))
{
key[i + 1] = key[i];
i--;
}
n++;
key[i + 1] = newKey;
}
else
{
while ((i >= 0) && (newKey < key[i]))
{
i--;
}
int insertChild = i + 1; // Subtree where new key must be inserted
if (children[insertChild].isFull())
{
// The root of the subtree where new key will be inserted has to be split
// We promote the mediand of that root to the current node and
// update keys and references accordingly
//System.out.println("This is the full node we're going to break ");
// Debugging code
//c[insertChild].printNodes();
Console.WriteLine("going to promote " + children[insertChild].key[T-1]);
n++;
children[n] = children[n - 1];
for (int j = n - 1; j > insertChild; j--)
{
children[j] = children[j - 1];
key[j] = key[j - 1];
}
key[insertChild] = children[insertChild].key[T - 1];
children[insertChild].n = T - 1;
BtreeNode newNode = new BtreeNode(T);
for (int k = 0; k < T - 1; k++)
{
newNode.children[k] = children[insertChild].children[k + T];
newNode.key[k] = children[insertChild].key[k + T];
}
newNode.children[T - 1] = children[insertChild].children[2 * T - 1];
newNode.n = T - 1;
newNode.isLeaf = children[insertChild].isLeaf;
children[insertChild + 1] = newNode;
Console.WriteLine("This is the left side ");
children[insertChild].printNodes();
Console.WriteLine("This is the right side ");
children[insertChild+1].printNodes();
children[insertChild+1].printNodes();
if (newKey < key[insertChild])
{
children[insertChild].insert(newKey);
}
else
{
children[insertChild + 1].insert(newKey);
}
}
else
children[insertChild].insert(newKey);
}
}
class Program
{
static void Main(string[] args)
{
Random rand = new Random();
BTree T = new BTree(3);
int INSERTS = 1000; // how many elements are inserted
int VALUE_LIMIT = 10000; // generated integers up to VALUE_LIMIT
int[] values = new int[INSERTS]; // array can be used to print insert order
// or to test other methods
for (int i = 0; i < INSERTS; i++)
{
int val = rand.Next(VALUE_LIMIT);
values[i] = val;
T.insert(val);
}
//T.printNodes();
T.printHeight();
}
}