1. 이진검색트리

이름만 들어서는 무슨 말인지 잘 모르겠다. 이 자료구조의 경우에는 영어가 더 편한것 같다.(이하 BST)

BST에 대해서 간략하게 개념을 정리해 보았다.

-- Terminology

• Root / Child / Parent / Siblings / Leaf / Edge(arrow)

-- Application

• HTML DOM

• Artificial Intelligence

• Computer file systems

Binary Search Trees (BST)

• Every parent node has at most two children
• Every node to the left of a parent node is always less than the parent
• Every node to the right of a parent node is always greater than the parnent

뿌리가 있고 그 밑으로 자료들이 뻗어가는 형태를 띄고 있다. tree는 다양한 형태가 있는데 그중에 BST는 큰게 오른쪽 작은게 왼쪽에 위치해있다. 그래서 이름처럼 검색에 매우 유용한 구조이다.

그럼 insert부터 알아보자.

1-1. Insert

BST insert pesudocode

-- Create a new node.

-- starting at the root.

• check if there is a root, if not – the root now becomes that new node.

• If there is a root, check if the value of the new node is greater than or less than the value of the root.

• keep comparing until you found the sweet spot for the new node! good luck.

newNode가 크면 계속 오른쪽으로 가다가 null을 만나면 그자리에 정착. 작은경우도 마찬가자!

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

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

  insert(val) {
    var newNode = new Node(val);
    if (!this.root) {
      this.root = newNode;
      return this;
    } else {
      var newNodeVal = newNode.val;
      var currentNode = this.root;

    while (true) {
      if (newNodeVal > currentNode.val) {
        if (currentNode.right) {
          currentNode = currentNode.right;
        } else {
          currentNode.right = newNode;
          break;
        }
      } else if (newNodeVal < currentNode.val) {
        if (currentNode.left) {
          currentNode = currentNode.left;
        } else {
          currentNode.left = newNode;
          break;
        }
      } else {
        return 'invalid num';
      }
    }
    return this;
  }
}

1-2. Find

이번에는 tree안에서 원하는 노드를 찾아보자.

found 라는 변수를 이용해서 keep track of 하는 방법을 또 배웠다. insert 와 마찬가지로 크기를 비교하며 따라 계속 내려가다가 발견되면 found가 true로 되면서 빠져나온다. 아님 current가 null이어도 빠져나온다.

find(val) {
  if (!this.root) return undefined;
  var current = this.root;
  var parent;
  var found = false;

  // while 문 자체에 조건을 다는 방법도 있다!
  // 코드가 훨씬 간결해진다
  while (current && !found) {
    if (val < current.val) {
      parent = current;
      current = current.left;
    } else if (val > current.val) {
      parent = current;
      current = current.right;
    } else {
      found = true;
    }
  }
  if (current) {
    return {
      current: current,
      parent: parent,
    };
  }
}

마지막으로 delete 메소드인데 길어서 다음글에서 설명하겠다!