Разработать 2-3 дерева поиска в Java
Мне было дано задание на создание 2-3 дерева поиска, которое должно поддерживать несколько разных операций, каждая из которых разделена на разные стадии задания. На первом этапе я должен поддержать операции get, put и size. Я сейчас пытаюсь реализовать операцию get, но я застрял и не могу обдумать, как продолжить, поэтому я подвергаю сомнению весь мой код, который написал, и чувствовал, что кто-то еще вводит.
Я посмотрел вокруг, как разработать 2-3 дерева поиска, но я нашел много кода, который не имел никакого смысла для меня, или он просто не делал то, что мне было нужно, и я хотел попытаться сделать это для своего Я с нуля и вот мы здесь.
Мой класс Node
package kth.id2010.lab.lab04;
public class Node {
boolean isLeaf = false;
int numberOfKeys;
String[] keys = new String[2]; //each node can contain up to 2 keys
int[] values = new int[2]; //every key contains 2 values
Node[] subtrees = new Node[3]; //every node can contain pointers to 3 different nodes
Node(Node n) {
n.numberOfKeys = 0;
n.isLeaf = true;
}
}
Мой класс создания дерева
package kth.id2010.lab.lab04;
public class Tree {
Node root; // root node of the tree
int n; // number of elements in the tree
private Tree(){
root = new Node(root);
n = 0;
}
//Return the values of the key if we find it
public int[] get(String key){
//if the root has no subtrees check if it contain the right key
if(this.root.subtrees.length == 0){
if(this.root.keys[0] == key){
return(this.root.keys[0].values);
}
else if(this.root.keys[1] == key){
return(this.root.keys[1].values);
}
}
//if noot in root, check its subtree nodes
//and here I can't get my head around how to traverse down the tree
else{
for(int i = 0; i < this.root.subtrees.length; i++){
for(int j = 0; j < this.root.subtrees[i].keys.length; j++){
if(this.root.subtrees[i].keys[j] == key){
return(this.root.subtrees[i].keys[j].values);
}
}
}
}
return null;
}
}
Что я могу сказать для себя, так это то, что мне нужно найти способ связать values[]
к каждому ключу, но я не могу понять, как это сделать. Это может быть недостаток сна или то, что я застрял в этом образе мышления.
1 ответ
привязать значения [] к каждому ключу
Возможно, имеет смысл использовать HashMap
сделать это отображение для вас, так как это то, для чего оно. Кроме того, если у вас есть два ключа и каждый ключ имеет два значения, у вас есть 4 значения, а не 2;)
В общем случае метод get в древовидной структуре почти всегда реализуем рекурсивно. Вот очень общая реализация get
алгоритм для 2-3 дерева в псевдокоде.
V get<K, V>(Node<K, V> node, K key)
{
if(node.is_leaf())
{
return node.keys.get(key); // This will either return the value, or null if the key isn't in the leaf and thus not in the tree
}
if(key < node.left_key)
{
return get(node.left_child, key); // If our key goes to the left, go left recursively
}
else if(node.two_node && key <= node.right_key)
{
return get(node.center_child, key) // If we have two keys, and we're less than the second one, we go down the center recursively
}
else
{
return get(node.right_child, key); // If we've gotten here, we know we're going right, go down that path recursively
}
}
Это должно привести вас в правильном направлении. Вставка / удаление для 2-3 деревьев немного сложнее, но это должно, по крайней мере, понять, как об этом думать. Подсказка; Ваш Node
класс должен быть двусвязным, то есть каждый узел / лист должен ссылаться на свой родительский узел, а также на его дочерние элементы, а корень - это просто узел, чей родитель null
,