TIL 40 | Tree

pca0046ยท2021๋…„ 7์›” 31์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
3/4
post-thumbnail

What is a tree?

A data structure that consists of nodes in a parent / child relationship

Binary Tree

  • Every parent node has at most two children

Binary Search Tree

  • 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 parent

Make a binary search tree

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

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

Inserting(Iteratively or Recursively)

  • Create a new node
  • Start 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
    • If it is greater
      • Check to see If there is a node to the right
        • If there is, move to that node and repeat these steps
        • If there is not, add that node as the right property
    • If it is less
      • Check to see If there is a node to the left
        • If there is, move to that node and repeat these steps
        • If there is not, add that node as the left property
insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      while (true) {
        if (value === current.value) return undefined;
        if (value < current.value) {
          if (current.left === null) {
            current.left = newNode;
            return this;
          } else {
            current = current.left;
          }
        } else if (value > current.value) {
          if (current.right === null) {
            current.right = newNode;
            return this;
          } else {
            current = current.right;
          }
        }
      }
    }
  }

Finding a node

  • Starting at the root
    • Check if there is a root, if not - we're done searching
    • It there is a root, check if the value of the new node is the value we are looking for. If we found it, we're done
    • If not, check to see if the value is greater than or less than the value of the root
    • If is greater
      -Check to see if there is a node to the right
      - If there is, move to that node and repeat these steps
      - If there is not, we're done searching
      -If is less
      -Check to see if there is a node to the left
      - If there is, move to that node and repeat these steps
      - If there is not, we're done searching
find(value) {
    if (this.root === null) return false;
    let current = this.root;
    let found = false;
    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.vlue) {
        current = current.right;
      } else {
        found = true;
      }
    }
    if (!found) return undefined;
    return current;
  }

  contains(value) {
    if (this.root === null) return false;
    let current = this.root;
    let found = false;
    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return true;
      }
    }
    return false;
  }

BFS

  • Create a queue(this can e an array) and a variable to store the values of nodes visited
    • Place the root node in the queue
    • Loop as long as there is anything in the queue
      • Dequeue a node from the queue and push the value of the node into the variable that sotres the nodes
      • If there is a left property on the node dequeued - add it to the queue
      • If there is a right property on the node dequeued - add it to the queue
    • return the variable that stores the values
BFS() {
    let node = this.root;
    let data = [];
    let queue = [];
    queue.push(node);

    while (queue.length) {
      node = queue.shift();
      data.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return data;
  }

DFS (Depth First Search)
(1) Preorder - recursively

  • Create a variable to store the values of nodes visited
    • Store the root of the BST in a variable called current
    • Write a helper function which accepts a node
    • Push the value of the node to the variable that stores the values
    • If the node has a left property, call the helper function with the left property on the node
    • If the node has a right property, call the helper function with the right property on the node
DFSPreOrder() {
    let data = [];
    let current = this.root;
    function traverse(node) {
      data.push(node.value);
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    }
    traverse(current);
    return data;
}

(2) Postorder - recursively

  • Create a variable to store the values of nodes visited
    • Store the root of the BST in a variable called current
    • Write a helper function which accepts a node
    • If the node has a left property, call the helper function with the left property on the node
    • If the node has a right property, call the helper function with the right property on the node
    • Push the value of the node to the variable that stores the values
    • Invoke the helper function with the current variable
DFSPostOrder() {
    let data = [];
    let current = this.root;
    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      data.push(node.value);
    }
    traverse(current);
    return data;
  }

(3) InOrder - recursively

  • Create a variable to store the values of nodes visited
    • Store the root of the BST in a variable called current
    • Write a helper function which accepts a node
    • If the node has a left property, call the helper function with the left property on the node
    • Push the value of the node to the variable that stores the values
    • If the node has a right property, call the helper function with the right property on the node
    • Invoke the helper function with the current variable
DFSInOrder() {
    let data = [];
    let current = this.root;
    function traverse(node) {
      if (node.left) traverse(node.left);
      data.push(node.value);
      if (node.right) traverse(node.right);
    }
    traverse(current);
    return data;
  }

Big O of BST

Not guaranteed

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

BFS & DFS which one is better?

์‹œ๊ฐ„ ๋ณต์žก๋„ ์ธก๋ฉด์—์„œ BFS ์™€ DFS ๋Š” ํฌ๊ฒŒ ์ฐจ์ด๊ฐ€ ์—†๋‹ค. ๋“ค๋‹ค ๋ฐ์ดํ„ฐ ์–‘์ด ๋Š˜์–ด๋‚ ์ˆ˜๋ก ์‹คํ–‰ ํšŸ์ˆ˜๋„ ์ฆ๊ฐ€ํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. tree์˜ ๊นŠ์ด๋ณด๋‹ค ๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ ๋„“์€ ๊ฒฝ์šฐ DFS๊ฐ€ ๋” ์ ์ ˆํ•˜๋‹ค. ๊ณต๊ฐ„ ๋ณต์žก๋„๊ฐ€ BFS๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ, BFS์˜ ๊ฒฝ์šฐ์—๋Š” ํƒ์ƒ‰์ด ํ•„์š”ํ•œ ํ˜•์ œ ๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ ํ์— ์ €์žฅํ•ด๋†”์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํŠธ๋ฆฌ์˜ ๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ ๋Š˜์–ด๋‚  ์ˆ˜๋ก ์šฉ๋Ÿ‰์„ ๋งŽ์ด ์ฐจ์ง€ํ•œ๋‹ค. ์ด ๋ฐ˜๋Œ€์˜ ๊ฒฝ์šฐ, ์ฆ‰ ๊ฐ€๋กœ๊ธธ์ด๊ฐ€ ์ข๊ณ  ๊นŠ์ด๊ฐ€ ๊นŠ์€ ๊ฒฝ์šฐ์—๋Š” BFS๊ฐ€ ๋” ์ ์ ˆํ•˜๋‹ค. ๊นŠ์ด๊ฐ€ ๊นŠ์–ด์งˆ์ˆ˜๋ก DFS์˜ ์žฌ๊ท€๊ฐ€ ์ž‘๋™ํ•˜๋ฉด์„œ ๊ธฐ์–ตํ•ด์•ผํ•  ์š”์†Œ๋“ค์ด ๋งŽ์•„์ง€๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. BFS ๋Š” ํ์— ์ €์žฅํ•ด๋†“๊ณ  ๋‹ค ๋‚ ๋ ค๋ฒ„๋ฆฌ๋ฉด์„œ ์ด๋™ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์šฉ๋Ÿ‰ ์ฐจ์ง€๊ฐ€ ๋œํ•˜๋‹ค.

DFS inorder, preorder which one is better?

-BST ํƒ์ƒ‰ํ•  ๋•Œ inorder๋กœ ํƒ์ƒ‰ํ•˜๋ฉด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ sorting๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ๋‹ค.
-BST ํƒ์ƒ‰ํ•  ๋•Œ preorder๋กœ ํƒ์ƒ‰ํ•˜๋ฉด ํŠธ๋ฆฌ ๋ชจ์–‘์ด ๊ทธ๋Œ€๋กœ ๋‹ด๊ธด ๋ฐ์ดํ„ฐ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ๋‹ค. root data์—์„œ ํƒ์ƒ‰์ด ์‹œ์ž‘๋˜๊ธฐ ๋•Œ๋ฌธ

0๊ฐœ์˜ ๋Œ“๊ธ€