ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자바스크립트 자료구조 트리(Tree)
    Computer Science/Algorithm, Data Structure 2019.06.11 17:44

    모든 자바스크립트 개발자가 알아야 하는 33가지 개념

     

    저번에 문자열에 특화된 트라이(Trie) 트리 자료구조에 대해 알아보았다.

     

    2019/06/04 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 자료구조 트라이(Trie)

     

    자바스크립트 자료구조 트라이(Trie)

    Trie(트라이)에 대해 알아보자. 트라이는 일종의 검색 유형의 최적화된 트리이다. 문자열 검색, 자동완성 기능에 활용 가능하다. const Node = function() { this.keys = new Map(); this.end = false; this.set..

    jeongw00.tistory.com

     

    이번에는 이진 탐색 트리(Binary Search Tree)에 대해 알아보자.

     

    우선 트리의 용어에 대해 알아보면

     

    Root: 트리의 최상위 노드

     

    Child: 자식 노드

     

    Parent: 부모 노드

     

    leaf: 자식 노드가 없는 노드

     

    ancestor: 조상 노드

     

    descendant: 자손 노드

     

    sibling: 형제 노드

     

    이진 탐색 트리(Binary Search Tree)

     

     

    모든 노드에는 최대 2개의 하위 노드가 있고

     

    각 노드의 키가 왼쪽 하위 트리에 저장된 키보다 크거나 같고

     

    오른쪽 하위 트리에 저장된 키보다 작거나 같아야 한다.

     

    class Node {
      constructor(data) {
        this.right = null;
        this.left = null;
        this.data = data;
      }
    }
    
    class Bst {
      constructor() {
        this.root = null;
      }
      // 추가
      insert(data) {
        const node = new Node(data)
    
        if (!this.root) {
          this.root = node;
          return this;
        }
    
        let current = this.root;
        while (current) {
          // 중복 검사
          if (data === current.data) {
            return;
          }
          // 왼쪽 노드 추가
          if (data < current.data) {
            if (!current.left) {
              current.left = node;
              break;
            }
            current = current.left;
          }
          // 오른쪽 노드 추가
          if (data > current.data) {
            if (!current.right) {
              current.right = node;
              break;
            }
            current = current.right;
          }
        }
      }
      // 검색
      find(data) {
        if (!this.root) return null
        let current = this.root;
    
        while (current) {
          if (data == current.data) return current.data;
    
          if (current.right && data > current.data) {
            current = current.right
          } else {
            current = current.left
          }
        }
    
        return false;
      }
      // 포함
      include(data) {
        const found = this.find(data)
    
        if (found) {
          return true;
        }
        return false
      }
    
      // Breadth-first search(너비 우선 탐색)
      bfs() {
        let node = this.root;
        const queue = [node];
        const finalData = []
    
        while (queue.length) {
          node = queue.shift()
          if (node.left) queue.push(node.left);
          if (node.right) queue.push(node.right);
          finalData.push(node.data);
        }
    
        return finalData
      }
      
      // Depth-first search(깊이 우선 탐색)
      // Pre-order traversal
      preOrder() {
        const finalData = [];
        // 재귀함수
        function traverse(node) {
          finalData.push(node);
          if (node.left) traverse(node.left)
          if (node.right) traverse(node.right)
        }
    
        traverse(this.root);
        return finalData
      }
      // Post-order traversal(후위 순회)
      postOrder() {
        const finalData = [];
        // 재귀함수
        function traverse(node) {
          if (node.left) traverse(node.left)
          if (node.right) traverse(node.right)
          finalData.push(node);
        }
        traverse(this.root)
        return finalData
      }
      // In-order traversal(중위 순회)
      inOrder() {
        const finalData = [];
        // 재귀함수
        function traverse(node) {
          if (node.left) traverse(node.left)
          finalData.push(node.data)
          if (node.right) traverse(node.right)
        }
        traverse(this.root)
        return finalData
      }
      // Max
      maxNode() {
        if (!this.root) return null;
        let current = this.root;
        while (current.right) {
          current = current.right;
        }
        return current.data;
      }
      // Min
      minNode() {
        if (!this.root) return null;
        let current = this.root;
        while (current.left) {
          current = current.left;
        }
        return current.data;
      }
    
    }
    
    const bst = new Bst()
    
    bst.insert(15)
    bst.insert(20)
    bst.insert(30)
    bst.find(15) // 15
    bst.find(10) // false
    bst.include(20) // true
    bst.include(25) // false
    bst.maxNode() // 30
    bst.minNode() // 15

     

    insert() 추가

     

    find() 탐색

     

    include() 포함

     

    Breadth-first search(너비 우선 탐색)

     

    Depth-first search(깊이 우선 탐색)

     

    Pre-order traversal(전위 순회)

     

    Post-order traversal(후위 순회)

     

    In-order traversal(중위 순회)

     

    Max(최대)

     

    Min(최소)

    댓글 0