이진 검색 트리(내 개인 Google 인터뷰 연구 노트)

Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.

이진 트리 연습

이진 검색 트리

이진 검색 트리 ~ 노드 배열

이진 검색 트리 시간 복잡도

이진 검색 트리 공간 복잡성

순회

/*------------------------------------------------------------------------------------
 |   Binary Tree Node
 *------------------------------------------------------------------------------------
 |
 |   . Api
 |     -> leftHeight
 |        @return {number}
 |     -> rightHeight
 |        @return {number}
 |     -> height
 |        @return {number}
 |     -> balanceFactor
 |        @return {number}
 |     -> uncle
 |        @return {BinaryTreeNode}
 |     -> setValue
 |        @param {*} value
 |        @return {BinaryTreeNode}
 |     -> setLeft
 |        @param {BinaryTreeNode} node
 |        @return {BinaryTreeNode}
 |     -> setRight
 |        @param {BinaryTreeNode} node
 |        @return {BinaryTreeNode}
 |     -> removeChild
 |        @param {BinaryTreeNode} nodeToRemove
 |        @return {boolean}
 |     -> replaceChild
 |        @param {BinaryTreeNode} nodeToReplace
 |        @param {BinaryTreeNode} replacementNode
 |        @return {boolean}
 |     -> copyNode (static)
 |        @param {BinaryTreeNode} sourceNode
 |        @param {BinaryTreeNode} targetNode
 |     -> traverseInOrder
 |        @return {*[]}
 |     -> toString
 |        @return {string}
 |
 */
const HashTable = require('@DataStructure/HashTable.js')
const Comparator = require('@Helper/Comparator')


class BinaryTreeNode 
{
  static make(...parameters)
  {
    return new this(...parameters)
  }

  constructor(data = null) 
  {
    this.data = data
    this.left = null
    this.right = null
    this.parent = null

    // Any node related meta information may be stored here.
    this.meta = HashTable.make()

    // This comparator is used to compare binary tree nodes with each other.
    this.nodeComparator = Comparator.make()
  }


  get leftHeight() 
  {
    if (!this.left) return 0

    return this.left.height + 1
  }

  get rightHeight() 
  {
    if (!this.right) return 0

    return this.right.height + 1
  }

  get height() 
  {
    return Math.max(this.leftHeight, this.rightHeight)
  }

  get balanceFactor() 
  {
    return this.leftHeight - this.rightHeight
  }

  get uncle() 
  {
    if (!this.parent) return undefined

    // Check if current node has grand-parent.
    if (!this.parent.parent) return undefined

    // Check if grand-parent has two children.
    if (!this.parent.parent.left || !this.parent.parent.right) return undefined

    // So for now we know that current node has grand-parent and this
    // grand-parent has two children. Let's find out who is the uncle.
    if (this.nodeComparator.equal(this.parent, this.parent.parent.left)) return this.parent.parent.right

    // Left one is an uncle.
    return this.parent.parent.left
  }

  setValue(value) 
  {
    this.value = value

    return this
  }


  setLeft(node) 
  {
    // Reset parent for left node since it is going to be detached.
    if (this.left) this.left.parent = null

    // Attach new node to the left.
    this.left = node

    // Make current node to be a parent for new left one.
    if (this.left) this.left.parent = this

    return this
  }

  setRight(node) 
  {
    // Reset parent for right node since it is going to be detached.
    if (this.right) this.right.parent = null

    // Attach new node to the right.
    this.right = node

    // Make current node to be a parent for new right one.
    if (node) this.right.parent = this

    return this
  }

  removeChild(nodeToRemove) 
  {
    if (this.left && this.nodeComparator.equal(this.left, nodeToRemove)) {
      this.left = null
      return true
    }

    if (this.right && this.nodeComparator.equal(this.right, nodeToRemove)) {
      this.right = null
      return true
    }

    return false
  }

  replaceChild(nodeToReplace, replacementNode) 
  {
    if (!nodeToReplace || !replacementNode) return false

    if (this.left && this.nodeComparator.equal(this.left, nodeToReplace)) {
      this.left = replacementNode
      return true
    }

    if (this.right && this.nodeComparator.equal(this.right, nodeToReplace)) {
      this.right = replacementNode
      return true
    }

    return false
  }

  static copyNode(sourceNode, targetNode) 
  {
    targetNode.setValue(sourceNode.value)
    targetNode.setLeft(sourceNode.left)
    targetNode.setRight(sourceNode.right)
  }

  traverseInOrder() 
  {
    let traverse = []

    // Add left node.
    if (this.left) {
      traverse = traverse.concat(this.left.traverseInOrder())
    }

    // Add root.
    traverse.push(this.value)

    // Add right node.
    if (this.right) {
      traverse = traverse.concat(this.right.traverseInOrder())
    }

    return traverse
  }

  toString() 
  {
    return this.traverseInOrder().toString()
  }
}

module.exports = BinaryTreeNode

// https://opendatastructures.org/versions/edition-0.1c/ods-java/node36.html


// lookup
// insert
// delete
// access 

// depth
// count
// isEmpty
// isNotEmpty


/** 
 | has(value)
   insert(value)
   lookup(value)
 | delete(value) // TODO: fix this function
 | depthFirstLog (cllback)
*/

class BinarySearchTree 
{
    constructor (value)
    {
      this.value = value 
      this.left = undefined
      this.right = undefined

      return this
    }

    insert (value)
    {
      let node = new BinarySearchTree(value)

      let recurse = bst => {
        if (bst.value > value && bst.left === undefined) {
          bst.left = node
        } else if (bst.value > value) {
          recurse(bst.left)
        } else if (bst.value < value && bst.right === undefined) {
          bst.right = node
        } else if (bst.value < value) {
          recurse(bst.right)
        }
      }

      recurse(this)

    }

    lookup (value)
    {
      let resolved = -1
      let recurse = bst => {
        if (bst.value === value) {
          resolved = bst
        } else if (bst.left !== undefined && value < bst.value) {
          recurse(bst.left)
        } else if (bst.right !== undefined && value > bst.value) {
          recurse(bst.right)
        }
      }

      recurse(this)

      return resolved
    }

    has (value)
    {
      let hasValue = false;
      //accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.
      let recurse = bst => {
        if (bst.value === value) {
          hasValue = true
        } else if (bst.left !== undefined && value < bst.value) {
          recurse(bst.left)
        } else if (bst.right !== undefined && value > bst.value) {
          recurse(bst.right)
        }
      }

      recurse(this)

      return hasValue
    }

    delete (start) 
    {
      let data = []
      let queue = []

      let node = start ? this.lookup(start) : this.root

      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)
      }
    }

    depthFirstLog (callback = console.log)
    {
      let recurse = bst => {
        callback.call(bst, bst.value)

        if (bst.left !== undefined) recurse(bst.left)
        if (bst.right !== undefined) recurse(bst.right)
      }

      recurse(this)
    }
}



module.exports = BinarySearchTree

FAANG Study Resource: Cracking the Coding Interview
(Google Recommended)