Binary Trees

• 비선형 구조

트리 사용예시

• HTML DOM
• Network Routing
• AI
• Computer File Systems

트리 용어 정리

• Root : 트리의 꼭대기 노드
• Child : 루트에서 멀어지는 방향으로 연결된 노드
• Parent : Child의 반대
• Siblings : 같은 부모노드를 가지는 자식 노드들
• Leaf : 자식이 없는 노드
• Edge : 노드들을 연결하는 것

Binary Search Tree

• 정렬 데이터를 가지고 탐색 작업을 한다.

Binary Search Tree 특징

• 모든 부모 노드는 최대 2개의 자식 노드를 가진다.
• 데이터가 특정한 순서로 저장된다.
• 부모 노드보다 왼쪽에 있는 모든 노드는 언제나 부모보다 작다
• 부모 노드보다 오른쪽에 있는 모든 노드는 언제나 부모보다 크다.

Big O of BST

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

BinarySearchTree Class

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

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

BST Inserting method

• 새로운 노드를 생성하여 제데로 된 자리에 노드를 놓는다.

의사코드

1. 새로운 노드 생성
2. 루트가 있는지 확인
3. 루트가 없으면 루트는 새로운 노드가 되고 트리를 리턴한다.
4. 만약 루트가 있다면 현재 위치를 나타내는 currentNode변수를 생성한다
5. while문을 돌며 트리를 탐색한다.
6. 만약 기존에 트리에 있는 값이 들어온다면 return undefined.
7. 현재 값보다 새로운 노드의 값이 크다면 현재 위치에 오른쪽에 값이 있는지 확인 한고 없으면 그곳이 새로 생성된 노드의 위치다.
8. 만약 현재 값보다 새로운 노드의 값이 작다면 현재 위치에 왼쪽에 값이 있는지 확인 하고 없다면 그곳이 새로 생성된 노드의 위치다.

insert(val){
  let newNode = new Node(val)
  if(!this.root){
    this.root = newNode
    return this
  }else{
    let currentNode = this.root 
    //currentNode, true 둘다 상관없다.
    while(true){
      //기존에 있는 값인 경우
      if(val === currentNode.val) return undefined
      if(currentNode.val < val){
        if(currentNode.right){
          currentNode = currentNode.right
        }else{
          currentNode.right = newNode
          return this
        }
      }else{
        if(currentNode.left){
          currentNode = currentNode.left 
        }else{
          currentNode.left = newNode
          return this
        }
      }
    }
  }
}

BST Find method

• 새로운 노드를 생성하여 제데로 된 자리에 노드를 놓는다.

의사코드

1. 루트가 있는지 확인.
2. 루트가 없으면 return false.
3. 만약 루트가 있다면 현재 위치를 나타내는 currentNode변수와 found변수를 생성한다.
4. while문을 돌며 트리를 탐색한다.
5. 현재 값보다 찾고자 하는 값이 크다면 현재 위치는 현재위치 오른쪽.
6. 만약 현재 값보다 찾고자 하는 값이 작다면 현재 위치는 위치 왼쪽.
7. 5,6번이 아니라면 found는 true로 업데이트하고 while문을 종료한다.
8. return currentNode.

find(val){
  if(!this.root) return false
  let currentNode = this.root
  let found = false
  while(currentNode && !found){
    if(currentNode.val < val){
      currentNode = currentNode.right
    }else if(val < currentNode.val){
      currentNode = currentNode.left
    }else{
      found = !found
    }
  }
  return currentNode
}