[JS] 이진 탐색 트리

1. 이진 탐색 트리란?

 

 이진 탐색 트리란 이진트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것을 말한다. 이진 탐색 트리의 특징은 다음과 같다.

 

1. 모든 원소는 서로 다른 유일한 키를 갖는다.

2. 왼쪽 서브트리에 있는 원소의 크기는 그 루트의 키보다 작다.

3. 오른쪽 서브트리에 있는 원소의 키는 그 루트의 키보다 크다.

4. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리다.

이번 포스팅에서 다룰 것은 이진 탐색 트리에 대한 간략한 정의, 탐색, 삽입, 삭제 연산이다. 이진 트리의 순회에 대해서는 이전에 포스팅을 했으니 참고하길 바란다.

 

 

2. 탐색 연산

탐색은 항상 루트에서 시작된다. 따라서 먼저 키값과 루트 노드의 키값을 비교한다. 비교 결과는 다음의 세 가지 중 하나가 될 것이다.

 

1. (키값 x = 루트 노드 키값) : 원하는 원소 찾았으므로 탐색 연산 성공

2. (키값 x < 루트 노드 키값) : 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행

3. (키값 x > 루트 노드 키값) : 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행

 다음은 키 값 4를 찾는 탐색과정을 나타낸 그림과 탐색 연산을 프로그램으로 짠 것이다.

[그림 1] 키값 4를 찾는 과정

/* 이진 탐색 트리의 탐색 연산 */
BST.prototype.search = function(node, data){
  let parent = node; //부모 노드
  let child = node;  //자식 노드
  while(child !== null){
    if(data < child.data){
    //키 값이 루트노드(자식 노드) 값 보다 작은 경우
    //현재 노드를 부모 노드에 저장하고
    //현재 노드의 왼쪽 노드를 루트 노드(자식 노드)에 저장한다.
      parent = child;
      child = child.left;
    }
    else if(data > child.data){
      parent = child;
      child = child.right
    }
    // 루트 노드와 자식노드가 같은 경우(바로 루트노드의 키 값과 같은 경우)
    // 루트노드(자식노드)만을 리턴하고 아닌경우 부모노드, 자식노드를 같이 리턴한다.
    else return parent === child ? [parent, null] : [parent, child];
  }
}

 

 

3. 삽입 연산

이진 탐색 트리에 원소를 삽입하려면 먼저 이진 탐색 트리에 같은 원소가 있는지를 확인하기 위해서 탐색을 해야 한다. 탐색 연산에 성공할 경우 이미 원소가 있으므로 삽입연산을 수행하지 않는다. 하지만 중복된 값이 없는 경우 그 자리에 원소를 삽입한다.

[그림 2] 5를 삽입 연산하는 과정

BST.prototype.insertBST = function(data){
  const insert = this.insertKey(this.root, data);
  this.root = insert;
} 

BST.prototype.insertKey= function(node, data){
  const root = node;
  const newNode = new Node(data);
  
  //루트가 null일 경우 중복이 없으므로 노드를 리턴한다.
  if(root === null)
    return newNode;

  /*값이 작을 경우 left값 리턴, 클 경우 right값 리턴
  또는 중복이 있을 경우 노드를 그대로 리턴한다.*/
  if(data < root.data){
    root.left = this.insertKey(root.left, data);
    return root;
  }
  else if(data > root.data){
    root.right = this.insertKey(root.right, data);
    return root;
  }
  else{
    return node;
  }
}

 

 

4. 삭제 연산

이진 탐색 트리에서 삭제연산을 하려면 먼저 탐색 연산을 해야한다. 삭제 할 노드는 자식 노드의 수에 따라 다음의 세 가지 경우가 있다.

 

1. 삭제할 노드가 단말 노드인 경우 (차수가 0)

2. 삭제할 노드가 한 개의 자식노드를 가진 경우 (차수가 1)

3. 삭제할 노드가 두 개의 자식노드를 가진 경우 (차수가 2)

[그림 3] 삭제할 노드가 단말 노드인 경우

 

[그림 4] 삭제할 노드가 한 개의 자식노드만 가진 경우

 

[그림 5] 삭제할 노드가 두 개의 자식을 가진 경우

BST.prototype.deleteBST = function(data){
//먼저 탐색 연산을 한다.
  let findNode = this.search(this.root, data);
  let parent = findNode[0];
  let child = findNode[1] === null ? parent : findNode[1];
  const root = child;

  console.log(this.root);

  if(child.left === null && child.right === null){
  //자식 노드가 0인 경우
    parent.data > child.data ? parent.left = null : parent.right = null;
  }
  else if(child.left === null || child.right === null){
  //자식 노드가 1인 경우
    parent = child;
    if(parent.left !== null){
      child = child.left;
      root.data = child.data;
      parent.left = null;
    }
    else{
      child = child.right;
      root.data = child.data;
      parent.right = null;
    }
  }
  else if(child.left !== null && child.right !== null){
  //자식 노드가 2인 경우
      parent = child;
      child = child.right;
      let flag = true;

      while(child.left !== null && child.right !== null){
        flag = false;
        parent = child;
        child = child.left;
      }
      root.data = child.data;
      flag === true ? parent.right = null : parent.left = null;
  }
  console.log(this.root);
}

 

4. 프로그램 코드

 최종 코드는 다음과 같다.

const Node = function(data){
  this.data = data;
  this.left = null;
  this.right = null;
}

const BST = function(){
  this.root = null;
}

BST.prototype.insertKey= function(node, data){
  const root = node;
  const newNode = new Node(data);

  if(root === null)
    return newNode;

  if(data < root.data){
    root.left = this.insertKey(root.left, data);
    return root;
  }
  else if(data > root.data){
    root.right = this.insertKey(root.right, data);
    return root;
  }
  else{
    return node;
  }
}

BST.prototype.insertBST = function(data){
  const insert = this.insertKey(this.root, data);
  this.root = insert;
} 

BST.prototype.search = function(node, data){
  let parent = node;
  let child = node;
  while(child !== null){
    if(data < child.data){
      parent = child;
      child = child.left;
    }
    else if(data > child.data){
      parent = child;
      child = child.right
    }
    else return parent === child ? [parent, null] : [parent, child];
  }
}


BST.prototype.deleteBST = function(data){
  let findNode = this.search(this.root, data);
  let parent = findNode[0];
  let child = findNode[1] === null ? parent : findNode[1];
  const root = child;

  console.log(this.root);

  if(child.left === null && child.right === null){
    parent.data > child.data ? parent.left = null : parent.right = null;
  }
  else if(child.left === null || child.right === null){
    parent = child;
    if(parent.left !== null){
      child = child.left;
      root.data = child.data;
      parent.left = null;
    }
    else{
      child = child.right;
      root.data = child.data;
      parent.right = null;
    }
  }
  else if(child.left !== null && child.right !== null){
      parent = child;
      child = child.right;
      let flag = true;

      while(child.left !== null && child.right !== null){
        flag = false;
        parent = child;
        child = child.left;
      }
      root.data = child.data;
      flag === true ? parent.right = null : parent.left = null;
  }
  console.log(this.root);
}

function main(){
  const bst = new BST();
  bst.insertBST(8);
  bst.insertBST(5);
  bst.insertBST(6);
  bst.insertBST(14);
  bst.insertBST(9);
  bst.insertBST(16);

  bst.deleteBST(5);
}

main();

 

5. 참고 자료

 자바로 배우는 쉬운 자료구조, 한빛 아카데미