java - 将新节点插入 AVLTree 后根节点为空

Question

简单来说，我正在创建自己的 AVLTree 数据结构。现在，当我在树中添加一个新节点时，它似乎添加得很好。

编辑:它似乎没有考虑我的重复项(也没有通过键将它们添加到原始节点的列表中)。

但是当我打印 rootNode 以查看它是否存在时，它不存在。我无法弄清楚我的 add 方法有什么问题。

这是我的 AVLTree 类:

package cw.util;

import java.util.ArrayList;
import java.util.Comparator;

public class AVLTree<K, V>
{
    public class Node {
        private K key;
        private ArrayList<V> valuesList;
        private Node left, right;
        private int height;

        public Node(K key, ArrayList<V> valuesList) {
            this.key = key;
            this.valuesList = valuesList;
            this.height = 0;
        }

        public Node(V value) {
        }

        public void addToNode(V value) {
            valuesList.add(value);
        }

        public K getKey() {
            return key;
        }

        public ArrayList<V> getValues() {
            return valuesList;
        }

        public Node getLeftChild() {
            return left;
        }
        public Node getRightChild() {
            return right;
        }

        public int getHeight() {
            return height;
        }

        public Node getChildNodeFromSide(String side) {
            switch(side) {
                default: return null;
                case "left": return left;
                case "right": return right;
            }
        }
    }

    private Node rootNode;
    private Comparator<K> comparator;

    //Unused
    public AVLTree() {
    }

    public AVLTree(Comparator<K> comparator) {
        this.comparator = comparator;
        this.rootNode = null;
    }

    public V insert(K key, V value) {
        Node n = insert(key, value, rootNode);

        if(n != null) {
            for(V v : n.getValues())
                System.out.println(v.toString());
            System.out.println();
            return value;
        } else {
            return null;
        }
    }

    public Node insert(K key, V value, Node node) {
        ArrayList<V> values = new ArrayList<V>();
        values.add(value);

        if(node == null)
            node = new Node(key, values);
        else if(comparator.compare(key, node.key) < 0) {
            node.left = insert(key, value, node.left);

            if(height(node.left) - height(node.right) == 2) {
                if(comparator.compare(key, node.left.key) < 0)
                    node = rotateWithLeftChild(node);
                else
                    node = doubleRotateWithLeft(node);
            }

        } else if(comparator.compare(key, node.key) > 0) {
            node.right = insert(key, value, node.right);

            if(height(node.right) - height(node.left) == 2) {
                if(comparator.compare(key, node.right.key) > 0)
                    node = rotateWithRightChild(node);
                else
                    node = doubleRotateWithRight(node);
            }
        } else node.getValues().add(value);

        node.height = Math.max(height(node.left), height(node.right)) + 1;

        return node;
    }

    public Node search(K key) {
        return search(key, rootNode);
    }

    public Node search(K key, Node node) {
        boolean isFound = false;

        while((node != null) && !isFound) {
            K nodeKey = node.getKey();
            if(comparator.compare(key, nodeKey) < 0)
                node = node.getLeftChild();
            else if(comparator.compare(key, nodeKey) > 0)
                node = node.getRightChild();
            else {
                isFound = true;
            }
            node = search(key, node);
        }
        if(isFound) return node;
        else return null;
    }

    //Custom Methods
    public boolean isEmpty() {
        return rootNode == null;
    }
    private int height(Node n) {
        return n == null ? -1 : n.getHeight();
    }

    private Node rotateWithLeftChild(Node node2) {
        Node node1 = node2.left;
        node2.left = node1.right;
        node1.right = node2;

        node2.height = Math.max(height(node2.left), height(node2.right)) + 1;
        node1.height = Math.max(height(node1.left), node2.getHeight()) + 1;

        return node1;
    }
    private Node rotateWithRightChild(Node node1) {
        Node node2 = node1.right;
        node1.right = node2.left;
        node2.left = node1;

        node1.height = Math.max(height(node1.left), height(node1.right)) + 1;
        node2.height = Math.max(height(node2.left), node1.getHeight()) + 1;

        return node2;
    }
    private Node doubleRotateWithLeft(Node node) {
        node.left = rotateWithRightChild(node.left);
        return rotateWithLeftChild(node);
    }
    private Node doubleRotateWithRight(Node node) {
        node.right = rotateWithLeftChild(node.right);
        return rotateWithRightChild(node);
    }
}

这是我测试类(class)的方法:

package cw.avl;

import cw.util.AVLTree;

public class AVLTest
{
    public static void main(String[] args) {
        AVLTree<String, Integer> tree = new AVLTree<String, Integer>(String.CASE_INSENSITIVE_ORDER);

        for (int i=1; i <= 10;i++) {
            String s = "S" + i;
            int x = i;
            tree.insert(s, x);
            tree.insert(s, x);
        }
    }
}

Answer 1

嗯，您似乎从未分配过 rootNode，因此它以 null 开头并保持不变。事实上，您的方法创建节点并返回它们:

if(节点==空) 节点=新节点(键，值)； ... 返回节点

但是您不使用返回的节点。

编辑:更长的解释:

当您从像这样的其他函数调用时:Node n = insert(key, value, rootNode);您基本上是在说:Node n = insert(key, value, null) )；。在接收端，这里:

public Node insert(K key, V value, Node 节点) { ,

您正在创建一个名为 node 的新变量，其初始值为 null。然后，您可以在执行以下操作时替换该值:

node = new Node(key, value);

该值适用于 insert(K,V,N) 方法中的 node 变量，rootNode 绝不会追溯更新。您可以直接这样做:

如果(节点==空){ 节点=新节点(键，值)； 根节点=节点； }