✍️
TIL
  • TIL
  • react
    • react 16.3 이후 라이프 싸이클
    • 함수형 컴포넌트 vs 클래스 컴포넌트
    • React의 장점
    • 기본문법
    • Flow Diagram
    • redux-saga
    • nextjs
    • mobx
    • 리액트는 어떻게 동작할까?
  • data-structure
    • 이진 검색 트리(binary search tree)
    • HashTable
    • Tree
    • 트라이(Trie)
    • 선형 구조 vs 비선형 구조
    • 연결 리스트(linked-list)
    • Queue
    • Graph
    • Heap
    • Stack
  • web
    • 웹 브라우저의 동작 원리
    • Basic
    • Webpack이란?
    • rendering
    • npm
    • babel
  • graphQL
    • Query
    • Mutation
    • Introduction
  • algorithm
    • big-o
    • 버블 정렬(bubble sort)
    • 힙 정렬(heap sort)
    • 선택 정렬(selection sort)
    • 퀵 정렬(quick sort)
    • 백트래킹 알고리즘
    • 삽입 정렬(insertion sort)
    • 계수 정렬(counting sort)
    • 다엑스트라 알고리즘
    • 이진 탐색
    • 합병 정렬(merge-sort)
    • 동적 계획법(Dynamic programming)
  • web-security
    • XSS(Cross Site Scripting)
    • CSRF(Cross-site request forgery)
    • Tabnabbing
  • javaScript
    • dom
    • 자바스크립트 성능 최적화
    • Event Loop
    • Snippets
    • javaScript
  • programming-paradigm
    • Object Oriented Programming
    • 함수형 프로그래밍
    • 구조적 프로그래밍
  • computer-science
    • Process vs Thread
    • 비트 연산자
    • 그레이 코드
  • vue
    • Vue
  • design-pattern
    • MVP pattern
    • Flux
    • 아토믹 디자인
    • MVVM pattern
    • MVC pattern
  • css
    • css
    • Grid
    • css-methodologies
    • FlexBox
  • html
    • html
  • regExp
    • regExp
  • git
    • Git-flow
Powered by GitBook
On this page

Was this helpful?

  1. data-structure

이진 검색 트리(binary search tree)

이진 탐색 트리는 "모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들"이라는 정의가 모든 노드 n에 대해서 참인 트리를 말한다.

바로 아래 자식뿐만 아니라 내 밑에 있는 모든 자식 노드들에 대해서 참이어야 한다.

시간 복잡도: 검색, 삭제, 삽입 O(log n)

function Node(data, left = null, right = null) {
  this.data = data
  this.left = left
  this.right = right
}

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

  insertNode(node) {
    // root node가 없으면 root에 node 삽입
    if (!this.root) {
      this.root = node
      return
    }

    let currentNode = this.root
    while (currentNode) {
      // 만약 node data가 현재 노드의 data보다 작다면
      if (node.data < currentNode.data) {
        // 만약 current node가 left subtree 없는 leaf node라면 left에 node삽입후 종료
        if (!currentNode.left) {
          currentNode.left = node
          return
        }
        // left subtree가 있으면 current node를 왼쪽 subtree로 이동
        currentNode = currentNode.left
        continue
      }
      // 만약 node data가 현재 노드의 data보다 크다면
      if (node.data > currentNode.data) {
        // 만약 current node가 right subtree 없는 leaf node라면 right에 node삽입
        if (!currentNode.right) {
          currentNode.right = node
          return
        }
        // right subtree가 있으면  current node를 오른쪽 subtree로 이동
        currentNode = currentNode.right
        continue
      }
      // 만약 node data가 현재 노드의 data와 동일하다면
      console.error(
        '이미 해당 data가 BST에 존재합니다 다른 data를 삽입해주세요.'
      )
      return
    }
  }

  inOrderTraversal(node = this.root) {
    if (node !== null) {
      this.inOrderTraversal(node.left)
      console.log('visit node: ' + node.data)
      this.inOrderTraversal(node.right)
    }
  }
}

const bst = new BinarySearchTree()
bst.insertNode(new Node(24))
bst.insertNode(new Node(20))
bst.insertNode(new Node(30))
bst.insertNode(new Node(26))
bst.insertNode(new Node(22))
bst.insertNode(new Node(14))
bst.inOrderTraversal() // 정렬된 node들
Previousdata-structureNextHashTable

Last updated 5 years ago

Was this helpful?