Java - 균형 잡힌 BinarySearchTree를위한 JUnit 테스트

Question

저는 작동하는 Binary Search Tree를 작성했으며 함께 진행할 JUnit 테스트를 구성하려고합니다. 나는 최대 값 (InOrder traversal)을 발견하기위한 하나,이 최대 값을 제거하기위한 하나, 이진 트리가 균형을 잡았는지 확인하기 위해 하나를 세 가지로 연구 중이다. 나는 처음 두 글을 썼지 만, 마지막 테스트를 어떻게 할 것인가를 알아낼 수는 없다. 내가 뭔가를 간과 한 것 같은 느낌이들 때, 나는 약간의 지침에 감사 할 것입니다.

내 시험 방법 :

public class BSTreePreLabTest { 
@Test 
public void testFindMax() { 
    BSTree<Integer> tree = new BSTree<Integer>(); 
    tree.addElement(15); 
    tree.addElement(16); 
    tree.addElement(17); 
    tree.addElement(18); 
    tree.addElement(19); 
    tree.addElement(20);  
    assertEquals("20", tree.findMax().toString()); 
} 


@Test 
public void testRemoveMax() { 
    BSTree<Integer> tree = new BSTree<Integer>(); 
    tree.addElement(15); 
    tree.addElement(16); 
    tree.addElement(17); 
    tree.addElement(18); 
    tree.addElement(19); 
    tree.addElement(20);  
    tree.removeMax(); 
    assertEquals("Inorder traversal: [15, 16, 17, 18, 19]", tree.toString()); 
} 

그리고 참조 내 주요 BinarySearchTree 방법, 필요한 경우 : 당신은 왼쪽과 오른쪽 하위 트리의 높이를 찾는 함수를 작성할 수 있습니다

public class BSTree<T> { 

private BSTreeNode<T> root = null; 
private int count; 

public BSTree(T element) { 
    root = new BSTreeNode<T>(element); 
    count = 1; 
} 

public BSTree() { 
    root = null; 
    count = 0; 
} 

public void addElement(T element) { 
    if (isEmpty()) { 
     root = new BSTreeNode<T>(element); 
    } 
    else { 
     BSTreeNode<T> current = root; 
     BSTreeNode<T> previous = null; 
     Comparable<T> comparableElement = (Comparable<T>) element; 
     while (current != null) { 
      if (comparableElement.compareTo(current.getElement()) < 0) { 
       previous = current; 
       current = current.getLeft(); 
      } 
      else { 
       previous = current; 
       current = current.getRight(); 
      } 
     } 
     BSTreeNode<T> newNode = new BSTreeNode<T>(element); 
     if (comparableElement.compareTo(previous.getElement()) < 0) 
      previous.setLeft(newNode);   
     else 
      previous.setRight(newNode); 
    } 
    count++; 
} 

public boolean isEmpty() { 
    return root == null; 
} 

public int size() { 
    return count; 
} 

public T find(T targetElement) throws ElementNotFoundException { 
    BSTreeNode<T> current = findNode(targetElement, root); 

    if (current == null) 
     throw new ElementNotFoundException("BSTree"); 

    return (current.getElement()); 
} 

private BSTreeNode<T> findNode(T targetElement, BSTreeNode<T> next) { 
    if (next == null) 
     return null; 

    if (next.getElement().equals(targetElement)) 
     return next; 

    BSTreeNode<T> temp = findNode(targetElement, next.getLeft()); 

    if (temp == null) 
     temp = findNode(targetElement, next.getRight()); 

    return temp; 
} 

public T removeElement(T targetElement) throws ElementNotFoundException { 
    T result = null; 

    if (isEmpty()) 
     throw new ElementNotFoundException("BSTree"); 
    else { 
     BSTreeNode<T> parent = null; 
     if (((Comparable<T>) targetElement).equals(root.getElement())) { 
      result = root.getElement(); 
      BSTreeNode<T> temp = replacement(root); 
      if (temp == null) 
       root = null; 
      else { 
       root.setElement(temp.getElement()); 
       root.setRight(temp.getRight()); 
       root.setLeft(temp.getLeft()); 
      } 
     } else { 
      parent = root; 
      if (((Comparable) targetElement).compareTo(root.getElement()) < 0) 
       result = removeElement(targetElement, root.getLeft(), parent); 
      else 
       result = removeElement(targetElement, root.getRight(), parent); 
     } 
    } 
    count--; 
    return result; 
} 

private T removeElement(T targetElement, BSTreeNode<T> node, 
     BSTreeNode<T> parent) throws ElementNotFoundException { 
    T result = null; 

    if (node == null) 
     throw new ElementNotFoundException("BSTree"); 
    else { 
     if (((Comparable<T>) targetElement).equals(node.getElement())) { 
      result = node.getElement(); 
      BSTreeNode<T> temp = replacement(node); 
      if (parent.getRight() == node) 
       parent.setRight(temp); 
      else 
       parent.setLeft(temp); 
     } else { 
      parent = node; 
      if (((Comparable) targetElement).compareTo(node.getElement()) < 0) 
       result = removeElement(targetElement, node.getLeft(), 
         parent); 
      else 
       result = removeElement(targetElement, node.getRight(), 
         parent); 
     } 
    } 

    return result; 
} 

private BSTreeNode<T> replacement(BSTreeNode<T> node) { 
    BSTreeNode<T> result = null; 

    if ((node.getLeft() == null) && (node.getRight() == null)) 
     result = null; 

    else if ((node.getLeft() != null) && (node.getRight() == null)) 
     result = node.getLeft(); 

    else if ((node.getLeft() == null) && (node.getRight() != null)) 
     result = node.getRight(); 

    else { 
     BSTreeNode<T> current = node.getRight(); 
     BSTreeNode<T> parent = node; 

     while (current.getLeft() != null) { 
      parent = current; 
      current = current.getLeft(); 
     } 

     current.setLeft(node.getLeft()); 
     if (node.getRight() != current) { 
      parent.setLeft(current.getRight()); 
      current.setRight(node.getRight()); 
     } 

     result = current; 
    } 

    return result; 
} 

public String toString() 
{ 
    ArrayList<T> temp = new ArrayList<T>(); 
    inOrder(root, temp); 
    return "Inorder traversal: " + temp.toString(); 
} 

public Iterator<T> iterator() 
{ 
    return iteratorInOrder(); 
} 

public Iterator<T> iteratorInOrder() 
{ 
    ArrayList<T> tempList = new ArrayList<T>(); 
    inOrder(root, tempList); 

    return tempList.iterator(); 
} 

public T findMax(){ 
    T result = null; 
    if (isEmpty()) 
     throw new ElementNotFoundException ("binary tree"); 
    else { 
     BSTreeNode<T> current = root; 

     while (current.getRight() != null) 
      current = current.getRight(); 

     result = current.getElement(); 
    } 

return result; 
} 

public T removeMax(){ 
    T result = null; 

    if (isEmpty()) 
     throw new ElementNotFoundException("binary tree"); 
    else 
    { 
     if (root.getRight() == null) 
     { 
      result = root.getElement(); 
      root = root.getLeft(); 
     } 
     else 
     { 
      BSTreeNode<T> parent = root; 
      BSTreeNode<T> current = root.getRight(); 

      while (current.getRight() != null) 
      { 
       parent = current; 
       current = current.getRight(); 
      } 

      result = current.getElement(); 
      parent.setRight(current.getLeft()); 
     } 

     count--; 
    } 

    return result; 
} 

protected void inOrder(BSTreeNode<T> node, ArrayList<T> tempList) { 
    if (node != null) { 
     inOrder(node.getLeft(), tempList); 
     tempList.add(node.getElement()); 
     inOrder(node.getRight(), tempList); 
    } 
} 

} 

Answer 1

나무가 균형 경우

int height(Node node) 
{ 
    if (node == null) 
     return 0; 

    return 1 + Math.max(height(node.left), height(node.right)); 
} 

다음, 당신은 확인하기 위해 다른 방법을 쓸 수 있습니다

boolean isBalanced(Node node) 
{ 
    int lh; 
    int rh; 

    if (node == null) 
     return true; 

    lh = height(node.left); 
    rh = height(node.right); 

    if (Math.abs(lh - rh) <= 1 
      && isBalanced(node.left) 
      && isBalanced(node.right)) { 
     return true; 
    } 
    return false; 
} 

그런 다음 JUnit 테스트 케이스를 작성하여 isBalanced()를 테스트 할 수 있습니다.

도움이 되었기를 바랍니다.