Java 자료구조(Data Structure) - Binary Search Tree & Tree traversal

Binary Search Tree

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다.

많은 트리의 모습 중 가장 간단하고 많이 사용하는 이진트리(binary tree)와 이진 탐색 트리(binary search tree)에 대해 알아보자.

먼저 이진 트리(Binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다. 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

이진 탐색 트리(Binary Search Tree)

이진 탐색이란 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나이다. 이진 탐색 알고리즘은 오름차순으로 정렬된 데이터를 같은 크기의 두 부분으로 나눈 후 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘이다.

1. 전체 데이터에서 중간(Root)에서 내가 찾고자 하는 값이 있는지 확인한다.
2. 중간값이 내가 찾고자 하는 값이 아닐 경우 오름차순으로 정렬된 데이터에서 중간값보다 큰 값인지 작은값인지 판단한다.
3. 찾고하 하는 값이 중간값보다 작은 값일 경우 데이터의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 탐색을 반복 수행한다.
4. 찾고자 하는 값이 중간값보다 큰 값일 경우 데이터의 중간값의 다음값부터 맨 마지막까지를 탐색범위로 잡고 탐색을 반복 수행한다.

이진 탐색 트리의 특징

각 노드에 중복되지 않는 키(key)가 있다. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있고 오른쪽 서브 트리는 큰 키를 갖는 노드들로 이루어져 있다. 즉 이진탐색트리(Binary Search Tree)는 모든 왼쪽 자신의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나  부모보다 큰 값을 가지는 특징이 있다.

이진 탐색 트리는 균형 잡힌 트리가 아닐 때 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제이다. 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.

 

이진 탐색 트리의 탐색 과정

이진 탐색 트리는 기존 이진 트리보다 탐색이 빠르다는 장점이 있다. 이진 탐색 트리의 탐색은 아래와 같은 과정을 거친다.

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 만약 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.

위와 같은 트리에서 5라는 값을 찾고자 한다면 제일 처음에는 루트 노드와 값을 비교한다.

1. 루트 노드가 10이므로 루트 노드보다 작기 때문에 왼쪽 서브트리로 탐색을 시작한다.
2. 이후 노드 7을 기준으로 비교해도 작기 때문에 왼쪽 서브틜로 탐색을 진행한다.
3. 이어 만난 값이 찾는 값이므로 탐색을 종료한다.

참고로 트리 안에 찾고자 하는 값이 없더라도 최대 트리의 높이인 h번 만큼의 연산 및 탐색이 진행된다.

 

이진 탐색 트리에서 노드의 추가

이진 탐색 트리에서 노드를 추가할 때 노드의 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽 서브트리에 추가한다.

위와 같은 트리에서 2라는 값을 삽입하고자 한다면 제일 처음 루트 노드와 값을 비교한다.

1. 10보다 작기 때문에 왼쪽 서브트리로 삽입을 위한 비교를 시작한다.
2. 이후 마주친 노드는 7 이므로 7을 기준으로 왼쪽 서브 트리로 삽입을 위한 비교를 시작한다.
3. 이후 마주친 노드는 5 이므로 5를 기준으로 왼쪽 서브 트리로 삽입을 위한 비교를 시작한다.
4. 이후 마주친 노드는 3 이므로 3을 기준으로 왼쪽 서브 트리로 삽입을 위한 비교를 시작한다.
5. 3은 하위 노드가 존재하지 않으므로 3의 좌측 노드에 2를 추가한다.

이진 탐색 트리에서 노드의 삭제

아래의 그림에서 2 노드처럼 삭제할 노드가 리프 노드인 경우 자식 노드가 없기 때문에 그냥 삭제하면 된다.

만약 3을 제거한다면 삭제할 노드의 부모 노드와 삭제할 노드의 자식 노드를 연결해주면 된다. 즉 3을 키로 가지는 노드를 제거하면서 기존의 2라는 키를 가진 노드의 위치를 삭제된 데이터의 위치로 이동한다.

다시 첫 번째 그림에서 5를 삭제 한다면 자식노드가 두개이므로 삭제할 노드와 대체할 노드를 서로 교환한다. 5를 기준으로 좌측 자식 노드는 3, 우측 자식 노드는 6이다. 좌측의 3과 5의 위치를 변경한다. 변경 후 자식노드는 2 하나밖에 없으므로 5를 삭제한다.

반응형

Tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다. 트리를 순회하는 방법으로는 전위 순회, 중위 순회, 후위 순회 3가지가 있다. 순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.

 

전위 순회(preorder traverse)

전위 순회에서 가장 먼저 방문하는 노드는 루트이다. 루트에서 시작해 왼쪽 노드들을 차례대로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다. 즉 부모 노드가 제일 먼저 방문되는 순회 방식이다. 전위순회는 주로 트리를 복사할 때 사용한다.

/* 최소한의 기능만 구현되어 있다.
   자식 노드가 없는 경우는 node == null이라고 가정한다.
   이미 이진 트리는 구현되어 있다고 가정한다. */

class Node {
  String data;
	Node left;
	Node right;

	public Node getLeft() {
      return left;
    }

    public String getData() {
      return data;
    }

    public Node getRight() {
      return right;
    }
}

public ArrayList<String> preOrder(Node node, ArrayList<String> list) {
    if (node != null) {
      list.add(node.getData());
      list = preOrder(node.getLeft(), list);
      list = preOrder(node.getRight(), list);
    }
    return list;
}

탐색 종료 시 list의 값 -> ["A", "B", "D", "H", "I", "E", "J", "K", "C", "F", "L", "M", "G", "N", "O"]

 

중위 순회 (inorder traverse)

중위 순회는 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다. 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식이다. 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.

/* 최소한의 기능만 구현되어 있다.
   자식 노드가 없는 경우는 node == null이라고 가정한다.
   이미 이진 트리는 구현되어 있다고 가정한다. */

class Node {
  String data;
	Node left;
	Node right;

	public Node getLeft() {
      return left;
    }

    public String getData() {
      return data;
    }

    public Node getRight() {
      return right;
    }
}

public ArrayList<String> inOrder(Node node, ArrayList<String> list) {
    if (node != null) {
      list = inOrder(node.getLeft(), list);
      list.add(node.getData());
      list = inOrder(node.getRight(), list);
    }
    return list;
}

탐색 종료 시 list의 값 -> ["H", "D", "I", "B", "E", "J", "K", "A", "L", "F", "M", "C", "N", "G", "O"]

 

후위 순회 (postorder traverse)

후위 순회는 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여 루트를 거치지 않고 오른쪽으로 이동해 순회한뒤 제일 마지막에 루트를 방문한다. 후위 순위는 자식노드가 먼저 삭제 되어야 상위 노드를 삭제 할 수 있는 트리를 삭제할 때 사용한다.

/* 최소한의 기능만 구현되어 있다.
   자식 노드가 없는 경우는 node == null이라고 가정한다.
   이미 이진 트리는 구현되어 있다고 가정한다. */

class Node {
  String data;
	Node left;
	Node right;

	public Node getLeft() {
      return left;
    }

    public String getData() {
      return data;
    }

    public Node getRight() {
      return right;
    }
}

public ArrayList<String> postOrder(Node node, ArrayList<String> list) {
    if (node != null) {
      list = postOrder(node.getLeft(), list);
      list = postOrder(node.getRight(), list);
      list.add(node.getData());
    }
    return list;
}

탐색 종료 시 list의 값 -> ["H", "I", "D", "J", "K", "E", "B", "L", "M", "F", "N", "O", "G", "C", "A"]