Java-자료구조 (Tree)

1. 트리 (Tree) 구조

• 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 실제로 어디에 많이 사용되나?
  • 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

2. 알아둘 용어

• Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node: 트리 맨 위에 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
• Child Node: 어떤 노드의 상위 레벨에 연결도니 노드
• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
• Sibling (Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

3. 이진 트리와 이진 탐색 트리 (Binary Search Tree

• 이진 트리: 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

4. 자료 구조 이진 탐색 트리의 장점과 주요 용도

• 주요 용도: 데이터 검색(탐색)
• 장점: 탐색 속도를 개선할 수 있음

단점은 이진 탐색 트리 알고리즘 이해 후에 살펴보기로 함

이진 트리와 정렬된 배열간의 탐색 비교

---

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

5. 직접 이진 트리 구현해 보기

5-1. 이진 탐색 트리에 데이터 넣기

• 이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함

// src/com.company.tree/NodeMgmt.java

package com.company.tree;

public class NodeMgmt {
    // head
    Node head = null;

    // Node에는 value, right, left가 있어야 한다
    public class Node {
        public Node left;
        public Node right;
        int value;
        public Node(int data) {
            this.value = data;
            this.left = null;
            this.right = null;
        }
    }

    // BST에 데이터 넣기
    public boolean insertNode(int data) {
        // Node가 하나도 없을 떄
        if(this.head == null) {
            this.head = new Node(data);
        } else {
            // Node가 하나 이상 들어가 있을 떄
            Node findNode = this.head;
            while(true) {
                // 만약 들어온 데이터가 헤드보다 작다면 왼쪽으로 가야함
                if(data < findNode.value) {
                    // 근데 left노드가 있다면?
                    if(findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        // 만약 left노드가 없다면 만들어야지
                        findNode.left = new Node(data);
                        // 이제서야 break를 통해 빼져 나온다
                        break;
                    }
                } else {
                    // 만약 작다면
                    if(findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }
}

// src/com.company/Main.java

package com.company;

import com.company.tree.NodeMgmt;

public class Main {
    public static void main(String[] args) {
        NodeMgmt myTree = new NodeMgmt();
        myTree.insertNode(2);
        myTree.insertNode(3);
        myTree.insertNode(4);
        myTree.insertNode(6);
    }
}

5-2. 이진 탐색 트리 노드 찾기

• 데이터를 넣은 규칙을 기반으로 알맞게 탐색해야 한다.

일단 유지 보수를 위해 Node 클래스를 NodeMgmt클래스와 분리해준다

// src/com.company/tree/Node.java

package com.company.tree;

// Node에는 value, right, left가 있어야 한다
public class Node {
    public Node left;
    public Node right;
    public int value;
    public Node(int data) {
        this.value = data;
        this.left = null;
        this.right = null;
    }
}

Node를 기반으로 구현된 NodeMgmt (BST) 클래스

// src/com.company/tree/NodeMgmt.java

package com.company.tree;

public class NodeMgmt {
    // head
    Node head = null;

    // BST에 데이터 넣기
    public boolean insertNode(int data) {
        // Node가 하나도 없을 떄
        if(this.head == null) {
            this.head = new Node(data);
        } else {
            // Node가 하나 이상 들어가 있을 떄
            Node findNode = this.head;
            while(true) {
                // 만약 들어온 데이터가 헤드보다 작다면 왼쪽으로 가야함
                if(data < findNode.value) {
                    // 근데 left노드가 있다면?
                    if(findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        // 만약 left노드가 없다면 만들어야지
                        findNode.left = new Node(data);
                        // 이제서야 break를 통해 빼져 나온다
                        break;
                    }
                } else {
                    // 만약 작다면
                    if(findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }

    // data를 바탕으로 이에 대한 노드를 찾는 것
    public Node search(int data) {
        // data가 하나도 없을 때
        if(this.head == null) {
            return null;
        } else {
            Node findNode = this.head;
            while(findNode != null) {
                if(findNode.value == data) {
                    // 만약 data가 같다면 찾은 노드를 반환한다.
                    return findNode;
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                } else {
                    findNode = findNode.right;
                }
            }
            return null;
        }
    }
}

Main메서드

// src/com.company/Main.java

package com.company;

import com.company.tree.Node;
import com.company.tree.NodeMgmt;

public class Main {
    public static void main(String[] args) {
        NodeMgmt myTree = new NodeMgmt();
        myTree.insertNode(2);
        myTree.insertNode(3);
        myTree.insertNode(4);
        myTree.insertNode(6);

        Node testNode = myTree.search(3);
        System.out.println(testNode.right.value);
    }
}

// 4

5-3. 이진 탐색 트리 노드 삭제 하기

매우 복잡하지만 다양한 케이스들을 분석하며 차근차근 구현해 보겠다

5-3-1. Leaf Node 삭제

• Leaf Node: Child Node가 없는 Node
• 삭제할 Node의 ParentNode가 삭제할 Node를 가리키지 않도록 한다

5-3-2. Child Node가 하나인 Node 삭제

• 삭제할 Node의 Parent Node가 삭제할 Node의 ChildNode를 가리키도록 한다.

5-3-3. Child Node가 두 개인 Node 삭제

• 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다
• -> 우린 위의 규칙으로 BST를 코딩 할 것이다.
• 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent노 Node가 가리키도록 한다.

5.3.3.1. 삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우

• 삭제할 Node의 오른쪽 자식 선택
• 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
• 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
• 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
• 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
• 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함

5-4 이진 탐색 트리 삭제 코드 구현과 분석

5-4-1 삭제할 Node 탐색

• 삭제할 Node가 없는 경우도 처리해야 함
  • 이를 위해 삭제할 Node가 없는 경우는 False를 리턴하고, 함수를 종료 시킴

//src/com.company/tree/NodeMgmt.java

package com.company.tree;

public class NodeMgmt {
    // head
    Node head = null;

    // BST에 데이터 넣기
    public boolean insertNode(int data) {
        // Node가 하나도 없을 떄
        if(this.head == null) {
            this.head = new Node(data);
        } else {
            // Node가 하나 이상 들어가 있을 떄
            Node findNode = this.head;
            while(true) {
                // 만약 들어온 데이터가 헤드보다 작다면 왼쪽으로 가야함
                if(data < findNode.value) {
                    // 근데 left노드가 있다면?
                    if(findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        // 만약 left노드가 없다면 만들어야지
                        findNode.left = new Node(data);
                        // 이제서야 break를 통해 빼져 나온다
                        break;
                    }
                } else {
                    // 만약 작다면
                    if(findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }

    // data를 바탕으로 이에 대한 노드를 찾는 것
    public Node search(int data) {
        // data가 하나도 없을 때
        if(this.head == null) {
            return null;
        } else {
            Node findNode = this.head;
            while(findNode != null) {
                if(findNode.value == data) {
                    // 만약 data가 같다면 찾은 노드를 반환한다.
                    return findNode;
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                } else {
                    findNode = findNode.right;
                }
            }
            return null;
        }
    }

    public boolean delete(int value) {
        boolean searched = false;

        // 우리는 찾아야 할 Node와 그 Parent Node를 둘다 찾아야 한다.
        // 그래서 둘 다 head로 놓고 시작한다.
        Node currParentNode = this.head;
        Node currNode = this.head;

        // 코너 케이스1: Node가 하나도 없을 때
        if(this.head == null) {
            return false;
            // 코너 케이스2: Node가 단지 하나만 있고 해당 Node가 삭제할 Node일 때
        } else {
            if(this.head.value == value && this.head.left == null && this.head.right == null) {
                this.head = null;
                return true;
            }
            // 순회 해서 찾아보도록 하자
            while(currNode != null) {
                if(currNode.value == value) {
                    searched = true;
                    break;
                } else if(value < currNode.value){
                    currParentNode = currNode;
                    currNode = currNode.left;
                } else {
                    currParentNode = currNode;
                    currNode = currNode.right;
                }
            }
            // 만약 찾지 못해서 searched 가 false인 경우
            if(searched == false) {
                return false;
            } else {
                // 결과적으로 searched가 true인 것들만
                // currNode에는 해당 데이터를 가지고 있는 Node
                // currParentNode에는 해당 데이터를 가지고 있는 Node의 Parent Node

            }
        }

    }
}

5.4.2. Case1: 삭제할 Node가 Leaf Node인 경우

// src/com.company/tree/NodeMgmt.java

package com.company.tree;

public class NodeMgmt {
    // head
    Node head = null;

    // BST에 데이터 넣기
    public boolean insertNode(int data) {
        // Node가 하나도 없을 떄
        if(this.head == null) {
            this.head = new Node(data);
        } else {
            // Node가 하나 이상 들어가 있을 떄
            Node findNode = this.head;
            while(true) {
                // 만약 들어온 데이터가 헤드보다 작다면 왼쪽으로 가야함
                if(data < findNode.value) {
                    // 근데 left노드가 있다면?
                    if(findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        // 만약 left노드가 없다면 만들어야지
                        findNode.left = new Node(data);
                        // 이제서야 break를 통해 빼져 나온다
                        break;
                    }
                } else {
                    // 만약 작다면
                    if(findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }

    // data를 바탕으로 이에 대한 노드를 찾는 것
    public Node search(int data) {
        // data가 하나도 없을 때
        if(this.head == null) {
            return null;
        } else {
            Node findNode = this.head;
            while(findNode != null) {
                if(findNode.value == data) {
                    // 만약 data가 같다면 찾은 노드를 반환한다.
                    return findNode;
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                } else {
                    findNode = findNode.right;
                }
            }
            return null;
        }
    }

    public boolean delete(int value) {
        boolean searched = false;

        // 우리는 찾아야 할 Node와 그 Parent Node를 둘다 찾아야 한다.
        // 그래서 둘 다 head로 놓고 시작한다.
        Node currParentNode = this.head;
        Node currNode = this.head;

        // 코너 케이스1: Node가 하나도 없을 때
        if(this.head == null) {
            return false;
            // 코너 케이스2: Node가 단지 하나만 있고 해당 Node가 삭제할 Node일 때
        } else {
            if(this.head.value == value && this.head.left == null && this.head.right == null) {
                this.head = null;
                return true;
            }
            // 순회 해서 찾아보도록 하자
            while(currNode != null) {
                if(currNode.value == value) {
                    searched = true;
                    break;
                } else if(value < currNode.value){
                    currParentNode = currNode;
                    currNode = currNode.left;
                } else {
                    currParentNode = currNode;
                    currNode = currNode.right;
                }
            }
            // 만약 찾지 못해서 searched 가 false인 경우
            if(searched == false) {
                return false;
            } else {
                // 결과적으로 searched가 true인 것들만
                // currNode에는 해당 데이터를 가지고 있는 Node
                // currParentNode에는 해당 데이터를 가지고 있는 Node의 Parent Node

                // 일단 currNode가 Leaf Node인 경우를 생각해 보면
                if(currNode.left == null && currNode.right == null) {
                    // currNode가 currParentNode보다 작은 경우
                    if(value < currParentNode.value) {
                        currParentNode.left = null;
                        // 안써줘도 되는데 명시적으로 처리하기 위해
                        currNode = null;
                    } else {
                        currParentNode.right = null;
                        // 이도 명시적으로 그냥 작성
                        currNode = null;
                    }
                } else if() {

                }
            }
        }

    }
}

5.5.2. Case2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우

// src/com.company/tree/NodeMgmt.java

package com.company.tree;

public class NodeMgmt {
    // head
    Node head = null;

    // BST에 데이터 넣기
    public boolean insertNode(int data) {
        // Node가 하나도 없을 떄
        if(this.head == null) {
            this.head = new Node(data);
        } else {
            // Node가 하나 이상 들어가 있을 떄
            Node findNode = this.head;
            while(true) {
                // 만약 들어온 데이터가 헤드보다 작다면 왼쪽으로 가야함
                if(data < findNode.value) {
                    // 근데 left노드가 있다면?
                    if(findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        // 만약 left노드가 없다면 만들어야지
                        findNode.left = new Node(data);
                        // 이제서야 break를 통해 빼져 나온다
                        break;
                    }
                } else {
                    // 만약 작다면
                    if(findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }

    // data를 바탕으로 이에 대한 노드를 찾는 것
    public Node search(int data) {
        // data가 하나도 없을 때
        if(this.head == null) {
            return null;
        } else {
            Node findNode = this.head;
            while(findNode != null) {
                if(findNode.value == data) {
                    // 만약 data가 같다면 찾은 노드를 반환한다.
                    return findNode;
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                } else {
                    findNode = findNode.right;
                }
            }
            return null;
        }
    }

    public boolean delete(int value) {
        boolean searched = false;

        // 우리는 찾아야 할 Node와 그 Parent Node를 둘다 찾아야 한다.
        // 그래서 둘 다 head로 놓고 시작한다.
        Node currParentNode = this.head;
        Node currNode = this.head;

        // 코너 케이스1: Node가 하나도 없을 때
        if(this.head == null) {
            return false;
            // 코너 케이스2: Node가 단지 하나만 있고 해당 Node가 삭제할 Node일 때
        } else {
            if(this.head.value == value && this.head.left == null && this.head.right == null) {
                this.head = null;
                return true;
            }
            // 순회 해서 찾아보도록 하자
            while(currNode != null) {
                if(currNode.value == value) {
                    searched = true;
                    break;
                } else if(value < currNode.value){
                    currParentNode = currNode;
                    currNode = currNode.left;
                } else {
                    currParentNode = currNode;
                    currNode = currNode.right;
                }
            }
            // 만약 찾지 못해서 searched 가 false인 경우
            if(searched == false) {
                return false;
            } else {
                // 결과적으로 searched가 true인 것들만
                // currNode에는 해당 데이터를 가지고 있는 Node
                // currParentNode에는 해당 데이터를 가지고 있는 Node의 Parent Node

                // 일단 currNode가 Leaf Node인 경우를 생각해 보면
                if(currNode.left == null && currNode.right == null) {
                    // currNode가 currParentNode보다 작은 경우
                    if(value < currParentNode.value) {
                        currParentNode.left = null;
                        // 안써줘도 되는데 명시적으로 처리하기 위해
                        currNode = null;
                    } else {
                        currParentNode.right = null;
                        // 이도 명시적으로 그냥 작성
                        currNode = null;
                    }
                    // currNode가 childNode를 하나만 가지고 있을 경우
                } else if(currNode.left != null && currNode.right == null) {
                    // Case1. 왼쪽에 ChildNode가 있을 경우
                    if(value < currParentNode.value) {
                        // 삭제할 값이 ParentNode 보다 작게 되면
                        currParentNode.left = currNode.left;
                        // 그냥 명시적으로 작성
                        currNode = null;
                    } else {
                        // 삭제할 값이 ParentNode 보다 크게 되면
                        currParentNode.right = currNode.left;
                        currNode = null;
                    }
                    return true;
                } else if(currNode.left == null && currNode.right != null) {
                    // Case2. 오른쪽에 ChildNode가 있을 경우
                    if(value < currParentNode.value) {
                        // 삭제할 값이 ParentNode 보다 크게 되면
                        currParentNode.left = currNode.right;
                        currNode = null;
                    } else {
                        currParentNode.right = currNode.right;
                        currNode = null;
                    }
                    return true;
                }
            }
        }

    }
}

5.4.3. Case3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)

• 기본 사용 가능 전략
  1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
• 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
  • 경우의 수가 또다시 두가지가 있음
    • Case3-1-1: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
    • Case3-1-2: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
      • 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임

5.4.4. Case3-2: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)

• 기본 사용 가능 전략
  1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
• 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
  • 경우의 수가 또다시 두가지가 있음
    • Case3-2-1: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
    • Case3-2-2: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
      • 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임

이를 모두 구현한 코드

package com.company.tree;

public class NodeMgmt {
    // head
    Node head = null;

    // BST에 데이터 넣기
    public boolean insertNode(int data) {
        // Node가 하나도 없을 떄
        if(this.head == null) {
            this.head = new Node(data);
        } else {
            // Node가 하나 이상 들어가 있을 떄
            Node findNode = this.head;
            while(true) {
                // 만약 들어온 데이터가 헤드보다 작다면 왼쪽으로 가야함
                if(data < findNode.value) {
                    // 근데 left노드가 있다면?
                    if(findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        // 만약 left노드가 없다면 만들어야지
                        findNode.left = new Node(data);
                        // 이제서야 break를 통해 빼져 나온다
                        break;
                    }
                } else {
                    // 만약 작다면
                    if(findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }

    // data를 바탕으로 이에 대한 노드를 찾는 것
    public Node search(int data) {
        // data가 하나도 없을 때
        if(this.head == null) {
            return null;
        } else {
            Node findNode = this.head;
            while(findNode != null) {
                if(findNode.value == data) {
                    // 만약 data가 같다면 찾은 노드를 반환한다.
                    return findNode;
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                } else {
                    findNode = findNode.right;
                }
            }
            return null;
        }
    }

    public boolean delete(int value) {
        boolean searched = false;

        // 우리는 찾아야 할 Node와 그 Parent Node를 둘다 찾아야 한다.
        // 그래서 둘 다 head로 놓고 시작한다.
        Node currParentNode = this.head;
        Node currNode = this.head;

        // 코너 케이스1: Node가 하나도 없을 때
        if(this.head == null) {
            return false;
            // 코너 케이스2: Node가 단지 하나만 있고 해당 Node가 삭제할 Node일 때
        } else {
            if(this.head.value == value && this.head.left == null && this.head.right == null) {
                this.head = null;
                return true;
            }
            // 순회 해서 찾아보도록 하자
            while(currNode != null) {
                if(currNode.value == value) {
                    searched = true;
                    break;
                } else if(value < currNode.value){
                    currParentNode = currNode;
                    currNode = currNode.left;
                } else {
                    currParentNode = currNode;
                    currNode = currNode.right;
                }
            }
            // 만약 찾지 못해서 searched 가 false인 경우
            if(searched == false) {
                return false;
            } else {
                // 결과적으로 searched가 true인 것들만
                // currNode에는 해당 데이터를 가지고 있는 Node
                // currParentNode에는 해당 데이터를 가지고 있는 Node의 Parent Node

                // 일단 currNode가 Leaf Node인 경우를 생각해 보면
                if(currNode.left == null && currNode.right == null) {
                    // currNode가 currParentNode보다 작은 경우
                    if(value < currParentNode.value) {
                        currParentNode.left = null;
                        // 안써줘도 되는데 명시적으로 처리하기 위해
                        currNode = null;
                    } else {
                        currParentNode.right = null;
                        // 이도 명시적으로 그냥 작성
                        currNode = null;
                    }
                    // currNode가 childNode를 하나만 가지고 있을 경우
                } else if(currNode.left != null && currNode.right == null) {
                    // Case1. 왼쪽에 ChildNode가 있을 경우
                    if(value < currParentNode.value) {
                        // 삭제할 값이 ParentNode 보다 작게 되면
                        currParentNode.left = currNode.left;
                        // 그냥 명시적으로 작성
                        currNode = null;
                    } else {
                        // 삭제할 값이 ParentNode 보다 크게 되면
                        currParentNode.right = currNode.left;
                        currNode = null;
                    }
                    return true;
                } else if(currNode.left == null && currNode.right != null) {
                    // Case2. 오른쪽에 ChildNode가 있을 경우
                    if(value < currParentNode.value) {
                        // 삭제할 값이 ParentNode 보다 크게 되면
                        currParentNode.left = currNode.right;
                        currNode = null;
                    } else {
                        currParentNode.right = currNode.right;
                        currNode = null;
                    }
                    return true;
                } else {
                    // Case 3
                    // ChildNode가 2개인 경우
                    // Case 3-1. 삭제할 Node가 paren Node의 왼쪽에 있을 떄
                    if(value < currParentNode.value) {
                        // 일단 가장 왼쪽으로 가야 한다
                        // 가장 작은 값을 가진 node를 change_node로
                        // 또한 change_node가 오른쪽에 자식을 갖고 있으면
                        // change_node의 왼쪽자식으로 이를 붙여줘야 하기 때문에
                        // change_node의 부모를 change_node_parent라고 해보자
                        Node changeNode = currNode.right;
                        Node changeParentNode = currNode.right;
                        // 순회를 시작한다
                        while(changeNode.left != null) {
                            changeParentNode = changeNode;
                            changeNode = changeNode.left;
                        }
                        // 여기까지 실행되었다는 뜻은 changeNode에는 삭제할 Node의 오른쪽 Node중에서
                        // 가장 작은 값을 지닌 Node가 들어가 있다는 뜻을 의미한다.
                        // 근데 만약 이의 오른쪽에 자식이 있다면?
                        if(changeNode.right != null) {
                            // changeparentNode의 왼쪽에 집어 넣는다.
                            changeParentNode.left = changeNode.right;
                        } else {
                            changeParentNode.left = null;
                        }

                        // changeNode의 오른쪽 node를 알맞는 위치로 변경
                        currParentNode.left = changeNode;

                        // ParentNode의 왼쪽 Child Node가 현재, changeNode이고,
                        // changeNode의 왼쪽/오른쪽 Child Node를 모두, 삭제할 currNode의
                        // 기존 왼쪽/오른쪽 Node로 변경ㄷ
                        changeNode.right = currNode.right;
                        changeNode.left = currNode.left;
                    } else {
                        // Case 3-1. 삭제할 Node가 paren Node의 오른쪽에 있을 때
                        Node changeNode = currNode.right;
                        Node changeParentNode = currNode.right;

                        while(changeNode.left != null) {
                            changeParentNode = changeNode;
                            changeNode = changeNode.left;
                        }
                        // changeNode가 null전 까지 그리고 changeParentNode는 그 위까지

                        // 이제 오른쪽 자식 검사
                        // 있다면
                        if(changeNode.right != null) {
                            changeParentNode.left = changeNode.right;
                        } else {
                            changeParentNode.left = null;
                        }
                        currParentNode.right = changeNode;

                        changeNode.right = currNode.right;
                        changeNode.left = currNode.left;
                    }
                }
            }
        }
    }
}

엣지 케이스
엣지 케이스란 알고리즘이 처리하는 데이터의 값이 알고리즘의 특성에 따른 일정한 범위를 넘을 경우에 발생하는 문제를 기리킨다.
예를 들면 fixnum이라는 변수의 값이 -128~127의 범위를 넘는 순간 문제가 발생하는 경우가 있을 수 있다. 어떤 분모가 0이 되는 상황처럼 데이터의 특정값에 대해 문제가 발생하는 경우도 마찬가지이다

코너 케이스
코너 케이스는 여러 가지 변수와 환경의 복합적인 상호작용으로 발생하는 문제이다. 예를 들어 fixnum이라는 변수의 값으로 128이 입력되었을 때, A기계에서 테스트했을 때는 정상작동하지만 B기계에서는 오류가 발생한다면 코너 케이스라고 할 수 있다.

코너 케이스 추가

// src/com.company/tree/NodeMgmt.java

package com.company.tree;

public class NodeMgmt {
    // head
    public Node head = null;

    // BST에 데이터 넣기
    public boolean insertNode(int data) {
        // Node가 하나도 없을 떄
        if(this.head == null) {
            this.head = new Node(data);
        } else {
            // Node가 하나 이상 들어가 있을 떄
            Node findNode = this.head;
            while(true) {
                // 만약 들어온 데이터가 헤드보다 작다면 왼쪽으로 가야함
                if(data < findNode.value) {
                    // 근데 left노드가 있다면?
                    if(findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        // 만약 left노드가 없다면 만들어야지
                        findNode.left = new Node(data);
                        // 이제서야 break를 통해 빼져 나온다
                        break;
                    }
                } else {
                    // 만약 작다면
                    if(findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }

    // data를 바탕으로 이에 대한 노드를 찾는 것
    public Node search(int data) {
        // data가 하나도 없을 때
        if(this.head == null) {
            return null;
        } else {
            Node findNode = this.head;
            while(findNode != null) {
                if(findNode.value == data) {
                    // 만약 data가 같다면 찾은 노드를 반환한다.
                    return findNode;
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                } else {
                    findNode = findNode.right;
                }
            }
            return null;
        }
    }

    public boolean delete(int value) {
        boolean searched = false;

        // 우리는 찾아야 할 Node와 그 Parent Node를 둘다 찾아야 한다.
        // 그래서 둘 다 head로 놓고 시작한다.
        Node currParentNode = this.head;
        Node currNode = this.head;

        // 코너 케이스1: Node가 하나도 없을 때
        if(this.head == null) {
            return false;
            // 코너 케이스2: Node가 단지 하나만 있고 해당 Node가 삭제할 Node일 때
        } else {
            if(this.head.value == value && this.head.left == null && this.head.right == null) {
                this.head = null;
                return true;
            }
            // 순회 해서 찾아보도록 하자
            while(currNode != null) {
                if(currNode.value == value) {
                    searched = true;
                    break;
                } else if(value < currNode.value){
                    currParentNode = currNode;
                    currNode = currNode.left;
                } else {
                    currParentNode = currNode;
                    currNode = currNode.right;
                }
            }
            // 만약 찾지 못해서 searched 가 false인 경우
            if(searched == false) {
                return false;
            } else {
                // 결과적으로 searched가 true인 것들만
                // currNode에는 해당 데이터를 가지고 있는 Node
                // currParentNode에는 해당 데이터를 가지고 있는 Node의 Parent Node

                // 일단 currNode가 Leaf Node인 경우를 생각해 보면
                if(currNode.left == null && currNode.right == null) {
                    // currNode가 currParentNode보다 작은 경우
                    if(value < currParentNode.value) {
                        currParentNode.left = null;
                        // 안써줘도 되는데 명시적으로 처리하기 위해
                        currNode = null;
                    } else {
                        currParentNode.right = null;
                        // 이도 명시적으로 그냥 작성
                        currNode = null;
                    }
                    // currNode가 childNode를 하나만 가지고 있을 경우
                } else if(currNode.left != null && currNode.right == null) {
                    // Case1. 왼쪽에 ChildNode가 있을 경우
                    if(value < currParentNode.value) {
                        // 삭제할 값이 ParentNode 보다 작게 되면
                        currParentNode.left = currNode.left;
                        // 그냥 명시적으로 작성
                        currNode = null;
                    } else {
                        // 삭제할 값이 ParentNode 보다 크게 되면
                        currParentNode.right = currNode.left;
                        currNode = null;
                    }
                    return true;
                } else if(currNode.left == null && currNode.right != null) {
                    // Case2. 오른쪽에 ChildNode가 있을 경우
                    if(value < currParentNode.value) {
                        // 삭제할 값이 ParentNode 보다 크게 되면
                        currParentNode.left = currNode.right;
                        currNode = null;
                    } else {
                        currParentNode.right = currNode.right;
                        currNode = null;
                    }
                    return true;
                } else {
                    // Case 3
                    // ChildNode가 2개인 경우
                    // Case 3-1. 삭제할 Node가 paren Node의 왼쪽에 있을 떄
                    if(value < currParentNode.value) {
                        // 일단 가장 왼쪽으로 가야 한다
                        // 가장 작은 값을 가진 node를 change_node로
                        // 또한 change_node가 오른쪽에 자식을 갖고 있으면
                        // change_node의 왼쪽자식으로 이를 붙여줘야 하기 때문에
                        // change_node의 부모를 change_node_parent라고 해보자
                        Node changeNode = currNode.right;
                        Node changeParentNode = currNode.right;
                        // 순회를 시작한다
                        while(changeNode.left != null) {
                            changeParentNode = changeNode;
                            changeNode = changeNode.left;
                        }
                        // 여기까지 실행되었다는 뜻은 changeNode에는 삭제할 Node의 오른쪽 Node중에서
                        // 가장 작은 값을 지닌 Node가 들어가 있다는 뜻을 의미한다.
                        // 근데 만약 이의 오른쪽에 자식이 있다면?
                        if(changeNode.right != null) {
                            // changeparentNode의 왼쪽에 집어 넣는다.
                            changeParentNode.left = changeNode.right;
                        } else {
                            changeParentNode.left = null;
                        }

                        // changeNode의 오른쪽 node를 알맞는 위치로 변경
                        currParentNode.left = changeNode;

                        // ParentNode의 왼쪽 Child Node가 현재, changeNode이고,
                        // changeNode의 왼쪽/오른쪽 Child Node를 모두, 삭제할 currNode의
                        // 기존 왼쪽/오른쪽 Node로 변경ㄷ
                        changeNode.right = currNode.right;
                        changeNode.left = currNode.left;

                        // 명시적으로 처리 해준다.
                        currNode = null;
                    } else {
                        // Case 3-1. 삭제할 Node가 paren Node의 오른쪽에 있을 때
                        Node changeNode = currNode.right;
                        Node changeParentNode = currNode.right;

                        while(changeNode.left != null) {
                            changeParentNode = changeNode;
                            changeNode = changeNode.left;
                        }
                        // changeNode가 null전 까지 그리고 changeParentNode는 그 위까지

                        // 이제 오른쪽 자식 검사
                        // 있다면
                        if(changeNode.right != null) {
                            changeParentNode.left = changeNode.right;
                        } else {
                            changeParentNode.left = null;
                        }
                        currParentNode.right = changeNode;


                        // currNode.right가 changeNode인 경우 changeNode가 currNode자리로 올라 가면서
                        // 오른쪽에 다시 자신의 객체를 가리키는 상황이 될 수 있습니다.

                        if(currNode.right != changeNode) {
                            changeNode.right = currNode.right;
                        }
                        changeNode.left = currNode.left;

                        // 명시적으로 처리 해준다.
                        currNode = null;
                    }
                }
            }
            return true;
        }
    }
}

코드 테스트

// src/com.company/Main.java

package com.company;

import com.company.tree.Node;
import com.company.tree.NodeMgmt;

public class Main {
    public static void main(String[] args) {
        NodeMgmt myTree = new NodeMgmt();
        myTree.insertNode(10);
        myTree.insertNode(15);
        myTree.insertNode(13);
        myTree.insertNode(11);
        myTree.insertNode(14);
        myTree.insertNode(18);
        myTree.insertNode(16);
        myTree.insertNode(19);
        myTree.insertNode(17);
        myTree.insertNode(7);
        myTree.insertNode(8);
        myTree.insertNode(6);
        System.out.println(myTree.delete(15));
        System.out.println("HEAD: " + myTree.head.value);
        System.out.println("HEAD LEFT: " + myTree.head.left.value);
        System.out.println("HEAD LEFT LEFT: " + myTree.head.left.left.value);
        System.out.println("HEAD LEFT RIGHT: " + myTree.head.left.right.value);

        System.out.println("HEAD RIGHT: " + myTree.head.right.value);
        System.out.println("HEAD RIGHT LEFT: " + myTree.head.right.left.value);
        System.out.println("HEAD RIGHT RIGHT: " + myTree.head.right.right.value);

        System.out.println("HEAD RIGHT RIGHT LEFT: " + myTree.head.right.right.left.value);
        System.out.println("HEAD RIGHT RIGHT RIGHT: " + myTree.head.right.right.right.value);
    }
}

// true
// HEAD: 10
// HEAD LEFT: 7
// HEAD LEFT LEFT: 6
// HEAD LEFT RIGHT: 8
// HEAD RIGHT: 16
// HEAD RIGHT LEFT: 13
// HEAD RIGHT RIGHT: 18
// HEAD RIGHT RIGHT LEFT: 17
// HEAD RIGHT RIGHT RIGHT: 19

---

6. 이진 탐색 트리의 시간 복잡도와 단점

6-1. 시간 복잡도 (탐색 시)

• depth(트리의 높이) 를 h라고 한다면, O(h)
• n개의 노드를 가진다면 h = log n에 가까우므로, 시간 복잡도는 O(log n)
  • 참고 : 빅오 표기법에서 logn에서의 log의 밑은 10이 아니라 2이다.
    • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미, 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미
    

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

6-2. 이진 탐색 트리의

• 평균 시간 복잡도는 O(log n)이지만,
  • 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
• 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트와 동일한 성능을 보여줌 ( O(n))