트리와 이진 탐색 트리 - 1

트리와 이진 탐색 트리 - 1

 

트리 (Tree) 구조

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

 

용어

• Node : 트리에서 데이터를 저장하는 기본 요소
• Root Node : 트리 맨 위에 있는 노드 (Root)
• Level : 최상위 노드를 Level 0 으로, 하위 노드로 연결된 노드의 깊이를 나타냄
• Parent Node : 어떤 노드의 상위 레벨에 연결된 노드 (부모 노드)
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드 (자식 노드)
• Leaf Node (Terminal Node) : Child Node가 없는 노드
• Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

 

 

이진 트리와 이진 탐색 트리 (Binary Search Tree)

이진 트리 : 노드의 최대 Branch가 2인 트리
이진 탐색 트리 (Binary Search Tree, BST) : 왼쪽 노드는 작은 값, 오른쪽 노드는 큰 값을 가지고 있음

https://blog.penjee.com/wp-content/uploads/2015/11/binary-search-tree-insertion-animation.gif

 

 

이진 탐색 트리의 장점과 사용

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

 

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

https://blog.penjee.com/wp-content/uploads/2015/11/binary-search-tree-sorted-array-animation.gif

 

구현

public class mgmtNode {
    Node head = null;
    
    public calss Node {
        Node left;
        Node right;
        int value;
        
        public Node(int data) {
            this.value = data;
            this.left = null;
            this.right = null;
        }
    }
    
    
    /*
    * 이진 탐색 트리 조건에 부합하게 넣기
    */
    public boolean insertNode(int data) {
        // Node 가 없을 경우
        if(this.head == null) {
            this.head = new Node(data);
            
        // Node 가 있을 경우    
        } else {
            Node findNode = this.head;
            while(true) {
                // Node의 왼쪽 경우 (작아야함)
                if(data < findNode.value) {
                    if(findNode.left != null) {
                        findNode = findNode.left;
                        
                    } else {
                        findNode.left = new Node(data);
                        break;
                    }
                    
                // Node의 오른쪽 경우 (커야함)    
                } else {
                    if(findNode.right != null) {
                        findNode = findNode.right;
                        
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }
    
    
    /*
    * 탐색
    */
    public Node search(int data) {
        // Node 가 없을 경우
        if(this.head == null) {
            return null;
            
        // Node 가 있을 경우    
        } else {
            Node findNode = this.head;
            while(findNode != null) {
                if(findNode.value == data) {
                    return findNode;
                    
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                    
                } else {
                    findNode = findNode.right;
                }
            }
            return null;
        }
    }
}



mgmtNode node = new mgmtNode();
node.insertNode(3);
node.insertNode(4);
node.insertNode(2);
node.insertNode(6);
node.insertNode(5);

Node testNode = node.search(3);
System.out.println(testNode.right.value);    // 4

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스