BST(Binary Search Tree) with JS

• 단일 연결 리스트 
• 이중 연결 리스트
• 스택 & 큐 (배열로 하는 방법은 숙지했음! linked list로 구현해 보기)
• 이진 검색 트리
• 트리 순회
• 이진 힙
• 해시 테이블 (사용해 봤지만 복습)
• 그래프, 그래프 순회
• 다익스트라 알고리즘
• 동적 프로그래밍

---

기본적인 연결리스트의 개념이 필요하다.

2024.01.23 - [코딩테스트/코테를 위한 알고리즘 & 자료구조 정리] - Singly Linked Lists with JS

Singly Linked Lists with JS

---

트리

연결리스트처럼 노드로 이루어진 데이터 구조이다.

가지를 가지고 있는 자료구조

트리는 비선형 구조이다.

루트는 top node이다.

자식은 루트에서 멀어지는 방향으로 연결된 노드입니다.

부모는 자식의 반대 개념이다.

---

트리 사용

• HTML DOM
  • 여러 요소들이 있고 한 요소 안에 자식에 해당하는 다른 요소가 중첩되어 있다.
• Network Routing
• Abstract Syntax Tree
• Artificial Intelligence (인공지능과 머신 러닝)

---

Binary Search Tree (BST)

이진 검색 트리 - 순서가 있는 정렬 데이터를 가지고 탐색하는 작업을 한다.

이진 트리의 특징은 자기보다 작은 값은 왼쪽, 큰 값은 오른쪽에 있다.

---

구현 (insert, find)

 

//Node생성은 이중연결리스트와 매우 비슷하지만 더 간단하다.
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

//이진트리의 기본의 root는 null로 시작된다. 
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  //값을 추가할 때 value가 저장된 Node형 새로운 값을 newNode에 할당한다.
  insert(value) {
    var newNode = new Node(value);
    //root가 null일경우 (값이 아무것도 없는 경우)
    if (this.root === null) {
    //root에 newNode를 넣는다.
      this.root = newNode;
      return this;
    }
    
    // 값이 있다면 root를 current에 넣어서 순회를 시킨다. 
    var current = this.root;
    while (true) {
    //값이 넣을 값과 같다면 종료시킨다.
      if (value === current.value) return undefined;
      
      //값이 기존 값보다 클 경우에는 오른쪽 node로 전달.
      if (value > current.value) {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        //오른쪽으로 넘어간다.
        current = current.right;
      } else {
      //작을 경우 왼쪽으로 node를 전달.
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        //왼쪽으로 넘어간다.
        current = current.left;
      }
    }
  }
  
  //find (순회)
  find(value) {
  //root가 null일경우 는 종료 (값이 없는 경우)
    if (this.root === null) return false;
    
    //root를 순회하는 current에 넣는다.
    var current = this.root;
    var found = false;
    
    //순회값과 Found가 true일 경우 종료시킨다.
    while (current && !found) {
    
    //왼쪽, 오른쪽 크기 비교해서 이동시킨다.
      if (value < current.value) current = current.left;
      else if (value > current.value) current = current.right;
      else found = true;
    }

    if (!found) return undefined;
    return current;
  }
}

var tree = new BinarySearchTree();

tree.insert(36);
tree.insert(8);
tree.insert(18);
tree.insert(41);
tree.insert(55);
tree.insert(66);
tree.insert(77);
tree.insert(92);
tree.insert(81);
tree.insert(89);
tree.insert(95);
tree.insert(93);
tree.insert(99);
let find = tree.find(3);
console.log(tree);
console.log(find);

 

Big O of BST

• insertion - O(log n)
• Searching - O(log n)