[비선형] 3. 이진 탐색 트리

in 자료구조 on 비선형




1. 이진 탐색 트리 (Binary Search Tree)

  • 현재 노드르 기준으로 왼쪽에는 작은 값, 오른쪽은 큰 값을 정렬해 놓는 이진 트리 기반 자료 구조
  • 노드 추가 : BinarySearchTree._insertNode(), BinarySearchTree.insert()
  • 노트 탐색 (최댓값) : BinarySearchTree._maxNode(), BinarySearchTree.max()
  • 노드 탐색 (최솟값) : BinarySearchTree._minNode(), BinarySearchTree.min()
  • 노트 탐색 (특정값) : BinarySearchTree._searchNode(), BinarySearchTree.search()
  • 노드 삭제 : BinarySearchTree._findMinNode(), BinarySearchTree._removeNode(), BinarySearchTree.remove()



2. 구현하기

트리

이진트리와 같은 부분

// Node() : value와 left, right node 저장을 위한 생성자
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

// BinarySearchTree() : 시작 노드인 root 를 저장하기 위한 생성자
function BinarySearchTree() {
  this.root = null;
}

// _insertNode() : 재귀로 트리를 순회하며 노드 추가 (내부 사용)
BinarySearchTree.prototype._insertNode = function (node, value) {
  // 현재값과 비교
  // 작으면 왼쪽, 크면 오른쪽
  // 왼쪽, 오른쪽에 left, right pointer 비어있다면 추가할 노드를 연결
  // 비어있지 않다면 하위 노드에서 다시 비교하도록 넘겨준다

  if (node === null) {
    node = new Node(value);
  } else if (value < node.value) {
    //🤔 재귀는 어려워...
    node.left = this._insertNode(node.left, value);
  } else if (value > node.value) {
    //🤔
    node.right = this._insertNode(node.right, value);
  }

  return node;
};

// inser() : 노드 추가
BinarySearchTree.prototype.insert = function (value) {
  this.root = this._insertNode(this.root, value);
};


// _inOrderTraverse() : 재귀로 트리를 순회하며 중위 순회 (내부 사용)
BinarySearchTree.prototype._inOrderTraverse = function (node, callback) {
  if (node === null) {
    return;
  }

  this._inOrderTraverse(node.left, callback);
  callback(node);
  this._inOrderTraverse(node.right, callback);
};

// inOrderTraverse() : 중위 순회하며 노드 출력
BinarySearchTree.prototype.inOrderTraverse = function (callback) {
  this._inOrderTraverse(this.root, callback);
};


let tree = new BinarySearchTree();

tree.insert("F");
tree.insert("B");
tree.insert("A");
tree.insert("D");
tree.insert("C");
tree.insert("E");
tree.insert("G");
tree.insert("I");
tree.insert("H");

// callback
function printNode(node) {
  process.stdout.write(`${node.value} -> `);
}

console.log("---------중위---------");
tree.inOrderTraverse(printNode);
console.log("end");



_minNode(), min(), _maxNode(), max()

// _minNode() : 반복적으로 순회하며 최솟값 노드 탐색 (내부 사용)
// tree의 가장 왼쪽 끝 노드가 최솟값
BinarySearchTree.prototype._minNode = function(node){
  if (node === null){
    return null
  }

  while (node && node.left !== null){
    node = node.left
  }

  return node.value
}

// min() : 최솟값 노드 탐색
BinarySearchTree.prototype.min = function(){
  return this._minNode(this.root)
}

// _maxNode() : 반복적으로 순회하며 최댓값 노드 탐색 (내부 사용)
// tree의 가장 왼쪽 끝 노드가 최솟값
BinarySearchTree.prototype._maxNode = function(node){
  if (node === null){
    return null
  }

  while (node && node.right !== null){
    node = node.right
  }

  return node.value
}

// max() : 최댓값 노드 탐색
BinarySearchTree.prototype.max = function(){
  return this._maxNode(this.root)
}

let tree = new BinarySearchTree();

tree.insert("F");
tree.insert("B");
tree.insert("A");
tree.insert("D");
tree.insert("C");
tree.insert("E");
tree.insert("G");
tree.insert("I");
tree.insert("H");

console.log(tree.min()) // A
console.log(tree.max()) // I



search(), _searchNode()

// _searchNode() : 재귀로 트리를 순회하며 값을 만족하는 노드 탐색
BinarySearchTree.prototype._searchNode = function (node, value) {
  if (node === null) {
    return false;
  }

  if (node.value === value) {
    return true;
  } else if (node.value > value) {
    return this._searchNode(node.left, value);
  } else if (node.value < value) {
    return this._searchNode(node.right, value);
  }

  return node.value;
};

// search() : value 노드 탐색
BinarySearchTree.prototype.search = function (value) {
  return this._searchNode(this.root, value);
};

let tree = new BinarySearchTree();

tree.insert("F");
tree.insert("B");
tree.insert("A");
tree.insert("D");
tree.insert("C");
tree.insert("E");
tree.insert("G");
tree.insert("I");
tree.insert("H");

console.log(tree.search("J")); // false
console.log(tree.search("I")); // true



remove(), _removeNode(), findMinNode()

// _findMinNode() : 반복적으로 트리를 순회하며 최솟값을 보유한 노드 탐색
BinarySearchTree.prototype._findMinNode = function (node) {
  while (node && node.left !== null) {
    node = node.left;
  }
  return node;
};

// _removeNode() : 재귀로 트리를 순회하며 값을 만족하는 노드를 찾고 삭제
BinarySearchTree.prototype._removeNode = function (node, value) {
  if (node === null) {
    return null;
  }
  if (node.value === value) {
    // case 1 : leaf node
    if (node.left === null && node.right === null) {
      node = null;
    }
    // case 2 : 1 child node
    else if (node.left === null) {
      node = node.right;
    } else if (node.right === null) {
      node = node.left;
    }
    // case 3 : 2 child node
    else {
      // 오른쪽 노드의 가장 작은 값을 node 로 교체
      let aux = this._findMinNode(node.right);
      node.value = aux.value;
      // 🤔
      node.right = this._removeNode(node.right, aux.value);
    }
  } else if (node.value > value) {
    node.left = this._removeNode(node.left, value);
  } else if (node.value < value) {
    node.right = this._removeNode(node.right, value);
  }
  return node;
};

// remove() : 노드 삭제
BinarySearchTree.prototype.remove = function (value) {
  root = this._removeNode(this.root, value);
};

let tree = new BinarySearchTree();

tree.insert("F");
tree.insert("B");
tree.insert("A");
tree.insert("D");
tree.insert("C");
tree.insert("E");
tree.insert("G");
tree.insert("I");
tree.insert("H");

// callback
function printNode(node) {
  process.stdout.write(`${node.value} -> `);
}

// console.log("---------중위---------");
// tree.inOrderTraverse(printNode);
// console.log("end");

tree.inOrderTraverse(printNode);
console.log("");
tree.remove("A");
tree.inOrderTraverse(printNode);
console.log("");
tree.remove("D");
tree.inOrderTraverse(printNode);
console.log("");
tree.remove("F");
tree.inOrderTraverse(printNode);

// A -> B -> C -> D -> E -> F -> G -> H -> I -> 
// B -> C -> D -> E -> F -> G -> H -> I -> 
// B -> C -> E -> F -> G -> H -> I -> 
// B -> C -> E -> G -> H -> I ->