트리 (Tree) - 1

트리란?

• Node와 Branch를 이용하여, 사이클을 이루지 않도록 구성한 데이터 구조이다.

• 이진 트리(Binary Tree)의 경우 탐색 알고리즘 구현에 많이 사용된다.
  - 최대 2개의 Branch를 갖는다.

• Node : 데이터와 브랜치 정보를 저장

• Root Node : 최상단 노드 (Level 0)

• Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결되 각 Node의 깊이

• Depth : 트리에서 Node가 가질 수 있는 최대 깊이

• Parent Node : 어떤 노드에 Branch로 연결된 상위 노드

• Child Node : 어떤 노드에 Branch로 연결된 하위 노드

• Siblings (Brother Node) : 동일한 Parent Node를 갖는 노드

• Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
  

이진 트리와 이진 탐색 트리

1. 이진 트리 (Binary Tree) : 노드의 최대 Branch가 2개인 트리
2. 이진 탐색 트리 (Binary Search Tree, BST)
   • 노드의 최대 Branch가 2개인 트리
   • 노드의 왼쪽 Child Node에는 해당 노드의 값보다 작은 값, 오른쪽 Child Node에는 해당 값보다 큰 값을 갖는다.

이진 탐색 트리의 장점

배열과 비교 시 탐색 속도가 빠르다.

출처 : https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

이진 탐색 트리 구현

public class BinaryTreeOperation {

    // Node Class 생성
    public static class NodeMgmt {
        Node root = null;
        public class Node {
            Node left;
            Node right;
            int value;

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

        // Node 생성 Method
        public boolean insertNode(int data) {
            // case 1. Node가 하나도 없을 때
            if(this.root == null) {
                this.root = new Node(data);
                return true;
            }
            // case 2. Node가 하나 이상 있을 때}
            else {
                Node findNode = this.root;
                while(true) {
                    // case 2-1. 현재 Node의 왼쪽 Child Node가 될 때
                    if(findNode.value > data) {
                        // case 2-1-1. 왼쪽 Child Node에 이미 값이 있는 경우
                        if(findNode.left != null) {
                            findNode = findNode.left;           // findNode를 바꿔주고 다시 검색
                        }
                        // case 2-1-2. 왼쪽 Child Node에 값이 없는 경우
                        else {
                            findNode.left = new Node(data);     // 현재 데이터로 Node 생성
                            return true;
                        }
                    }
                    // case 2-2. 현재 Node의 오른쪽 Child Node가 될 때
                    else {
                        // case 2-2-1. 오른쪽 Child Node에 이미 값이 있는 경우
                        if(findNode.right != null) {
                            findNode = findNode.right;          // findNode를 바꿔주고 다시 검색
                        }
                        // case 2-2-2. 오른쪽 Child Node에 값이 없는 경우
                        else {
                            findNode.right = new Node(data);     // 현재 데이터로 Node 생성
                            return true;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        NodeMgmt tree = new NodeMgmt();

        boolean flag = false;

        flag = tree.insertNode(1);
        System.out.println("flag : " + flag);		// flag : true
        flag = tree.insertNode(2);
        System.out.println("flag : " + flag);		// flag : true
        flag = tree.insertNode(3);
        System.out.println("flag : " + flag);		// flag : true
        flag = tree.insertNode(4);
        System.out.println("flag : " + flag);		// flag : true
    }
}