[Algorithm]BinaryTree, BinaryTreeSearch

Mayton·2022년 9월 17일
0

Coding-Test

목록 보기
26/37

kakao2019길찾기게임 문제 풀이 중 이전 알고리즘 강의를 들으면서는 이해했다고 생각했지만, 실제 코테에서 활용하려다 보니 제대로 구현할 수 없었던 알고리즘 이해를 위한 정리 블로그입니다.

이진 트리(Binary Tree)란?

자식노드가 최대 두개인 노드들로 구성된 트리
종류는 full binary tree, complete binary tree, balanced binary tree 3가지가 있다.

Full Binary Tree

모든 레벨에서 노드들이 꽉 채워진 이진트리
가장 많이 나오는 문제로 레벨에 따른 노드의 숫자가 있다.

이미지 출처:https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

complete binary tree

마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉채워진 이진트리


이미지 출처:https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

Full Binary Tree와 Complete Binary Tree는 다음과 같은 관계를 지닌다.

left_index = 2*index+1;
right_index= 2*index+2;

balanced binary tree

모든 잎새노드의 깊이 차이가 많아야 1인 트리를 말한다.

이진트리의 구현

기본적인 이진트리의 구조

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

function BinaryTree(){
  this.root=null
}

삽입

삽입하는 값이 node.value보다 작으면 node.left, 크거나 같으면 node.right에 insert 해준다.

Binary.prototype._insertNode= function(node,value){
  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;
}

Binary.prototype.insert(value){
  this.root=this._insertNode(this.root,value);
}

전위순회

Binary.prototype._preOrderTraverseNode= function(node,callback){
  if(node===null){
    return;
  }
  callback(node);
  this._preOrderTraverseNode(node.left,callback);
  this._preOrderTraverseNode(node.right,callback);
}

Binary.prototype.proOrderTraverse=function(callback){
	this._preOrderTraverseNode(this.root, callback);
}

후위순회

BinaryTree.prototype._postOrderTraverseNode = function (node, callback) {
  if (node === null) {
    return;
  }
  this._postOrderTraverseNode(node.left, callback);
  this._postOrderTraverseNode(node.right, callback);
  callback(node);
};

BinaryTree.prototype.postOrderTraverse = function (callback) {
  this._postOrderTraverseNode(this.root, callback);
};

중위순회

BinaryTree.prototype._inOrderTraverseNode = function (node, callback) {
  if (node === null) {
    return;
  }
  this._inOrderTraverseNode(node.left, callback);
  callback(node);
  this._inOrderTraverseNode(node.right, callback);
};

BinaryTree.prototype.inOrderTraverse = function (callback) {
  this._inOrderTraverseNode(this.root, callback);
};

이진탐색트리(Binary Search Tree)란?

이진탐색트리란 이진탐색과 연결리스트를 결합한 자료구조의 일종으로, 이진탐색의 효율적인 탐색능력을 유지하면서, 빈번한 자료 입력과 삭제를 가능하도록 하였다.

이진탐색은 탐색의 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 되지 않는데 비해, 연결리스트는 자료 입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만, 탐색하는데 O(n)의 계산 복잡성이 발생한다.

이진탐색트리는 중위순회방식을 사용하고, 삽입하는 방식도 이진트리와 동일하다.

삽입

Binary.prototype._insertNode= function(node,value){
  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;
}

Binary.prototype.insert(value){
  this.root=this._insertNode(this.root,value);
}

중위순회방식

BinaryTree.prototype._inOrderTraverseNode = function (node, callback) {
  if (node === null) {
    return;
  }
  this._inOrderTraverseNode(node.left, callback);
  callback(node);
  this._inOrderTraverseNode(node.right, callback);
};

BinaryTree.prototype.inOrderTraverse = function (callback) {
  this._inOrderTraverseNode(this.root, callback);
};

최소값

node의 가장 왼쪽에 있는 값이 제일 작은 값이다.

Binary.prototype._minNode = function(node){
  if(node===null){
   return null; 
  }
  
  while(node && node.left !==null){
    node=node.left;
  }
  
  return node.value;
}

Binary.prototype.min=function(){
  return this._minNode(this.root);
}

최대값

node의 가장 오른쪽에 있는 값이 제일 큰 값이다.

Binary.prototype._maxNode=function(node){
  if(node===null){
    return null;
  }
  
  while (node && node.right !== null) {
    node = node.right;
  }
  return node.value;
}

Binary.prototype.max=function(){
  return this._maxNode(this.root);
}

탐색

value가 node.value보다 작으면 왼쪽, 크면 오른쪽에 있다는 점을 이용해서 찾는다.

Binary.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);
  }
}

Binary.prototype.search=function(value){
  return this._searchNode(this.root, value);
}

삭제

값을 찾았을 때 왼쪽 노드, 오른쪽 노드가 없을 때를 각각 확인하고, 모두 있다면 오른쪽 노드에서 가작 작은값을 삭제한 값의 위치에 올린다.

BinaryTree.prototype._findMinNode(node){
  while(node && node.left !==null){
    node=node.left;
  }
  return node;
}

BinaryTree.prototype._removeNode=function(node,value){
  if(node===null){
    return null
  }
  if(node.value===value){
    if(node.left === null && node.right ===null){
      node = null;
    }else if (node.left===null){
      node=node.right;
    }else if (node.right===null){
      node=node.left
    }else{
      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;
}

BinaryTree.prototype.remove(value){
  this.root = this._removeNode(this.root, value)
}
profile
개발 취준생

0개의 댓글