Javascript 알고리즘: 트리

💻 자료구조, 알고리즘으로 더 빠른 S/W 만들기 (3)

글 작성자: SoniaComp
공부한 기록을 공유하기 위한 글입니다. 수정할 내용이 있다면 알려주세요!

📕 위 책을 추천하는 이유
JS 코드가 간결해서, 알고리즘의 핵심 논리를 이해하기 정말 쉽다! 👍

Table of the Contents
1. 트리
1.1 이진트리
1.2 이진검색트리
1.3 AVL 트리

🐥우리가 이 자료구조에서 무엇을 유심히 살펴봐야 하는지 짚고 시작해보장!

어떤 자료구조를 선택할 때, 고려해야 할 4가지 기본연산!
접근, 삽입, 삭제, 검색의 ‘시간복잡도’와 ‘공간복잡도’

1. 트리

Github 참고

트리는 자식노드를 지닌 노드로 구성
🌲 Root Node: 최상위 노드

트리의 중요한 연산: 순회 → 모든 노드들에 접근하는 것

function TreeNode(value) {
    this.value = value;
    this.children = [];
}

1.1 이진 트리

자식 노드가 왼쪽, 오른쪽 두 개뿐인 트리
순회 시간복잡도: O(n)

function BinaryTreeNode(value){
    this.value = value;
    this.left = null;
    this.right = null;
}
// 이진트리에는 항상 루트 노드가 있다.
function BinaryTree(){
    this._root = null;
}

선순위 순회(루트, 왼쪽, 오른쪽): 루트 먼저 조사

BinaryTree.prototype.traversePreOrder = function(){
    traversePreOrderHelper(this._root);
    function traversePreOrderHelper(node) {
        if(!node){ return; }
        console.log(node.value);
        // 루트값 접근 이후에 왼쪽, 오른쪽
        traversePreOrderHelper(node.left);
        traversePreOrderHelper(node.right)
    }
}
// 😗다른 구현 방법
// 빈스택을 생성한 다음,
// 루트를 스택에 추가하고, 모든 항목을 하나씩 꺼내는 반복문으로도 구현 가능

중순위 순회(왼쪽, 루트, 오른쪽) : 트리를 생성한 원래 순서대로

BinaryTree.prototype.traverseInOrder = function(){
    traverseInOrderHelper(this._root);
    function traverseInOrderHelper(noe){
        if(!node) return; // 종료조건
        traverseInOrderHelper(node.left);
        console.log(node.value);
        traverseInOrderHelper(node.right);
    }
}
// 😗다른 구현 방법: 반복문 사용
BinaryTree.prototype.traverseInOrderIterative = function(){
    var current=this._root, s=[], done=false;
    while(!done){
        if(current!=null){
            s.push(current);
            current=current.left; // 가장 왼쪽으로 이동
        } else {
            if(s.length){
                current=s.pop();
                console.log(current.value);
                current=current.right);
            } else {
                done=true;
            }
        }
}

후순위 순회(왼쪽, 오른쪽, 루트-현재노드)

// 방법1: 재귀함수 이용(선순위, 중순위 순회 첫번째 방법과 같은 논리)
// 😗다른 구현 방법: 두 개의 스택
BinaryTree.prototype.traversePostOrderIterative = function(){
    var s1=[], s2=[]; // 두 개의 스택
    s1.push(this._root);
    while(s1.length){
        var node=s1.pop();
        s2.push(node); // 두개의 스택: 거꾸로 효과!! 맨 처음이 맨 나중
        if(node.left) s1.push(node.left);
        if(node.right) s1.push(node.right);
    }
    while(s2.legnth){
        var node=s2.pop();
        console.log(node.value);
    }
}

BFS:너비우선검색(각 노드 단계를 방문)

BinaryTree.prototype.traverLevelOrder = function(){
    var root=thie._root, queue=[];
    if(!root) return;
    queue.push(root);
    while(queue.length){
        var temp=queue.shift();
        console.log(temp.value);
        if(temp.left) queue.push(temp.left);
        if(temp.right) queue.push(temp.right);
    }
}

1.2 이진검색 트리

왼쪽 자식이 부모보다 작고, 오른쪽 자식이 부모보다 크다.
순회 시간 복잡도: O(log2(n))

function BinarySearchTree(){
    this._root=null;
}

삽입

BinarySearchTree.prototype.insert = function(value){
  var thisNode = {left:null, right: null, value: value};
  if(!this._root){
      this._root = thisNode;
  }else{
     var currentRoot = this._root;
     while(true){
       if(currentRoot.value>value){
           if(currentRoot.left!=null){currentRoot=currentRoot.left;}
           else{currentRoot.left=this.Node; break;}
       }else if(currentRoot.value<value){
           //left와 같은 논리
       }else{ break; } // 현재 루트와 값이 같은 경우
    }
  }
}

삭제

BinarySearchTree.prototype.remove = function(value){
  return deleteRecursively(this._root, value);
  function deleteRecursively(root, value){
    if(!root){ return null; }
    // 삭제할 value 찾는 중
    else if(value<return.value){
      root.left=deleteRecursively(root.left, value);
    }else if(value>return.value){
      // 여전히 찾는 중인 코드
    }else{ // 찾았다!!!!
      // 1. 자식이 없는 경우 -> 그냥 삭제
      if(!root.left&&!root.right){return null;}
      // 2. 자식이 하나인 경우 -> 자식이 부모 대체  
      else if(!root.left){root=root.right; return root;}
      else if(!root.right){ } //위와 같은 논리
      // 3. 자식이 둘 다 있음-> 왼쪽 하위트리 최대치, 오른쪽 하위 최소치로 대체
      else {
        var temp = findMin(root.right);
        root.value = temp.value;
        root.right = deleteRecursively(root.right, temp.value);
        return root;
      }
    }
    return root;
  }
  function findMin(root){
    while(root.left) root=root.left;
    return root;
  }
}

검색
이진트리의 특징을 이용!

1.3 AVL 트리

스스로 균형을 잡음: 높이를 최소로 유지!
→ 이진검색트리가 한쪽에 치우치지 않게 해줌!!
→ 시간복잡도 log값 보장!!

function AVLTree(value){
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

트리 높이 구하기
depth 값을 항상 모니터링

AVLTree.prototype.setDepthBasedOnChildren = function(){
    if(this.node==null){this.depth=0;}
    else{this.depth=1;}
    if(this.left!=null){this.depth=this.left.depth+1;}
    if(this.right!=null&&this.depth<=this.right.depth{
        this.depth=this.right.depth+1;
    }
}

트리 균형 잡기
단일 회전 코드가 궁금하다면 Github 참고

AVLTree.prototype.balance=function(){
    var ldepth=this.left==null?0:this.left.depth;
    var rdepth=this.rigth==null?0:this.right.depth;
    if(ldepth>rdepth+1){
      // LR 혹은 LL 회전
      var lldepth=this.left.left==null?0:this.left.left.depth;
      var lrdepth=this.left.right==null?0:this.left.right.depth;
      if(lldepthh<lrdepth){this.left.rotateRR();}
      this.rotateLL(); // 현재 노드의 LL은 무조건 발생)
    }else if(ldepth+1<rdepth){ 
      // 위와 같은 논리
    }
}

삽입, 삭제
삽입, 삭제 후 균형을 잡아야 함