Rhyme/ルックアップツリーADT-二叉ルックアップツリーの簡単なシミュレーションJava版


検索ツリーADT-二叉検索ツリーの簡単なシミュレーションJava版
package my.binary.search.tree;

/**
 *     ADT         
 *        Integer
 *
 * @author RhymeChiang
 * @date 2018/01/17
 **/
public class BinarySearchTree<T extends Comparable super T>> {

    /**
     *       
     */
    private BinaryNode root;

    /**
     *        
     *
     * @param 
     */
    private static class BinaryNode<T> {

        private T element;
        private BinaryNode left;
        private BinaryNode right;

        public BinaryNode() {
        }

        public BinaryNode(T element) {
            this.element = element;
        }

        public BinaryNode(T element, BinaryNode left, BinaryNode right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }

    /**
     *      
     */
    public void makeEmpty() {
        root = null;
    }

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

    /**
     *     element           
     *
     * @param element
     * @return
     */
    public boolean contains(T element) {
        return contains(element, root);
    }

    /**
     *     element          root 
     *
     * @param element
     * @param root
     * @return
     */
    private boolean contains(T element, BinaryNode root) {
        if (root == null) {
            return false;
        }
        int compareResult = element.compareTo(root.element);

        if (compareResult > 0) {
            return contains(element, root.right);
        }

        if (compareResult < 0) {
            return contains(element, root.left);
        }

        return true;

    }

    /**
     *              
     *
     * @return
     */
    public T findMin() {
        if (findMin(root) != null) {
            return findMin(root).element;
        }
        return null;
    }

    /**
     *              
     *
     * @param root
     * @return
     */
    private BinaryNode findMin(BinaryNode root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            return findMin(root.left);
        }
        return root.left;
    }

    /**
     *            
     *
     * @return
     */
    public T findMax() {
        BinaryNode maxNode = findMax(root);
        if (maxNode != null) {
            return maxNode.element;
        }
        return null;
    }

    /**
     *              
     *
     * @param root
     * @return
     */
    private BinaryNode findMax(BinaryNode root) {
        if (root == null) {
            return null;
        }
        if (root.right != null) {
            return findMax(root.right);
        }
        return root.right;
    }

    /**
     *     element
     *
     * @param element
     */
    public void insert(T element) {
        root = insert(element, root);
    }

    /**
     *       root      
     *
     * @param element
     * @param root
     * @return
     */
    private BinaryNode insert(T element, BinaryNode root) {
        if (root == null) {
            return new BinaryNode<>(element);
        }
        int compareResult = element.compareTo(root.element);
        if (compareResult > 0) {
            root.right = insert(element, root.right);
        } else if (compareResult < 0) {
            root.left = insert(element, root.left);
        }
        return root;
    }

    /**
     *         element
     *
     * @param element
     */
    public void remove(T element) {

    }

    /**
     *            element
     *
     * @param element
     * @param root
     * @return
     */
    private BinaryNode remove(T element, BinaryNode root) {
        if (root == null) {
            return null;
        }

        int compareResult = element.compareTo(root.element);

        if (compareResult > 0) {
            root.right = remove(element, root.right);
        } else if (compareResult < 0) {
            root.left = remove(element, root.left);
        }
        //            
        else if (root.left != null && root.right != null) {
            root.element = findMin(root.right).element;
            root.right = remove(root.element, root.right);
        }
        //          
        else {
            root = (root.left != null) ? root.left : root.right;
        }
        return root;
    }
}