트리에 대해서 공부했으니, 이진탐색트리를 구현하는 방법에 대해서 정리해보려고 합니다. :)


✅ init

Node를 만들 클래스, Binary Search Tree 클래스를 만들어줍니다.

1
2
3
4
5
6
7
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
1
2
3
4
5
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

🚀 insert method

Pseudo Code

  • 새로운 노드(newNode)를 만든다.
  • root Node와 비교한다.
  • root Node가 없다면 newNode를 root로 만든다.
  • root Node가 있다면 newNode의 값이 큰 지, 작은 지 비교한다.
  • root Node보다 크다면?
    • root.right에 속한 노드를 확인한다.
    • root.right가 있다면 이전 스텝을 동일하게 반복한다.
    • root.right가 없다면 newNode를 root.right로 만든다.
  • root Node보다 작다면?
    • root.left에 속한 노드를 확인한다.
    • root.left 있다면 이전 스텝을 동일하게 반복한다.
    • root.left 없다면 newNode를 root.left로 만든다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);

    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    // 비교하는 노드를 current라는 변수에 할당
    let current = this.root;
    while (true) {
      // 이미 존재하는 요소라면 undefined 혹은 false return
      if (value === current.value) return undefined;
      // value가 작다면 왼쪽으로 이동
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        } else {
          current = current.left;
        }
      } else if (value > current.value) {
        if (current.right === null) {
          this.root.right = newNode;
          return this;
        } else {
          current = current.right;
        }
      }
    }
  }
}

contains method

🚀 Pseudo Code

  • root부터 시작
    • root가 없다면 탐색할 필요가 없음
    • root가 있다면, new Node의 값이 root의 값보다 작은지 큰지 비교한다.
  • 만약 new Node의 값이 더 크다면?
    • current = current.right
    • 종료조건에 도달할 때까지 계속 반복한다.
    • 값을 찾았다면 return true
  • 만약 new Node의 값이 더 작다면?
    • current = current.left
    • 종료 조건에 도달할 때까지 계속 반복한다.
    • 값을 찾았다면 return true
  • 종료조건까지 찾지 못했다면 return false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
contains (value) {
  if(this.root === null) return false;

  let current = this.root;
  let found = false; // 해당 요소를 찾았는지 확인하는 변수

  // current가 존재하고 값을 찾지 못했다면 (found가 false라면) while문 실행
  while(current && !found) {
    if(value < current.value) {
      current = current.left;

    } else if(value > current.value) {
      current = current.right;
    } else {
      return true
    }
  }
  return false;
}

🏖️ Array를 이용해서 푸는 방법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const array = [1, 1, 5, 400, 599, 1004, 2876, 8712];

function BinarySearchTree(array, findValue) {
  let left = 0;
  let right = array[array.length - 1];
  let mid = Math.floor((left + right) / 2);

  while (left < right) {
    if (array[mid] === findValue) {
      return mid;
    }

    if (array[mid] < findValue) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }

    mid = Math.floor((left + right) / 2);
  }

  return -1;
}