트리

트리

트리 관련 용어

💬  순서 트리와 무순서 트리

  ◽  형제 노드의 순서가 있는지 없는지에 따라 트리를 구분할 수 있다.

 

순서 트리 탐색

너비 우선 탐색

💬  낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려간다.

너비 우선 탐색

💬  A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L

 

깊이 우선 탐색

💬  리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다.

💬  리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아간 후, 순차적으로 자식 노드로 탐색을 이어간다.

전위 순회 (Preorder)

💬  노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

💬  A -> B ->D ->H ->E ->I -> J -> C -> F -> K -> L -> G

 

중위 순회 (Inorder)

💬  왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

💬  H -> D -> B -> I -> E -> J -> A -> K -> F -> L -> C -> G

 

후위 순회 (Postorder)

💬  왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

💬  H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A

 

이진트리와 이진검색트리

이진트리

💬  노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리라고 한다.

이진트리

 

완전이진트리

💬  조건

    ◽  마지막 레벨을 제외한 레벨은 노드를 가득 채운다.

    ◽  마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없다.

완전이진트리

💬  따라서, n개의 노드를 저장할 수 있는 완전이진트리의 높이는 logn이다.

 

이진검색트리

💬  조건

    ◽  어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.

    ◽  오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.

    ◽  같은 키 값을 갖는 노드는 없다.

💬  이진검색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 얻을 수 있으며, 단순하고, 노드의 삽입이 쉽다는 점으로 폭넓게 사용된다.

 

이진검색트리 만들기

import java.util.Comparator;

public class BinTree<K, V> {
  // 노드
  static class Node<K, V> {
    private K key;             // 키 값
    private V data;            // 데이터
    private Node<K, V> left;   // 왼쪽 자식 노드
    private Node<K, V> right;  // 오른쪽 자식 노드
    
    // 생성자
    Node(K key, V data, Node<K, V> left, Node<K, V> right) {
      this.key = key;
      this.data = data;
      this.left = left;
      this.right = right;
    }
    
    // 키 값을 반환
    K getKey() {
      return key;
    }
    
    // 데이터를 반환
    V getValue() {
      return data;
    }
    
    // 데이터를 출력
    void print() {
      System.out.println(data);
    }
  }
  
  private Node<K, V> root;                          // 루트
  private Comparator<? super K> comparator = null;  // 비교자
  ...
}

 

노드 클래스 Node<K, V>

💬  이진트리의 개별 노드를 나타내는 클래스이다.

    ◽  key : 키 값

    ◽  data : 데이터

    ◽  left : 왼쪽 자식 노드에 대한 참조 (왼쪽 포인터)

    ◽  right : 오른쪽 자식 노드에 대한 참조 (오른쪽 포인터)

 

이진검색트리 클래스 BinTree<K, V>

◽  root : 루트에 대한 참조를 보존, 유지하는 필드다.

◽  comparator : 키 값의 대소 관계를 비교하는 비교자이다.

 

생성자

// 생성자
public BinTree() {
  root = null;
}

// 생성자
public BinTree(Comparator<? super K> c) {
  this();
  comparator = c;
}

BinTree()

◽  노드가 하나도 없는 이진검색트리를 생성하는 생성자이다.

◽  노드 키 값의 대소 관계를 판단할 때 자연 순서에 따라 수행한다.

◽  비교자를 설정하지 않으므로 필드 comparator 값은 널이 된다.

 

BinTree(Comparator<? super K> c)

◽  노드의 대소 관계를 판단할 때 전달받은 비교자에 의해 아래와 같이 수행한다.

    ◽  this()에 의해 인수를 전달받지 않는 생성자 BinTree()를 호출한다. root가 널인 이진검색 트리를 생성한다.

    ◽  필드 comparator에 전달받은 c를 설정한다.

 

두 키 값을 비교하는 comp 메서드

// 두 키 값을 비교
private int comp(K key1, K key2) {
  return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2)
                         : comparator.compare(key1, key2);
}

◽  이 메서드는 두 키 값 key1과 key2를 비교하여 아래 값을 반환한다.

    ◽  key1 > key2 -> 양수

    ◽  key1 < key2 -> 음수

    ◽  key1 == key 2 -> 0

◽  비교자 comparator가 null인 경우

((Comparable<K>)key1).compareTo(key2)

    ◽  key1을 Comparable<K> 인터페이스형으로 형변환하고, compareTo 메서드를 호출하여 key2와 비교한다.

◽  비교자 comparator가 null이 아닌 경우

comparator.compare(key1, key2)

 

키 값으로 검색하는 search 메서드

이진검색트리에서 노드를 검색하는 과정

💬  알고리즘은 아래와 같다.

  ◽  1. 루트부터 선택하여 검색을 진행한다. 여기서 선택하는 노드를 p라고 한다.

  ◽  2. p가 널이면 검색에 실패한다.

  ◽  3. 검색하는 값 key와 선택한 노드 p의 키 값을 비교하여

    ◽  값이 같으면 검색에 성공(검색 종료)합니다.

    ◽  key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입한다. (왼쪽으로 검색 진행)

    ◽  key가 크면 선택한 노드에 오른쪽 자식 노드를 대입한다. (오른쪽으로 검색 진행)

  ◽  4. 2번 과정으로 돌아간다.

// 키에 의한 검색
public V search(K key) {
  Node<K, V> p = root;                   // 루트에 주목
  
  while (true) {
    if (p == null)                       // 더 이상 진행하지 않으면
      return null;                       // 검색 실패
    int cond = comp(key, p.getKey());    // key와 노드 p의 키를 비교
    if (cond == 0)                       // 같으면
      return p.getValue();               // 검색 성공
    else if (cond < 0)                   // key 쪽이 작으면
      p = p.left;                        // 왼쪽 서브 트리에서 검색
    else                                 // key 쪽이 크면
      p = p.right;                       // 오른쪽 서브 트리에서 검색
  }
}

 

노드를 삽입하는 add 메서드

이진검색트리에 노드를 삽입하는 과정

💬  알고리즘은 아래와 같다.

  ◽  1. 루트를 선택한다. 여기서 선택하는 노드를 node로 한다.

  ◽  2. 삽입할 키 key와 선택 노드 node의 키 값을 비교한다. 값이 같다면 삽입에 실패한다 (종료).

      ◽ 값이 같지 않은 경우 key 값이 삽입할 값보다 작으면

          ◽  왼쪽 자식 노드가 없는 경우에는 [ a ] 경우와 같이 노드를 삽입한다 (종료).

          ◽  왼쪽 자식 노드가 있는 경우에는 선택한 노드를 왼쪽 자식 노드로 옮긴다.

      ◽ key 값이 삽입할 값보다 크면

          ◽  오른쪽 자식 노드가 없는 경우에는 [ b ] 경우와 같이 노드를 삽입한다 (종료).

          ◽  오른쪽 자식 노드가 있는 경우에는 선택한 노드를 오른쪽 자식 노드로 옮긴다.

  ◽  3. 2번으로 돌아간다.

// node를 루트로 하는 서브 트리에 노드<K, V>를 삽입
private void addNode(Node<K, V> node, K key, V data) {
  int cond = comp(key, node.getKey());
  if (cond == 0)
    return;                                   // key가 이진검색트리에 이미 있음
  else if (cond < 0) {
    if (node.left == null)
      node.left = new Node<K, V>(key, data, null, null);
    else
      addNode(node.left, key, data);          // 왼쪽 서브 트리에 주목
  } else {
    if (node.right == null)
      node.right = new Node<K, V>(key, data, null, null);
    else
      addNode(node.right, key, data);        // 오른쪽 서브 트리에 주목
  }
}

// 노드를 삽입
public void add(K key, V data) {
  if (root == null)
    root = new Node<K, V>(key, data, null, null);
  else
    addNode(root, key, data);
}

 

노드를 삭제하는 remove 메서드

💬  자식 노드가 없는 노드를 삭제하는 경우

자식 노드가 없는 노드를 삭제하는 과정

  ◽  삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 null로 한다.

  ◽  삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 null로 한다.

💬  자식 노드가 1개인 노드를 삭제하는 경우

자식 노드가 1개인 노드를 삭제하는 과정

◽  삭제 대상 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.

◽  삭제 대상 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.

💬  자식 노드가 2개인 노드를 삭제하는 경우

자식 노드가 2개인 노드를 삭제하는 과정

◽  1. 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다.

◽  2. 검색한 노드를 삭제 위치로 옮긴다 (검색한 노드의 데이터를 삭제 대상 노드 위치로 복사한다).

◽  3. 옮긴 노드를 삭제한다. 이때

    ◽  옮긴 노드에 자식이 없으면 '자식 노드가 없는 노드의 삭제 순서'에 따라 노드를 삭제한다.

    ◽  옮긴 노드에 자식이 1개만 있으면 '자식 노드가 1개 있는 노드의 삭제 순서'에 따라 노드를 삭제한다.

// 키 값이 key인 노드를 삭제
public boolean remove(K key) {
  Node<K, V> p = root;                   // 스캔 중인 노드
  Node<K, V> 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) {                    // key 쪽이 작으면
        isLeftChild = true;              // 왼쪽 자식으로 내려감
        p = p.left;                      // 왼쪽 서브 트리에서 검색
      } else {                           // key 쪽이 크면
        isLeftChild = false;             // 오른쪽 자식으로 내려감
        p = p.right;                     // 오른쪽 서브 트리에서 검색
      }
    }
  }
  
  if (p.left == null) {                  // p에는 왼쪽 자식이 없음
    if (p == root)
      root = p.right;
    else if (isLeftChild)
      parent.left = p.right;             // 부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
    else
      parent.right = p.right;            // Ex) 7을 삭제하는 경우
  } else if (p.right == null) {          // p에는 오른쪽 자식이 없음
    if (p == root)
      root = p.left;
    else if (isLeftChild)
      parent.left = p.left;              // Ex) 1을 삭제하는 경우
    else
      parent.right = p.left;             // 부모의 오른쪽 포인터가 왼쪽 자식을 가리킴
  } else {                               // Ex) 5를 삭제하는 경우
    parent = p;
    Node<K, V> left = p.left;            // 서브 트리 가운데 가장 큰 노드
    isLeftChild = true;
    while (left.right != null) {         // 가장 큰 노드 left를 검색
      parent = left;
      left = left.right;
      isLeftChild = false;
    }
    p.key = left.key;
    p.data = left.data;
    if (isLeftChild)
      parent.left = left.left;           // left를 삭제
    else
      parent.right = left.left;          // left를 삭제
  }
  return ture;
}

 

모든 노드를 출력하는 print 메서드

💬  모든 노드의 키 값을 오름차순으로 출력하기 위해 중위 순회 방법으로 트리를 검색한다.

// node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력
private void printSubTree(Node node) {
  if (node != null) {
    printSubTree(node.left);                 // 왼쪽 서브 트리를 키 값의 오름차순으로 출력
    System.out.println(node.key + " " + node.data);  // node를 출력
    printSubTree(node.right);                // 오른쪽 서브 트리를 키 값의 오름차순으로 출력
  }
}

// 모든 노드를 키 값의 오름차순으로 출력
public void print() {
  printSubTree(root);
}