190121 자료구조 - 이진 트리

2019-01-21

자료구조 - 이진 트리

트리의 구조

  • 정점(vertex)/노드(node): 트리에서 자료를 보관하는 곳

  • 간선(edge)/링크(link): 정점에서 다른 정점으로 가는 경로

  • 레벨(level): 루트부터 노드까지 걸리는 거리(root의 레벨이 1)

  • 높이(height)/깊이(depth): 가장 높은 레벨

  • 차수(degree): 특정 노드의 자식 수

  • 부모(parent): 레벨 N인 노드와 연결된 레벨 N-1에 있는 노드

  • 자식(son): 레벨 N인 노드와 연결된 레벨 N+1에 있는 노드

  • 형제(sibling): 같은 부모를 가지는 노드

  • 조상(ancestors): 자신에게 오기 위한 경로에 있는 모든 노드

  • 후손(descendant): 자신을 출발로 갈 수 있는 모든 노드

  • 트리의 차수: 트리의 모든 노드 중 가장 높은 차수

  • 단말(terminal)/잎(leaf): 차수가 0인 노드(==자식이 없는 노드)

이진 트리
  • 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
  • 이진 탐색 트리 / 힙의 구현에 이용된다.
  • 효율적인 검색과 정렬이 가능하다
  • 포화 이진 트리 : 마지막 레벨까지 모든 노드가 차 있는 이진 트리
  • 완전 이진 트리 : 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리
  • 편향트리 : 한쪽으로 기울어진 트리
이진 트리의 순회
  • 전위 순회
    • 루트-왼쪽 서브트리-오른쪽 서브트리
  • 중위 순회
    • 왼쪽 서브트리-루트-오른쪽 서브트리
  • 후위 순회
    • 왼쪽 서브트리-오른쪽 서브트리-루트
이진 트리의 구현 - 이진 탐색 트리
  • 이진 탐색 트리

    • 주어진 노드의 값보다 작은 자식은 왼쪽에, 큰 원소는 오른쪽에

      • 숫자,날짜,문자열….

    • 이진 탐색 트리 구현

         class Node{
     private char data;
     private Node left;
     private Node right;
          
     public Node(char data) {
       this.data = data;
     }
     public char getData() {
       return data;
     }
     public void setData(char data) {
       this.data = data;
     }
     public Node getLeft() {
       return left;
     }
     public void setLeft(Node left) {
       this.left = left;
     }
     public Node getRight() {
       return right;
     }
     public void setRight(Node right) {
       this.right = right;
     }
   }

    • 이진 탐색 트리에서 값 찾기

        public static void searchBST(Node node, char key) { // node는 이원 탐색 트리, key는 탐색 키 값
    if(node == null) { // 이원탐색트리가 공백이면 종료
      System.out.println("탐색 실패");
      return;
    }
    if(node.getData() == key) { // 노드의 데이터값이 key값과 일치하면 탐색 성공후 종료
      System.out.println("탐색 성공");
      return;
    }
    if(node.getData() < key) { // 노드의 데이터값보다 키값이 크다면 
      searchBST(node.getRight(), key); //오른쪽 서브 트리에서 탐색을 실시
    }else { // 노드의 데이터값보다 키값이 작다면
      searchBST(node.getLeft(), key); // 왼쪽 서브 트리에서 탐색을 실시
    }
  }

    • 이진 탐색 트리에 값 삽입하기

        public static void insertBST(Node node, char key) { //node는 이원탐색트리, key는 삽입하려는 키 값
    Node p = node;
    Node q = null;
         
    while(p != null) { //노드가 null이 나올때까지 즉 이진 탐색 트리의 끝까지 검사 한다.
      if(key == p.getData()) { // 삽입하려는 키값이 이미 있는지 검사한다.
        System.out.println("실패 : key값이 있음");
        return;
      }
      q = p; //해당 노드의 부모노드를 기억시킨다.
      if(p.getData() < key) { // 키값보다 노드의 데이터가 작다면
        p = p.getRight(); // 오른쪽 서브트리로 이동한다.
      }else { // 키값보다 노드의 데이터가 크다면
        p = p.getLeft(); // 왼쪽 서브트리로 이동한다.
      }
    }
    Node newNode = new Node(key); // 새로운 key값을 가진 노드를 생성한다.
         
    if(node == null) { // 최초부터 공백 이원탐색 트리라면 가장 루트로 만든다.
      node = newNode;
    }else if(key < q.getData()) { //아까 기억시킨 부모 노드의 데이터보다 key값이 작다면
      q.setLeft(newNode); //새로 왼쪽 서브트리로 만든다.
    }else { // 아까 기억시킨 부모 노드의 데이터보다 key값이 크다면
      q.setRight(newNode); // 새로 오른쪽 서브트리로 만든다.
    }
  }

    • 이진 탐색 트리 값 삭제하기

        public static void deleteBST(Node node, char key) {
    Node p = node;
    Node deleteNode = null; // 삭제할 key값을 가진 노드
    Node parent = null;  // 삭제할 노드의 부모 노드
         
    while(p != null) {
      if(p.getData() == key) { // 키값을 찾았으면
        deleteNode = p; // 해당 노드릉 삭제노드로 지정
        break;
      }
      parent = p;// 노드의 부모 노드를 기억
      if(p.getData() < key) { // 키값보다 노드의 데이터가 작다면
        p = p.getRight(); // 오른쪽 서브트리로 이동한다.
      }else { // 키값보다 노드의 데이터가 크다면
        p = p.getLeft(); // 왼쪽 서브트리로 이동한다.
      }
    }
         
    if(deleteNode == null) {return;} // 삭제할 원소가 없으면 종료
         
    if(deleteNode.getLeft() == null && deleteNode.getRight() == null) { 
        // 1. 삭제할 노드가 리프 노드의 경우
      if(parent.getLeft() == deleteNode) { // 삭제할 노드가 부모의 왼쪽 노드라면
        parent.setLeft(null);
      }else {// 삭제할 노드가 부모의 오른쪽 노드라면
        parent.setRight(null);
      }
    }else if(deleteNode.getLeft() == null || deleteNode.getRight() == null) {
        // 2. 삭제할 노드의 차수가 1인경우
      if(deleteNode.getLeft() != null) { // 삭제할 노드 왼쪽에 노드가 있다면
        if(parent.getLeft() ==deleteNode ) { // 삭제할 노드가 부모노드의 왼쪽이라면
          parent.setLeft(deleteNode.getLeft()); // 부모노드 왼쪽에 삭제할 노드의 왼쪽 서브트리를 붙인다.
        }else { // 삭제할 노드가 부모노드의 오른쪽 이라면
          parent.setRight(deleteNode.getLeft());// 부모노드 오른쪽에 삭제할 노드의 왼쪽 서브트리를 붙인다.
        }
      }else { // 삭제할 노드가 오른쪽 에 노드가 있다면
        if(parent.getLeft() ==deleteNode ) { // 삭제할 노드가 부모노드의 왼쪽이라면
          parent.setLeft(deleteNode.getRight()); // 부모노드 왼쪽에 삭제할 노드의 왼쪽 서브트리를 붙인다.
        }else { // 삭제할 노드가 부모노드의 오른쪽 이라면
          parent.setRight(deleteNode.getRight());// 부모노드 오른쪽에 삭제할 노드의 왼쪽 서브트리를 붙인다.
        }
      }
    }else { 
        // 3. 삭제할 노드의 차수가 2인경우
      Node q = deleteNode.getLeft(); // 삭제할 노드의 왼쪽 서브트리에서 최대 키값을 가져온다.
           
      deleteNode.setData(q.getData()); // 왼쪽 서브트리에서 가장 큰값을 삭제할 노드에 데이터에 넣는다.
      deleteBST(deleteNode.getLeft(), deleteNode.getData()); // 삭제할 노드 왼쪽의 노드를 삭제한다.
    }
  }

    • 탐색/삽입/삭제연산의 시간 복잡도

      • 평균: O(log n)
      • 최악: O(n) (편향 트리인 경우) ->AVL 트리로 해결
AVL 트리(Adelson-Velskii and Landis’ tree)
  • 어떤 노드든 모든 자식의 깊이 차이가 1을 넘지 않도록 만든다
    • 노드에 삽입/삭제 연산시 왼쪽과 오른쪽의 부분 트리가 균형이 맞는지 확인하고,
    • 만약 균형이 맞지 않는다면 조건에 맞게 재배열한다.
힙
  • 최소 힙: 부모 노드가 자식 노드보다 항상 작은 트리 구조
  • 최대 힙: 부모 노드가 자식 노드보다 항상 큰 트리 구조
  • 순서를 가진 큐/리스트의 가장 작은/큰 원소에 빠르게 접근해야 하는 경우 특히 더 유용하다.
  • 완전 이진 트리이기 때문에 배열로 구현이 가능하다.
  • 힙의 삽입/삭제
    • 삽입: 최고 깊이에서 가장 오른쪽에 삽입한 후, 부모 노드가 자신보다 더 크거나 작은 경우 부모 노드와 자식 노드를 계속 swap한다.(bottom-up 방식)
    • 삭제: 루트 값을 꺼낸 후, 루트 노드를 최고 깊이에서 가장 오른쪽 노드로 대체한다.
      • 힙의 성질을 유지하기 위해 루트 노드에서부터 자식 노드들을 top-down하면서 자신보다 더 큰/작은 자식 노드가 있으면 자신과 자식노드를 swap한다.
      • 만약 왼쪽 자식과 오른쪽 자식이 둘 다 자신보다 작다면, 둘 중에 더 큰/작은 자식과 swap한다.
자료 출처