[TIL] 220116

Lee Syongยท2022๋…„ 1์›” 16์ผ
0

TIL

๋ชฉ๋ก ๋ณด๊ธฐ
151/204
post-thumbnail

๐Ÿ“ ์˜ค๋Š˜ ํ•œ ๊ฒƒ

  1. ์ž๋ฃŒ ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ณต์Šต

๐Ÿ“š ๋ฐฐ์šด ๊ฒƒ (๋ณต์Šต)

์ฑ… ใ€Ž๋ˆ„๊ตฌ๋‚˜ ์ž๋ฃŒ ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ใ€ ๋ณต์Šต

1. ์ž๋ฃŒ ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • [TIL] 211023
    • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ
    • ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ

์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์—์„œ๋Š” ๊ธฐ๋กํ•ด๋†“์€ ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ์— ๋ฐ”๋กœ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๊ณ , ๊ฐ ๋…ธ๋“œ๊ฐ€ ๋ฐ”๋กœ ์•ž ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋งํฌ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

  • [TIL] 211024
    • ์ด์ง„ ํŠธ๋ฆฌ
    • ์ด์ง„ ํŠธ๋ฆฌ์˜ ์—ฐ์‚ฐ ๐Ÿ’ข
    • ๋ฐฐ์—ด VS ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ
    • ์ •๋ ฌ๋œ ๋ฐฐ์—ด VS ์ด์ง„ ํŠธ๋ฆฌ
    • ์ด์ง„ ํŠธ๋ฆฌ์˜ ์ˆœํšŒ

๐Ÿ™‹โ€โ™€๏ธ ์ด์ง„ ํŠธ๋ฆฌ์˜ ์—ฐ์‚ฐ ไธญ '์‚ญ์ œ'

class TreeNode {
  constructor(value, left_child = null, right_child = null) {
    this.value = value;
    this.left_child = left_child;
    this.right_child = right_child;
  }
}

const node_1 = new TreeNode(1);
const node_2 = new TreeNode(3);
const root = new TreeNode(5, node_1, node_2);

function remove(valueToRemove, node) {
  if (node === null) {
    return null;
  } else if (valueToRemove < node.value) {
    node.left_child = remove(valueToRemove, node.left_child);
  } else if (valueToRemove > node.value) {
    node.right_child = remove(valueToRemove, node.right_child);
  } else {
    if (node.left_child === null) {
      return node.right_child;
    } else if (node.right_child === null) {
      return node.left_child;
    } else {
      node.right_child = lift(node.right_child, node);
      return node;
    }
  }
}

function lift(node, nodeToRemove) {
  if (node.left_child) {
    node.left_child = lift(node.left_child, nodeToRemove);
    return node;
  } else {
    nodeToRemove.value = node.value;
    return node.right_child;
  }
}

๐Ÿ’ก ์ค‘์œ„ ์ˆœํšŒ

// ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ โ†’ ๋ถ€๋ชจ ๋…ธ๋“œ โ†’ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ
function traverse_and_print(node) {
  if (node === null) {
    return;
  }
  traverse_and_print(node.left_child);
  console.log(node.value);
  traverse_and_print(node.right_child);
}

[ ์ฑ… ๊ทธ๋ฆผ ์ฐธ๊ณ  ]
์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์—†์„ ๋•Œ๊นŒ์ง€ ๋‚ด๋ ค๊ฐ€์„œ ๊ฐ€์žฅ ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ์ถœ๋ ฅ
์ถœ๋ ฅํ•œ ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ๊ทธ ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ์ถœ๋ ฅ
๊ทธ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด ๊ทธ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ์ถœ๋ ฅ


โœจ ๋‚ด์ผ ํ•  ๊ฒƒ

  1. ์ž๋ฃŒ ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜
profile
๋Šฅ๋™์ ์œผ๋กœ ์‚ด์ž, ํ–‰๋ณตํ•˜๊ฒŒ๐Ÿ˜

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