搜索树

package com.company.stucts.binarytree.searchtree;
/**
 * nowjava - 时代Java 提 供 
**/


import java.util.Comparator;


@SuppressWarnings({ "Duplicates", "WeakerAccess" })

public class SearchTree<K, V> {

    private Node<K, V> rootNode;

    private final Comparator<K> comparator;


    public SearchTree(Comparator<K> comparator) {

        this.comparator = comparator;

    }/** 来 自 NowJava.com**/


    public void add(K key, V value) {

        Node<K, V> node = rootNode;

        Node<K, V> parentNode = null;


        while (node != null) {

            int result = comparator.compare(key, node.key);

            if (result == 0) {

                node.value = value;

                return;

            } else {

                parentNode = node;

                if (result < 0) {

                    node = node.left;

                } else {

                    node = node.right;

                }

            }

        }


        Node<K, V> newNode = new Node<>(key, value);


        if (parentNode == null) {

            rootNode = newNode;

        } else {

            if (comparator.compare(key, parentNode.key) < 0) {

                parentNode.left = newNode;

            } else {

                parentNode.right = newNode;

            }

        }

    }


    public V getValue(K key) {

        Node<K, V> node = rootNode;

        while (node != null) {

            int result = comparator.compare(key, node.key);

            if (result == 0) {

                return node.value;

            }


            if (result < 0) {

                node = node.left;

            } else {

                node = node.right;

            }

        }


        return null;

    }


    public void remove(K key) {

        Node<K, V> node = rootNode;

        Node<K, V> parentNode = null;


        // search node

        while (node != null) {

            int result = comparator.compare(key, node.key);

            if (result == 0) {

                break;

            }


            parentNode = node;

            if (result < 0) {

                node = node.left;

            } else {

                node = node.right;

            }

        }


        // node not find

        if (node == null) {

            return;

        }


        if (node.right == null) {

            if (parentNode == null) {

                // change root node

                rootNode = node.left;

            } else {

                // change parent node

                if (node == parentNode.left) {

                    parentNode.left = node.left;

                } else {

                    parentNode.right = node.left;

                }

            }

        } else {

            Node<K, V> mostLeftNode = node.right;

            parentNode = null;


            while (mostLeftNode.left != null) {

                parentNode = mostLeftNode;

                mostLeftNode = mostLeftNode.left;

            }


            node.value = mostLeftNode.value;

            node.key = mostLeftNode.key;

            if (parentNode != null) {

                parentNode.left = mostLeftNode.right;

            } else {

                node.right = mostLeftNode.right;

            }

        }

    }


    public void printTree() {

        printNode(rootNode);

    }


    private void printNode(Node<K, V> node) {

        System.out.println("Node: [" + node.key + "," + node.value + "]");

        if (node.left != null) {

            printNode(node.left);

        }


        if (node.right != null) {

            printNode(node.right);

        }

    }


    private static class Node<K, V> {

        private K key;

        private V value;

        private Node<K, V> left, right;


        Node(K key, V value) {

            this.key = key;

            this.value = value;

        }

    }


    /**

     * Test main method

     */