将新节点插入AVLTree后，根节点为空

Question

所以在simpletons中，我创建了自己的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); 
    } 
} 

这里是我测试类：

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 == null) node = new Node(key, values); ... return node

但你不使用返回的节点。

编辑：更详细的解释：

当你从这样的其他功能拨打电话：Node n = insert(key, value, rootNode);你基本上是说：Node n = insert(key, value, null);。在接收端，在这里：

public Node insert(K key, V value, Node node) {，

要创建一个名为node与初始值null新的变量。然后你替换该值，当你这样做：

node = new Node(key, values);

该值在insert(K,V,N)方法node变量，绝不是rootNode追溯更新。你可能只是这样做的权利有：

if(node == null) { node = new Node(key, values); rootNode = node; }