java - 用java开发一个2-3搜索树

Question

我接到了一项任务，要创建一个 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 不足，或者我被这种思维方式所困。

Answer 1

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.