스플레이 트리 검색 구현

Question

저는 일부 데이터 구조에 대해 자세히 배우려고 노력했으며 제대로 작동하려면 이진 스플레이 트리를 얻으려고합니다. 다음 코드를 실행할 때마다 내가 찾고있는 노드가 과거의 루트보다 두 개 이상 많다는 것을 알려주고 루트에서 전체면을 삭제합니다. 노드가 맨 위에서 한 레벨 아래에 있으면 잘 작동합니다.

나는 무엇이 잘못 될지 모르지만 내 회전 기능과 관련이 있다고 가정합니다. 나는 이것을 내가 모델링 한 인서트 함수에 대해 제대로 작동하도록했다.

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

Answer 1

귀하의 문제는 당신이 회전 할 때, 당신은 기능 "SplaySearch"에서 H 노드에 대한 참조를 업데이트하지만, 원래 "searchIt"기능의 부모 노드를 업데이트하지 않는 것입니다. 따라서 프로그램은 회전 된 노드가 부모 여야한다고하더라도 원래 부모 노드가 부모로 남아 있다고 생각합니다. 따라서 나무를 인쇄 할 때 사용하는 메서드를 실행하면 실제로 나무의 부모 노드가 아닌 노드에서 인쇄되지만 자식은 프로그램에서 rotateLeft 및 rotateRight라는 프로그램의 횟수에 따라 다릅니다.).

이 문제를 해결하려면 일반 이진 트리 에서처럼 검색을 구현 ​​한 다음 트리 상단에 노드를 표시하는 검색 기능과 완전히 별개의 "splay"기능을 만들어야합니다. 모든 검색이 끝날 때이 Splay 함수를 호출하여 참조를 올바르게 업데이트해야합니다. 이것은 스플래쉬 트리를 구현하는 전통적인 방법이며, 스플레이 트리에 관한 위키 백과 문서를 보거나 Google 검색을 수행하는 것이 좋습니다. 또한 회전 기능이 완전하지 않다는 것을 알고 싶을 수도 있습니다. 분출 나무의 관점에서, 당신은 또한 단일 회전과 매우 다른 두 가지 유형의 이중 회전을 가지고 있습니다. 다시 한 번, 나는 그들에 대해 더 깊이 알기 위해 분출 나무를 찾는 것이 좋습니다.

Answer 2

두 번째로 Tristan Hull이 "작동하는"검색 방법을 사용하여 정규 BST를 만드는 방법을 설명합니다. 일단 작동 시키면, splay 메소드를 추가하는 것이 사소한 일입니다. Splay Tree in Java을 구현할 때 실제로 동일한 작업을 수행했습니다. 그것은 더 나은 소프트웨어 설계와 간단한 구현입니다.