2015년 2월 16일 월요일

Binary Search Tree (이진 탐색 트리)

Binary Search Tree는 최대 2개의 자식 노드를 가질 수 있는 Binary Tree의 한 종류로 다음의 특징을 갖는다


  1. 왼쪽 자식 노드의 키 값은 자신보다 작거나 같다.
  2. 오른쪽 자식 노드의 키 값은 자신보다 크거나 같다.
위의 특징은 모든 서브 트리에도 동일하게 적용되어야 한다.
예를 들어 아래의 트리는 Binary Search Tree 이다

        10
    8        15
  5  9   12   18
2                  20

Binary Search Tree를 구현해보면 재귀 알고리즘에 대한 훈련에 도움이 많이 된다.

트리의 노드는 다음과 같이 코드로 표현할 수 있다.
다양한 데이터를 표현할 수 있도록 Generic을 사용하였지만, 알고리즘의 이해를 위해서는 주로 int형을 사용한다.

public class TreeNode<T> {
 private T data;
 private TreeNode<T> left;
 private TreeNode<T> right;

 public TreeNode(T data) {
  this.data = data;
 }

 public T getData() {
  return data;
 } 

 public void setData(T data) {
  this.data = data;
 }

 public TreeNode<T> getLeft() {
  return left;
 }

 public void setLeft(TreeNode<T> left) {
  this.left = left;
 }

 public TreeNode<T> getRight() {
  return right;
 }

 public void setRight(TreeNode<T> right) {
  this.right = right;
 }
}

data: 노드가 가진 키 값
left: 왼쪽 자식의 참조
right: 오른쪽 자식의 참조

1. 트리의 순회 (traverse)

트리의 모든 노드를 조회하는 것을 순회(traverse)라고 한다. 순회에는 3가지 방법이 있는데, 각각 다음과 같은 순서로 조회한다.

Pre-Order: 자신 -> 왼쪽 자식 -> 오른쪽 자식
In-Order: 왼쪽 자식 -> 자신 -> 오른쪽 자식
Post-Order: 왼쪽 자식 -> 오른쪽 자식 -> 자신

여기서는 Pre-Order를 사용할 것이다.

public class BinarySearchTree {
 public void traversePreOrder(TreeNode<Integer> root) {
  if(root == null)
   return;
  
  System.out.print(root.getData() + " ");
  traversePreOrder(root.getLeft());
  traversePreOrder(root.getRight());
 }
}

2. 노드 삽입 (insertion)

노드의 삽입은 BST의 특징을 잘 이해하면 구현하기 어렵지 않다. 즉 왼쪽 자식은 자신보다 키 값이 작거나 같고, 오른쪽 자식은 자신보다 키 값이 크거나 같아야한다.


public class BinarySearchTree {
 public void traversePreOrder(TreeNode<Integer> root) {
  if(root == null)
   return;
  
  System.out.print(root.getData() + " ");
  traversePreOrder(root.getLeft());
  traversePreOrder(root.getRight());
 }

 public void insert(TreeNode<Integer> root, <Integer> node) {
  if(root == null || node == null)
   return; 
     
  if(node.getData() >= root.getData()) {
   if(root.getRight() == null) {
    root.setRight(node);
    return;
   }
   
   insert(root.getRight(), node);
  }
  
  else if (node.getData() < root.getData()) {
   if(root.getLeft() == null) {
    root.setLeft(node);
    return;
   }
   insert(root.getLeft(), node);
  } 
 }
}
루트 노드로부터 삽입하려는 노드의 키값을 비교하여 값이 작으면 왼쪽으로 이동 (재귀 호출을 통해)하고 값이 크거나 같으면 오른쪽으로 이동한다.

3. 노드 검색 (search)

노드 검색도 BST의 특징을 잘 이해한다면 노드의 삽입과 같은 원리로 쉽게 구현할 수 있다.


public class BinarySearchTree {
 public void traversePreOrder(TreeNode<Integer> root) {
  if(root == null)
   return;
  
  System.out.print(root.getData() + " ");
  traversePreOrder(root.getLeft());
  traversePreOrder(root.getRight());
 }

 public void insert(TreeNode<Integer> root, <Integer> node) {
  if(root == null || node == null)
   return; 
     
  if(node.getData() >= root.getData()) {
   if(root.getRight() == null) {
    root.setRight(node);
    return;
   }
   
   insert(root.getRight(), node);
  }
  
  else if (node.getData() < root.getData()) {
   if(root.getLeft() == null) {
    root.setLeft(node);
    return;
   }
   insert(root.getLeft(), node);
  } 
 }

 public TreeNode<Integer> search(TreeNode<Integer> root, int key) {
  
  if(root == null) 
   return null;
  
  if(key == root.getData()) {
   return root;
  }
  
  else if(key > root.getData()) {
   return search(root.getRight(), key);
  }  
  else if(key < root.getData()) {
   return search(root.getLeft(), key);
  }
  
  return null;
 }
}
원리는 노드 삽입과 마찬가지로 키 값을 비교하여, 값이 같으면 그 노드를 리턴하고, 값이 작으면 왼쪽 자식으로 이동 (재귀 호출을 통해), 값이 크면 오른쪽 자식으로 이동한다.

4. 노드 삭제 (deletion)

노드 삭제는 몇 가지 고려해야할 것들이 있다. 우선 노드의 삭제의 원리는 해당되는 노드를 찾아서 삭제한 후에, 삭제된 노드의 서브트리를 BST에 맞도록 재구성해야 한다는 것이다. 이때 삭제된 노드의 자식 노드 갯수에 따라 재구성하는 방법이 달라진다.

1. 자식 노드가 없는 경우 (즉 leaf 노드)
- leaf 노드인 경우에는 노드만 삭제하면 된다.

2. 자식 노드가 1개인 경우
- 삭제될 노드의 부모 노드에서 자식 노드를 직접 참조하게 한다. 삭제될 노드가 부모의 왼쪽 자식이면 왼쪽 자식을 부모의 왼쪽 자식으로, 오른쪽 자식이면 부모의 오른쪽 자식으로 직접 참조하게 한다.

3. 자식 노드가 2개인 경우
- 이 경우에 노드를 삭제하고 서브 트리를 재구성하는 것 보다, 노드는 그대로 두고 노드의 키값을 BST가 유지되도록 다른 값으로 대체(substitution)하는 방법을 취한다.
예를 들어, 아래의 트리에서 15를 삭제한다고 하면, 노드는 그대로 두고 15의 자리에 12를 넣고 12를 삭제한다.

        10
    8        15
  5  9   12   18
2                  20

        10
    8        12
  5  9          18
2   

이렇게 하면 BST를 유지할 수 있다.

그런데 다음과 같이해도 BST를 유지할 수 있다.

        10
    8        18
  5  9   12   20
2                  

즉 15 자리에 18을 넣고, 원래 있던 18 자리에 20을 넣고, 20을 삭제한다.

일반적으로 표현하면, 삭제될 노드의 값으로 올 수 있는 것은 삭제될 노드의 왼쪽 자식중에서 가장 큰 값 또는 오른쪽 자식중에서 가장 작은 값을 넣으면 된다. 이렇게 하면 BST의 특성상 BST를 유지할 수 있다.

public class BinarySearchTree {
 public void traversePreOrder(TreeNode<Integer> root) {
  if(root == null)
   return;
  
  System.out.print(root.getData() + " ");
  traversePreOrder(root.getLeft());
  traversePreOrder(root.getRight());
 }

 public void insert(TreeNode<Integer> root, <Integer> node) {
  if(root == null || node == null)
   return; 
     
  if(node.getData() >= root.getData()) {
   if(root.getRight() == null) {
    root.setRight(node);
    return;
   }
   
   insert(root.getRight(), node);
  }
  
  else if (node.getData() < root.getData()) {
   if(root.getLeft() == null) {
    root.setLeft(node);
    return;
   }
   insert(root.getLeft(), node);
  } 
 }

 public TreeNode<Integer> search(TreeNode<Integer> root, int key) {
  
  if(root == null) 
   return null;
  
  if(key == root.getData()) {
   return root;
  }
  
  else if(key > root.getData()) {
   return search(root.getRight(), key);
  }  
  else if(key < root.getData()) {
   return search(root.getLeft(), key);
  }
  
  return null;
 }

 public void delete(TreeNode<Integer> parent, TreeNode<Integer> node, int key) {
  if(node == null)
   return ;
  
  if(key > node.getData()) {
   delete(node, node.getRight(), key);
  }
  
  else if(key < node.getData()) {
   delete(node, node.getLeft(), key);
  }
  // found the node
  else {
   // the node has 2 children
   if(node.getLeft() != null && node.getRight() != null) {
    // finding a node which has minimum value in the right subtree of the node found
    // and replacing the value of the found node with the minimum value of the right subtree
    // and deleting the node having minimum value
    TreeNode min = findMin(node.getRight());
    node.setData(min.getData());
    delete(node, node.getRight(), min.getData());
   }
   
   // the node has left child
   else if(node.getLeft() != null) {
    if(parent.getLeft() == node)
     parent.setLeft(node.getLeft());
    else
     parent.setRight(node.getLeft());
   }
   
   // the node has right child
   else if(node.getRight() != null) {
    if(parent.getLeft() == node)
     parent.setLeft(node.getRight());
    else
     parent.setRight(node.getRight());
   }
   
   // the node is leaf
   else {
    if(parent.getRight() == node) {
     parent.setRight(null);
    }
    
    if(parent.getLeft() == node) {
     parent.setLeft(null);
    }
   }
  }
 }
}
parent: 부모 노드
node: 탐색을 시작할 노드
key: 삭제할 키

노드 삭제후 BST를 재구성하기 위해서는 parent 노드가 필요하다. 위의 코드에서는 오른쪽 자식중에서 최소값으로 대체하는 방법을 사용하였다.

아래와 같이 테스트 코드를 작성하면 된다.


 public static void main(String[] args) {
  TreeNode<Integer> root = new TreeNode<Integer>(20);
  BinarySearchTree bst = new BinarySearchTree();
  
  TreeNode<Integer> tn8 = new TreeNode<Integer>(8);
  TreeNode<Integer> tn22 = new TreeNode<Integer>(22);
  TreeNode<Integer> tn4 = new TreeNode<Integer>(4);
  TreeNode<Integer> tn12 = new TreeNode<Integer>(12);
  TreeNode<Integer> tn3 = new TreeNode<Integer>(3);
  TreeNode<Integer> tn10 = new TreeNode<Integer>(10);
  TreeNode<Integer> tn14 = new TreeNode<Integer>(14);
  
  bst.insert(root, tn8);
  bst.insert(root, tn22);
  bst.insert(root, tn4);
  bst.insert(root, tn12);
  bst.insert(root, tn3);
  bst.insert(root, tn10);
  bst.insert(root, tn14);
  
  bst.traversePreOrder(root);
  
  System.out.println();
  
  TreeNode<Integer> search = bst.search(root, 14);
  if(search == null)
   System.out.println("no search result...");
  else
   System.out.println("found..." + search.getData());
  
  System.out.println("min : " + bst.findMin(root).getData());
  System.out.println("max : " + bst.findMax(root).getData());
  
  bst.delete(null, root, 4);
  bst.traversePreOrder(root);
 }

댓글 없음:

댓글 쓰기