Splay樹搜索實現

我一直在嘗試學習一些數據結構的來龍去脈，我試圖讓一個二進制splay樹正常工作。每次運行下面的代碼時，我所尋找的節點都超過了根節點，它告訴我它在那裏，然後從根節點刪除整個一面。如果節點只從頂部向下一級，它會正常工作。Splay樹搜索實現

我不確定發生了什麼問題，但我想它與我的旋轉功能有關。我已經正確地爲插入功能正常工作，這是我之後建模的功能。

public class SplayBST { 
    Node root; 
    int count; 
    int level = 0; 
    boolean found = false; 
    public SplayBST() { 
     root = null; 
     count = 0; 
    } 

public String searchIt(String x) { 
    //after finishing search method I need to check if splaySearch exists then don't insert just splay it 
    splaySearch(root, x); 
    if (this.found == true) { 
     this.found = false; 
     return x; 
    } 
    else { 
     return null; 
    } 
} 


    Node splaySearch(Node h, String x) { 
     if (h == null) { 
      return null; 
     } 
     if (x.compareTo(h.value) < 0) { 
      try { 
      if (x.compareTo(h.left.value) < 0) { 
       h.left.left = splaySearch(h.left.left, x); 
       h = rotateRight(h); 
      } else if (x.compareTo(h.left.value) > 0) { 
       h.left.right = splaySearch(h.left.right, x); 
       h.left = rotateLeft(h.left); 
      } 
      else { 
       this.found = true; 
       return h.left; 
      } 
      return rotateRight(h); 
      } 
     catch (NullPointerException ex) { 
      return null; 
      } 
     } 

     else { //basically x.compareTo(h.value)>0 
      try { 
      if (x.compareTo(h.right.value) > 0) { 
       h.right.right = splaySearch(h.right.right, x);     
       h = rotateLeft(h); 
      } else if (x.compareTo(h.right.value) < 0) { 
       h.right.left = splaySearch(h.right.left, x); 
       h.right = rotateRight(h.right); 
      } 
      else { 
       this.found = true; 
       return h.right; 
      } 
      return rotateLeft(h); 
      } 
      catch (NullPointerException ex) { 
       return null; 
      } 
     } 
    } 


    Node rotateLeft(Node h) { 
     Node x = h.right; 
     h.right = x.left; 
     x.left = h; 
     return x; 
    } 
    Node rotateRight(Node h) { 
     Node x = h.left; 
     h.left = x.right; 
     x.right = h; 
     return x; 
    } 


    class Node { 
     Node left; 
     Node right; 
     String value; 
     int pos; 
     public Node(String x) { 
      left = null; 
      right = null; 
      value = x; 
     } 
    } 
}

來源

2012-10-08 clifgray

你的問題是，當你旋轉，您更新功能「SplaySearch」到節點H的參考，但你不更新在原有的「searchIt」功能的父節點。因此，即使旋轉的節點應該是父節點，程序「認爲」原始父節點仍然是父節點。因此，當你運行你用來打印你的樹的任何方法時，你從一個實際上不是樹的父節點的節點打印，但是一個孩子（它所在的級別取決於你的程序調用了多少次rotateLeft和rotateRight ）。

爲了解決這個問題，我建議在普通二叉樹中實現搜索，然後將「splay」函數與將樹節點放到樹頂部的搜索函數完全分開。您可以在每次搜索結束時調用此splay功能，確保正確更新您的參考。這是實現樹狀結構樹的傳統方法，我建議你看看它（也許看一下關於splay樹的維基百科文章或者Google搜索）。此外，你可能想知道你的旋轉功能不完整。在斜紋樹方面，你也有兩種不同的單旋轉雙重旋轉類型。同樣，我建議查找一些展開樹來深入瞭解它們。

來源

2012-10-08 23:05:26

好的謝謝你的幫助 – clifgray

謝謝你嘗試我的方法。你有沒有得到它的工作？ –

哈哈我仍然在努力，我會想象它會需要一段時間 – clifgray

我第二次特里斯坦赫爾的方法來創建一個「工作」搜索方法的常規BST。一旦你得到這個工作，添加一個splay方法是相當微不足道的。我實際上做了同樣的事情，當我實施Splay Tree in Java。這是一個更好的軟件設計和更簡單的實現。

來源

2012-10-09 00:00:59 Justin

Splay樹搜索實現

回答

相關問題