Корневой узел равен null после вставки нового узла в AVLTree

Question

Итак, в simpletons я создаю свою собственную структуру данных AVLTree. Теперь, когда я добавляю новый узел в свое дерево, он, кажется, добавляет штраф.

РЕДАКТИРОВАТЬ: Он, похоже, не учитывает мои дубликаты (и не добавляет их в список первоначального узла по ключу).

Но когда я печатаю rootNode, чтобы увидеть, существует ли он, его не существует. Я не могу понять, в чем проблема с моим методом добавления.

Вот мой 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

Но вы не использовать возвращаемый узел.

Edit: длинное описание:

При вызове из другой функции, как это: 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);

Это значение для node переменной в методе insert(K,V,N), ни в коей мере не является rootNode задним числом обновляется. Вы можете просто сделать это прямо здесь:

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