🔍 Binary Search Tree

👀 이진 트리(Binary Tree)

자식노드가 최대 두 개인 노드들로 구성된 트리로, 자료의 삽입/삭제 방법에 따라 Full Binary Tree, Complete Binary Tree, Perfect binary Tree로 나뉜다.

• 정 이진 트리(Full Binary Tree): 각 노드가 0 or 2개의 자식 노드를 갖는다.

• 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

• 포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경로, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.

👀 이진 탐색 트리(Binary Search Tree)

이진 탐색 + 연결 리스트 = 이진 탐색 트리로, 이진 탐색의 효율적인 탐색 능력 + 빈법한 자료 입력과 삭제가 가능하다.

✔ 이진 탐색 트리의 특징

• 각 노드에 중복되지 않는 key를 가진다.

• 루트노드의 왼쪽 서브 트리 = 해당 노드의 key보다 작은 key를 갖는 노드들로 이루어진다.

• 루트노드의 오른쪽 서브 트리 = 해당 노드의 key보다 큰 key를 갖는 노드들로 이루어진다.

• 좌우 서브 트리 모두 이진 탐색 트리이다.

따라서, 이진 탐색 트리의 탐색은 아래와 같은 과정을 거친다.

1. 찾고자 하는 key값과 root 노드 비교(root = key값 -> 탐색 종료)

2. 찾고자하는 key값 < root 노드 -> 왼쪽 서브 트리 탐색

3. 찾고자하는 key값 > root 노드 -> 오른쪽 서브 트리 탐색

4. 1~3의 과정을 찾고자하는 key 값을 찾을 때까지 반복

5. 값을 찾지 못하면 연산 종료(false return)

위의 과정을 거칠 시, 최대 트리의 높이(h) 만큼 탐색을 진행하기 때문에 O(h)의 복잡도를 가지며, 트리안에 찾고자하는 값이 없더라도 마찬가지로 최대 h번의 연산 및 탐색이 진행된다.

👀 Tree Traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 의미한다.

모든 노드를 방문하기 위해서는 일정 조건이 필요하고, 트리 구조를 유지보수하거나 특정 목적을 위해서 순회의 방법을 나누는데, 전위 순회, 중위 순회, 후위 순회로 크게 3가지로 나눌 수 있다.

일단, 아래의 이진 트리를 예시로 각 순회 방법에 따라 탐색 순서를 알아보자.

✔ 전위 순회(Preorder Traverse)

가장 먼저 root 노드를 방문하고, 왼쪽의 노드들을 순차적으로 둘러본 뒤에 오른쪽 노드를 탐색한다.

따라서, 부모 노드를 제일 먼저 방문하는 순회 방식으로, 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용한다.

위의 이미지를 참고하면 탐색 순서는

A -> B -> D -> G -> H -> E -> C -> F ->I -> J

✔ 중위 순회(Inorder Traverse)

root를 가운데에 두고 순회하는 방식으로, 제일 왼쪽 끝에 있는 노드부터 순회하며, root를 기준으로 왼쪽에 있는 노드 순회를 끝낸 후 -> root ->오른쪽 노드 순회의 과정을 거친다.

즉, 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식으로, 이진 탐색 트리의 오름차 순으로 값을 가져올 때 사용한다.

위의 이미지를 참고하면 탐색 순서는

G -> D -> H -> B -> E -> A -> I -> F -> J -> C

✔ 후위 순회(Postorder Traverse)

root를 가장 마지막에 방문하는 방식으로, 제일 왼쪽 끝에 있는 노드부터 순회 -> 오른쪽 노드 순회 -> root 노드의 과정을 거친다.

트리 삭제의 경우, 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문에 후위 순회의 방법을 사용한다.

위의 이미지를 참고하면 탐색 순서는

G -> H -> D -> E -> B -> I -> J -> F -> C -> A

🔥 Binary Search Tree / Tree Traversal 구현 코드

class BinarySearchTree {
  constructor(value) {
    //BST의 constructor를 구현-> 이진 탐색 트리의 Node.
    this.value = value;
    this.left = null;
    this.right = null;
  }

  // tree에 value 추가(삽입)
  insert(value) {
    // 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행.
    if (value < this.value) {
      // this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가.
      if (this.left === null) {
        this.left = new BinarySearchTree(value);
      } else {
        // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀 사용.
        this.left.insert(value);
      }

    // 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행.
    } else if (value > this.value) {
      // this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가.
      if (this.right === null) {
        this.right = new BinarySearchTree(value);
      } else {
        // this.right의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀 사용.
        this.right.insert(value);
      }
		//그것도 아니라면, 입력값이 트리에 들어 있는 경우.
    } else {
      // 이미 value값을 포함하고 있으므로, 아무것도 하지 않는다.
    }
  }

  // tree의 value값 탐색.
  contains(value) {
    // 찾는 value값이 노드의 value와 일치한다면, true return.
    if (value === this.value) {
      return true;
    }
    // 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains 재귀 사용.
    if (value < this.value) {
			// 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true return.
			// 일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색(재귀)
      return !!(this.left && this.left.contains(value));
    }

    // 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains 재귀 사용.
    if (value > this.value) {
			// 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true return.
			// 일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색(재귀)
      return !!(this.right && this.right.contains(value));
    }
		// 없다면 false return
  }

	/*
	트리의 순회
  단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 한다.
	*/

	// 전위 순회
  preorder(callback) {
		callback(this.value);
    if (this.left) {
      this.left.preorder(callback);
    };
    if (this.right) {
      this.right.preorder(callback);
    };
  }

	// 중위 순회
  inorder(callback) {
    if (this.left) {
      this.left.inorder(callback);
    };
    callback(this.value);
    if (this.right) {
      this.right.inorder(callback);
    };
  }

	// 후위 순회
  postorder(callback) {
    if (this.left) {
      this.left.postorder(callback);
    };
    if (this.right) {
      this.right.postorder(callback);
    };
    callback(this.value);
  }

}

// 입출력
const rootNode = new BinarySearchTree(10);
rootNode.insert(7);
rootNode.insert(8);
rootNode.insert(12);
rootNode.insert(11);
rootNode.left.right.value; // 8
rootNode.right.left.value; //11

let arr = [];
rootNode.preorder((value) => arr.push(value * 2));
arr; // [20, 14, 16, 24, 22]
...

Reference: 코드스테이츠