我接到了一项任务,要创建一个 2-3 搜索树,该树应该支持几个不同的操作,每个操作都分为任务的不同阶段。 对于第 1 阶段,我应该支持操作 get、put 和 size。我目前正在尝试实现 get 操作,但我被卡住了,我无法全神贯注地思考如何继续,所以我质疑我编写的所有代码,并觉得需要其他人的输入。
我查看了如何开发一个 2-3 搜索树,但我发现有很多代码对我来说毫无意义,或者它只是没有做我需要它做的事情,我想尝试做这是我自己从头开始的,我们现在就在这里。
我的节点类
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[]
绑定(bind)到每个键,但我想不出具体方法。可能是 sleep 不足,或者我被这种思维方式所困。
最佳答案
bind values[] to each key
使用 HashMap
可能更有意义为你做那个映射,因为这就是它的目的。除此之外,如果您有两个键并且每个键有两个值,那么您有 4 个值,而不是 2 个 ;)
一般来说,树结构中的get方法几乎都是可以递归实现的。这是伪代码中 2-3 树的 get
算法的非常通用的实现。
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
.
关于java - 用java开发一个2-3搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26262279/