[자료구조] 211103 이진탐색(Binary Search Tree)구현 이해하기

📌 이진탐색(Binary Search Tree)

이진탐색은 토이문제에서 자주 응용되곤 했다. 보통은 배열의 중간 인덱스의 값 또는 임의의 값을 변수로 삼고, 그 기준을 바탕으로 나누어진 왼쪽 인덱스 그리고 오른쪽 인덱스를 활용하여 문제를 풀수 있다. 그래서 이 이진탐색 구현도 변수로 left,right 그리고 value을 이용한다.
구현해내야 할 메서드는 아래와 같다.

• insert(value): 입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.
• contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
• preorder(callback): 전위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
• inorder(callback): 중위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
• postorder(callback): 후위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.

constructor(value) {
		//constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
    this.value = value;
    this.left = null;
    this.right = null;
  }

1) insert(value)

입력값 value를 기준으로 현재 노드의 값보다 크거나 작은 것에 대한 조건문이 있어야 한다.

• '입력값 value가 this.value보다 작다면' 그리고 'value가 this.value보다 크다면'으로 나눈다
• 그리고 그 첫번째 조건문 내에서 Node(전체트리)의 왼쪽이 비워져있다면 그렇지 않다면의 경우로 나눈다.

insert() {
if (value < this.value) { //입력값 value가 this.value보다 작다면
      if (this.left === null) { } 
      else { }
}
else if (value > this.value) { //value가 this.value보다 크다면
    if (this.right === null) { } 
    else { }
}    

이런 모양새이다. 만약 왼쪽이 비어져 있다면 비어져 있는곳에 값들을 생성해야 할테니 새로운 트리를 생성하여 value를 집어넣는다. 왼쪽이 비어져 있지 않다면 재귀함수를 이용하여 value를 집어넣는다. this.left.insert(value)

insert(value) {
if (value < this.value) { //입력값 value가 this.value보다 작다면
      if (this.left === null) {
       this.left = new BinarySearchTree(value)
      } 
      else { 
        return this.left.insert(value)
      }
}
else if (value > this.value) { //value가 this.value보다 크다면
    if (this.right === null) { 
      this.right = new BinarySearchTree(value)
    } 
    else { 
      return this.right.insert(value)
    }
}    

왼쪽이 채워졌으면 오른쪽도 똑같이 채워주도록 한다. this.right.insert(value)

2) contains()

트리에 포함된 데이터를 찾아야 한다. 그래서 입력값 value가 this.value가 같다면 true 리턴한다.

contains(value) {
    if (this.value === value) {
      return true;
    }
// 입력값을 기준으로 현재 노드의 값보다 작은지 판별하는 조건문.
    if (value < this.value) { }	
// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문.
    if (value > this.value) { }
  }

트리에 포함된 데이터를 찾는 것이기 때문에 this.value가 null인 경우는 고려하지 않는다. 현재 노드의 값과 입력값이 일치하지 않는 경우는 또 두가지로 나눠진다.

• 현재 노드의 값이 입력값보다 작을 때
  • 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환

!!(this.left && this.left.contains(value))

• 현재 노드의 값이 입력값보다 클 때
  • 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환

!!(this.right && this.right.contains(value))

트리순회

테스트케이스에서 전위순회와 중위순회 그리고 후위순회를 구현하라고 했다. 트리순회는 트리에 저장된 값을 모두 확인해야 하기 때문이다. 여기서는 preorder(전위순회) inorder(중위순회) 그리고 postorder(후위순회) 로 나누었다.
콜백함수를 호출하는 위치가 각각 다르기 때문에 이름도 그에 따라 달라진다.

preorder(callback) {
  callback(this.value);
    if (this.left) {
      this.left.preorder(callback)
    };
//2)
    if (this.right) {
      this.right.preorder(callback);
    };
  }
//3) 

inorder 중위 순회시엔 2번위치에 콜백함수 호출. postorder 후위 순회시엔 3번위치에 콜백함수 호출