Java - 平衡型BinarySearchTreeのJUnitテスト

Question

私は実用的なバイナリ検索ツリーを作成し、それに合わせていくつかのJUnitテストを構築したいと考えています。私は3つの作業を行っています：1つは最大値（InOrderトラバーサル）を見つけて、1つはこの最大値を取り除き、もう1つはバイナリツリーが均衡しているかどうかを調べることです。私は最初の2つを書いてきましたが、最後のテストをどのようにしてバランスをとるかを決める方法が分かりません。私は何かを見過ごしたような気がするので、私はいくつかの指導に感謝します。

私の試験方法：

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

次に、isBalanced（）をテストするJUnitテストケースを記述することができます。

こちらがお役に立てば幸いです。