データ構造とアルゴリズム-ツリー検索(java説明)

一、概説
バイナリ・ソート・ツリー(Binary Sort Tree)は、バイナリ・サーチ・ツリー(Binary Search Tree)とも呼ばれ、バイナリ・サーチ・ツリーとも呼ばれます.
1.1、定義
(1)左サブツリーが空でない場合、左サブツリー上のすべてのノードの値はそのルートノードの値以下である.(2)右サブツリーが空でない場合、右サブツリー上のすべてのノードの値はそのルートノードの値以上である.(3)左サブツリー、右サブツリーもそれぞれ2つのフォークソートツリーである.
二、二叉検索ツリーの実現
ここでの二叉検索ツリーの定義は、前のブログの二叉ツリーの定義で拡張されているので、これらの操作は二叉ツリーが定義した操作の補完です.
2.1、抽象実現
BinarySearchTreeADT.java:

package sihai;

/**
 *        
 */
public interface BinarySearchTreeADT extends BinaryTreeADT 
{
    /** 
     *               
     */
    public void addElement(T element);

    /** 
     *            
     */ 
    public T removeElement(T targetElement);

    /** 
     *               
     */
    public void removeAllOccurrences(T targetElement);

    /** 
     *          
     */
    public T removeMin();

    /** 
     *          
     */ 
    public T removeMax();

    /** 
     *          
     */ 
    public T findMin();

    /** 
     *         
     */
    public T findMax();
}

三、チェーンテーブルで二叉検索ツリーを実現する
ここでBinaryTreeNodeクラスは、ツリー内の各ノードを表します.各BinaryTreeNodeオブジェクトは、ノードに格納されている要素への参照を維持し、また、ノードへの各子供への参照も維持します.LinkedBinaryTreeは、空の作成を担当する2つのコンストラクション関数を提供します.もう1つは、ルートノードが特定の要素であるリンクツリーを作成します.
LinkedBinaryTree.java:

package jsjf;

import jsjf.exceptions.*;
import jsjf.*;

/**
 *                          
 */
public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T>
                                        implements BinarySearchTreeADT
{

    public LinkedBinarySearchTree() 
    {
        super();
    }


    public LinkedBinarySearchTree(T element) 
    {
        super(element);

        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");
    }

    /**
     *     
     */
    public void addElement(T element) 
    {
        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");

        Comparable comparableElement = (Comparable)element;

        if (isEmpty())
            root = new BinaryTreeNode(element);
        else 
        {
            if (comparableElement.compareTo(root.getElement()) < 0)
            {
                if (root.getLeft() == null) 
                    this.getRootNode().setLeft(new BinaryTreeNode(element));
                else
                    addElement(element, root.getLeft());
            }
            else
            {
                if (root.getRight() == null) 
                    this.getRootNode().setRight(new BinaryTreeNode(element));
                else
                    addElement(element, root.getRight());
            }
        }
        modCount++;
    }

    /**
     *           
     */
    private void addElement(T element, BinaryTreeNode node) 
    {
        Comparable comparableElement = (Comparable)element;

        if (comparableElement.compareTo(node.getElement()) < 0)
        {
            if (node.getLeft() == null) 
                node.setLeft(new BinaryTreeNode(element));
            else
                addElement(element, node.getLeft());
        }
        else
        {
            if (node.getRight() == null) 
                node.setRight(new BinaryTreeNode(element));
            else
                addElement(element, node.getRight());
        }
    }


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

        if (isEmpty())
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else
        {
            BinaryTreeNode parent = null;
            if (((Comparable)targetElement).equals(root.element)) 
            {
                result =  root.element;
                BinaryTreeNode temp = replacement(root);
                if (temp == null)
                    root = null;
                else 
                {
                    root.element = temp.element;
                    root.setRight(temp.right);
                    root.setLeft(temp.left);
                }

                modCount--;
            }
            else 
            {                
                parent = root;
                if (((Comparable)targetElement).compareTo(root.element) < 0)
                    result = removeElement(targetElement, root.getLeft(), parent);
                else
                    result = removeElement(targetElement, root.getRight(), parent);
            }
        }

        return result;
    }

    /**
     *     
     */
    private T removeElement(T targetElement, BinaryTreeNode node, BinaryTreeNode parent)
    throws ElementNotFoundException 
    {
        T result = null;

        if (node == null)
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else
        {
            if (((Comparable)targetElement).equals(node.element)) 
            {
                result =  node.element;
                BinaryTreeNode temp = replacement(node);
                if (parent.right == node)
                    parent.right = temp;
                else 
                    parent.left = temp;

                modCount--;
            }
            else 
            {                
                parent = node;
                if (((Comparable)targetElement).compareTo(node.element) < 0)
                    result = removeElement(targetElement, node.getLeft(), parent);
                else
                    result = removeElement(targetElement, node.getRight(), parent);
            }
        }

        return result;
    }

    /**
     *                
     */
    private BinaryTreeNode replacement(BinaryTreeNode node) 
    {
        BinaryTreeNode result = null;

        if ((node.left == null) && (node.right == null))
            result = null;

        else if ((node.left != null) && (node.right == null))
            result = node.left;

        else if ((node.left == null) && (node.right != null))
            result = node.right;

        else
        {
            BinaryTreeNode current = node.right;
            BinaryTreeNode parent = node;

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

            current.left = node.left;
            if (node.right != current)
            {
                parent.left = current.right;
                current.right = node.right;
            }

            result = current;
        }

        return result;
    }

    /**
     *            
     */
    public void removeAllOccurrences(T targetElement)
                   throws ElementNotFoundException 
    {
        removeElement(targetElement);

        try
        {
            while (contains((T)targetElement))
                removeElement(targetElement);
        }

        catch (Exception ElementNotFoundException)
        {
        }
    }

    /**
     *      
     */
    public T removeMin() throws EmptyCollectionException 
    {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else 
        {
            if (root.left == null) 
            {
                result = root.element;
                root = root.right;
            }
            else 
            {
                BinaryTreeNode parent = root;
                BinaryTreeNode current = root.left;
                while (current.left != null) 
                {
                    parent = current;
                    current = current.left;
                }
                result =  current.element;
                parent.left = current.right;
            }

            modCount--;
        }

        return result;
    }

    /**
     *       
     */
    public T removeMax() throws EmptyCollectionException 
    {
        // TODO
    }

    /**
     *             
     */
    public T findMin() throws EmptyCollectionException 
    {
        // TODO
    }

    /**
     *             
     */
    public T findMax() throws EmptyCollectionException 
    {
        // TODO
    }

    /**
     *       
     */
    public T find(T targetElement) throws ElementNotFoundException 
    {
        // TODO
    }

    /**
     *      
     */
    public LinkedBinarySearchTree getLeft()
    {
        // TODO
    }

    /**
     *      
     */
    public LinkedBinarySearchTree getRight()
    {
        // TODO
    }

    /**
     *       
     */
    private BinaryTreeNode findNode(T targetElement, BinaryTreeNode next) 
    {
        // TODO
    }
}

注意:中にはまだいくつか改善されていないものがあります.後でゆっくり勉強して改善します.
$(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('
').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); });