이진탐색트리BinarySearchTree

알고리즘 이론 공부 하면서 구현해봄

삭제하는 함수가 어렵다
삭제대상 노드의 상황에 따라서 3가지 경우가 있다
1.말단노드 일때(쉬움) 부모의 left 나 right null처리
2.자녀가 하나만 있을때(쉬움) 부모와 삭제대상노드의 자녀를 연결.
3.자녀가 둘일때(어려움)

3번의 경우에 처리하는 방식이 2가지 방법이 있다
첫째. 삭제대상노드의 왼쪽 자녀중 가장 큰값을 가진 노드와 자리 교환하는 방법
둘째. 삭제대상노드의 오른쪽 자녀중 가장 작은 값을 가진 노드와 자리 교환하는 방법이 있다. 코드에서 minChild 라고 구현함

코드는 둘째 방법을 사용하여 구현하였다

그럼 추가적으로 구현할때 코드에서 분기되는 것들이 있다.

3.1 부모의 왼쪽노드 인가(부모의 left 를 minChild로 갱신)
3.2 부모의 오른쪽 노드인가(부모의 right 를 minChild로 갱신

3.1.1 minChild 가 오른쪽 자녀가 있나(하나만 있다. 둘있는 경우는 없다. 왜냐면 가장 작은 값을 가진 노드를 찾은 거니까)
3.1.2 자녀가 없나

에 따라서 삭제대상 노드와 minChild 의 자리교환에 따른 처리만 하면된다

public class BST {

    public class Node{
        int value;
        Node left;
        Node right;
        Node(int value)
        {
            this.value = value;
        }
    }

    public Node head;

    public boolean Insert(int value)
    {
        if(head != null)
        {
            Node search = head;
            while(true)
            {
                if(value < search.value)
                {
                    if(search.left == null)
                    {
                        search.left = new Node(value);
                        return true;
                    }
                    search = search.left;
                }
                else if(value > search.value)
                {
                    if(search.right == null)
                    {
                        search.right = new Node(value);
                        return true;
                    }
                    search = search.right;
                }
                else
                    return false;
            }
        }
        else
            head = new Node(value);

        return true;
    }

    public boolean Update(int value)
    {
        if(head != null)
        {
            Node search = head;
            while(search != null)
            {
                if(value < search.value)
                    search = search.left;
                else if(value > search.value)
                    search = search.right;
                else {
                    search.value = value;
                    return true;
                }
            }
        }
        return false;
    }

    public boolean Delete(int value)
    {
        if (head == null)
            return false;

        boolean SearchSuccess = false;
        Node deleteTarget = head;

        Node parent = null;
        while (deleteTarget != null) {
            parent = deleteTarget;
            if (value < deleteTarget.value)
                deleteTarget = deleteTarget.left;
            else if (value > deleteTarget.value)
                deleteTarget = deleteTarget.right;

            if(deleteTarget.value == value)
            {
                SearchSuccess = true;
                break;
            }
        }
        if (false == SearchSuccess)
            return false;

        //LeafNode
        if(deleteTarget.left == null && deleteTarget.right == null)
        {
            if(deleteTarget.value < parent.value)
            {
                parent.left = null;
                deleteTarget = null;
            }
            else
            {
                parent.right = null;
                deleteTarget = null;
            }
        }
        //One Child
        else if(deleteTarget.left != null && deleteTarget.right == null)
        {
            if(deleteTarget.value < parent.value)
            {
                parent.left = deleteTarget.left;
                deleteTarget = null;
            }
            else
            {
                parent.right = deleteTarget.left;
                deleteTarget = null;
            }
        }
        else if(deleteTarget.left == null && deleteTarget.right != null)
        {
            if(deleteTarget.value < parent.value)
            {
                parent.left = deleteTarget.right;
                deleteTarget = null;
            }
            else
            {
                parent.right = deleteTarget.right;
                deleteTarget = null;
            }
        }
        //Tow Child
        else
        {

            if(deleteTarget.value < parent.value)
            {
                //Find d's right child who has min value(minChild)
                Node minChild = deleteTarget.right;
                Node ParentOfminChild = deleteTarget;

                while(minChild.left != null)
                {
                    ParentOfminChild = minChild;
                    minChild = minChild.left;
                }

                //minChild has right child
                if(minChild.right != null)
                {
                    ParentOfminChild.left = minChild.right;
                }
                //minChild has no child
                else
                {
                    ParentOfminChild.left = null;
                }

                parent.left = minChild;
                minChild.left = deleteTarget.left;
                minChild.right = deleteTarget.right;

                deleteTarget = null;
            }
            else
            {
                //Find d's right child who has min value(minChild)
                Node minChild = deleteTarget.right;
                Node ParentOfminChild = deleteTarget;

                while(minChild.left != null)
                {
                    ParentOfminChild = minChild;
                    minChild = minChild.left;
                }

                //minChild has right child
                if(minChild.right != null)
                {
                    ParentOfminChild.left = minChild.right;
                }
                //minChild has no child
                else
                {
                    ParentOfminChild.left = null;
                }

                parent.right = minChild;
                minChild.left = deleteTarget.left;
                minChild.right = deleteTarget.right;

                deleteTarget = null;
            }
        }


        return true;

    }

}