[Data Structure] Java Binary Search Tree 구현

🎯 목표 :  이진 탐색 트리를 구현하며, 균형 잡힌 이진 탐색 트리를 구현 하기 위한 알고리즘 학습

📒 Binary Search Tree

📌 이진 탐색 트리 조건

• 모든 노드는 유일한 키를 가진다.
• 왼쪽 서브 트리의 키는 루트의 키보다 작다.
• 오른쪽 서브 트리의 키는 루트의 키보다 크다
• 왼쪽과 오른쪽 서브 트리 모두 이진 탐색 트리다.

---

📌 이진 탐색 트리 장점 

• 구조가 단순하다.
• 중위 순회를 하면 키값의 오름차순으로 노드를 얻을수 있다.
• 이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다.
• 노드를 삽입하고 지우는 것이 쉽다.

---

📒 이진 탐색 트리 구현

📌 이진 탐색 트리의 개별 Node Class

• 각 노드를 정의할 Class
• 각 노드는 고유의 키를 가진 맴벼 변수 Key가 있다.
• 각 노드는 고유의 키에 대한 데이터를 가진 맴버 변수 value가 있다.
• 고유의 키를 가지며, 자식 노드를 참조하는 노드를 맴버 변수로 가지고 있다(left, right).
• 각 변수에 대한 게터 세터를 가지며, 해당 노드의 데이터를 출력해주는 print 메소드를 가지고있다.

    static class Node<Key,Value>{
        private Key key;
        private Value data;
        private Node<Key,Value> left;
        private Node<Key,Value> right;

        public Node(Key key, Value data, Node<Key, Value> left, Node<Key, Value> right) {
            this.key = key;
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public Key getkey() { return key; }

        public void setKey(Key key) { this.key = key; }

        public Value getData() { return data; }

        public void setData(Value data) { this.data = data; }

        // 해당 노드의 데이터를 출력한다.
        public void print(){ System.out.println(data); }
    }

---

📌 이진 탐색 트리 클래스의 변수, 생성자, 삽입 요소 비교 메소드

• Node 클래스의 root 변수, 삽입 요소를 비교할 Comparator
• root값을 null 값으로 초기화 해주고, comparator가 따로 정의 되어 있다면 생성자로 받아 선언한다.
• 기본형 데이터 타입을 인자로 받았을때 기본 정렬 방식을 구현할 메소드 comp()

    private Node<Key,Value> root;
    private Comparator<? super Key> comparator = null;
    // root의 값 초기화 생성자
    public BsTreeLink (){
        root=null;
    }
    // 비어있는 루트 트리를 생성하고 전달받은 comparator을 정의한다.
    public BsTreeLink (Comparator<? super Key> c){
        this();
        comparator = c;
    }
    private int comp(Key key1, Key key2){
        return (comparator == null) ?
                // 기본 정렬 기준이 있는 데이터가 들어온다면 compareTo 메소드가 구현된다.
                ((Comparable<Key>)key1).compareTo(key2)
                // 생성자로 트리 생성을 했다면, 비교자로 비교
                : comparator.compare(key1,key2);
    }

---

📌 탐색 메소드 search(key)

search 알고리즘

• 루트를 p로 정의한다.
• p가 null 이면 검색에 실패후 메소드 종료.
• 검색하는 노드의 key와 p의 key를 비교.
• 작으면 왼쪽 크면 오른쪽으로 가서 해당 노드를 p로 정의후 1의 과정부터 다시 탐색한다.

    public  Value search(Key key){
        Node<Key, Value> p = root;
        while (true){
            if(p==null) return null; // 실패
            int cond = comp(key,p.getkey()); // key와 p의 키값 비교
            if (cond == 0) return p.getData(); // 같다면 Data 반환
            else if(cond<0) p= p.left; // 작다면 cond는 -1일 것이고 왼쪽 자식노드를 루트로 다시검색
            else p=p.right; // 크다면 cond는 1일 것이고 오른쪽 자식노드를 루트로 다시검색
        }
    }

---

📌 삽입 메소드 add(node,key,data)

add 알고리즘

• 서브트리의 루트를 선택하고 p로 정의한다.
• 삽입할 key와 p의 키값을 비교한다. 같다면 실패 메소드 종료.
• 작다면 왼쪽 노드로 가서 비어있다면 삽입 같이 있다면 재귀 호출.
• 크다면 오른쪽 노드로 가서 비어 있다면 삽입 값이 있다면 재귀 호출.

    private void addNode(Node<Key,Value> p,Key key, Value data){
        int cond = comp(key,p.getkey());
        if(cond==0) return; // 같다면 종료
        else if (cond<0) { // 작다면 왼쪽으로 가서 비교
            if(p.left==null) p.left = new Node<Key,Value>(key,data,null,null);
            else addNode(p.left,key,data);
        }else { // 크다면 오른쪽으로 가서 비교
            if(p.right==null) p.right = new Node<Key,Value>(key,data,null,null);
            else addNode(p.right,key,data);
        }
    }

    public void add(Key key, Value data){
        // 루트가 비어있다면 새로운 노드 생성
        if(root == null) root = new Node<Key,Value>(key,data,null,null);
        // 아니라면 addNode 메소드 호출하여 비어있는 노드에 키와 데이터 값 삽입
        else addNode(root,key,data);
    }

---

📌 삭제 메소드 remove(Node)

remove 알고리즘

1. 자식 노드가 없는 노드를 삭제하는 경우
1.1 삭제할 노드가 부모노드의 왼쪽이면 왼쪽 포인터를 null
1.2 삭제할 노드가 부모노드의 오른쪽이면 오른쪽 포인터를 null
2.자식 노드가 하나인 노드를 삭제하는 경우
2.1 삭제할 노드가 부모노드의 왼쪽이면 왼쪽 포인터를 삭제할 노드 자식 노드를 가르키도록 정의
2.2 삭제할 노드가 부모노드의 오른쪽이면 오른쪽 포인터를 삭제할 노드 자식 노드를 가르키도록 정의
3. 자식 노드가 둘인 노드를 삭제하는 경우
3.1 삭제할 노드의 왼쪽 서브트리에서 키값이 가장 큰 노드를 검색
3.2 검색할 노드의 데이터를 삭제할 노드로 복사
3.3 검색한 노드를 삭제
3.3.1 3.3에서 삭제한 노드에 자식이 없다면 1의 순서에 따라 삭제
3.3.2 3.3에서 삭제한 노드에 자식이 1개만 있다면 2의 순서에 따라 삭제
# 서브 트리에서 키값이 가장 큰 노드를 검색 하였을때 자식이 하나거나 없는 경우밖에 없다.

    public boolean remove(Key key){
        Node<Key,Value> p = root; // 탐색중인 노드
        Node<Key,Value> parent = null; // 탐색중인 노드의 부모 노드
        boolean isLeftChild = true; // p가 부모의 왼쪽 자식 노드인지 확인

        // 삭제할 노드를 탐색
        while (true){
            if(p==null) return false; // 탐색중인 노드가 비어있다면 삭제 실패.
            int cond = comp(key,p.getkey()); // key와 p의 키 값을 비교
            if(cond==0) break; // 찾으면 반복문 빠져나감.
            else {
                parent = p;
                if(cond<0){
                    isLeftChild = true;
                    p = p.left;
                } else {
                    isLeftChild = false;
                    p= p.right;
                }
            }
        }
        // p의 왼쪽 노드가 없을때
        if (p.left==null){
            if(p==root) root = p.right; // root를 삭제할때
                // 삭제할 노드가 부모노드의 왼쪽 일때
            else if(isLeftChild) parent.left = p.right;
                // 삭제할 노드가 부모노드의 오른쪽 일때
            else parent.right = p.right;
        // p의 양쪽 노드가 없을때
        } else if (p.right == null) {
            if(p==root) root=p.left; // root를 삭제할때
            else if(isLeftChild) parent.left = p.left;
            else parent.right = p.left;
        } else {
            // 삭제할 노드의 양쪽 모두 노드를 가지고 있을때.
            parent = p;
            Node<Key,Value> left = p.left;
            isLeftChild = true;
            // 삭제할 노드의 왼쪽 서브트리에서 가장 큰 키 값을 찾는다.
            while (left.right != null){
                parent = left;
                left = left.right;
                isLeftChild = false;
            }
            p.key = left.key;
            p.data = left.data;
            if(isLeftChild) parent.left = left.left;
            else parent.right = left.left;
        }
        return true;
    }

---

📌 순회와 출력

중위 순회, 전위 순회, 후위 순회를 구현하고 출력한다.

    // 중위 순회
    private void inorderSubTree(Node node){
        if(node != null){
            inorderSubTree(node.left);
            System.out.println(node.key+" = "+node.data);
            inorderSubTree(node.right);
        }
    }
    // 전위 순회
    private void preOrderSubTree(Node node){
        if(node != null){
            System.out.println(node.key+" = "+node.data);
            preOrderSubTree(node.left);
            preOrderSubTree(node.right);
        }
    }
    // 후위 순회
    private void postOrderSubTree(Node node){
        if(node != null){
            postOrderSubTree(node.left);
            postOrderSubTree(node.right);
            System.out.println(node.key+" = "+node.data);
        }
    }

    // 트리의 모든 데이터 출력
    public void print(){
        inorderSubTree(root);
    }
    public void preOrderPrint(){
        preOrderSubTree(root);
    }
    public void postOrderPrint(){
        postOrderSubTree(root);
    }

---

📌 균형 탐색 트리

• 이진 탐색 트리는 검색 삽입 삭제 하는 과정을 효율적으로 실행하지만,키 값의 오름 차순으로 노드를 삽입하는 상황에서는 트리의 높이가 지나치게 커진다.
• 이를 보완 하기 위해 균형 탐색 트리를 활용한다.
• 이진 균형 탐색 트리에는 AVL트리, 레드-블랙 트리 등이 있다.
• 추후 이진 탐색 트리를 균형 탐색 트리로 재 조정하는 알고리즘을 구현해보는 시간을 가져야 겠다.