트리와 이진 탐색 트리(1)

1. 트리란?

- 트리는 난이도로 보면 자료구조 중 제일 높음

-> 트리를 유지보수하는 로직이 복잡하더라도, 참고하는 편이 좋음

 

- 면접에서 트리의 특정 로직을 구현하라고 할 수 있음 

 

- 트리는 노드와 브랜치라는 것을 사용해서 사이클을 이루지 않도록 구성함

-> 트리는 굉장히 넓은 범위로 정의를 한 것임

-> 그 중에서 우리가 익혀야 하는 것은 이진 트리 구조임  

 

- 노드가 있을 때, 최상단 노드는 루트 노드임

-> 이진 트리는 노드의 최대 브랜치가 2개

-> 이진 트리 중에서 이진 탐색 트리(Binary Search Tree)가 있음  

 

- 이진 탐색 트리 노드의 왼쪽 노드는 작은 값이,  

  오른쪽 노드는 큰 값이 들어감  

-> 이진 트리 중에서도 이진 탐색 트리를 많이 씀 

 

- 최상단에 위치한 노드는 Level 0,  두번째는 Level 1, 세번째는 Level 2

 

- 노드의 상위 노드를 Parent Node,

  노드의 하위 노드를 Child Node라고 함

-> Child Node끼리는 Sibling이라고 함  

 

- Child Node가 하나도 없는 노드를 

  leaf node 혹은 terminal node라고 함  

 

- 이진 탐색 트리가 굉장히 많이 쓰임

-> 이진 탐색 트리를 잘 알아야 함  

 

- BST는 검색에서 O(logn)의 시간 복잡도를 가짐  

 

2. 이진 탐색 트리 구현

public class NodeMgmt{
  public class 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){
       if(this.head == null){
           this.head = new Node(data); 
       }else{
         Node findNode = this.head;
         
         while(true){
           if(data < findNode.value){
             if(findNode.left != null){
                findNode = findNode.left;
             }else{
                findNode.left = new Node(data);
                break;
             }
           }else{
             if(findNode.right != null){
                findNode = findNode.right;
             }else{
                findNode.right = new Node(data);
                break;
             }
           }
           return true;
        }

 

참고

- 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online편