2015-10-19 74 views
1

所以在simpletons中,我創建了自己的AVLTree數據結構。現在,當我將一個新節點添加到我的樹中時,它似乎很好。將新節點插入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); 
     } 
    } 
} 
+0

沒有重複,我覺得海報不知道是什麼問題,但是,是的,的確,它是:-) –

回答

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; }

+0

看一看的情況下,在另一個使用該插入方法的插入方法 – madcrazydrumma

+0

@madcrazydrumma在'insert'中指定'node'不會爲'rootNode'分配任何東西。對於對象,Java不是「通過引用傳遞」,而是「通過引用的值傳遞」(https://stackoverflow.com/q/40480)。 – Siguza

+0

@Siguza我讀過你說的是'重複'的問題。那麼如果java不是通過引用傳遞的話,我將如何去解決這個問題呢?我將如何解決這個問題? – madcrazydrumma