[Data Structure] 트리

트리란?(Tree)

트리는 자식 노드를 지닌 노드들로 구성된다. 첫 번째이자 가장 상위 노드를 루트 노드(root node)라고 부른다. 일반적인 트리는 자식을 얼마든지 가질 수 있다.

이진트리(Binary Tree)

이진 트리는 자식 노드가 왼쪽, 오른쪽 두 개뿐인 트리다.

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

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

left와 right에 Node들을 연결해주면 된다.

트리의 순회

트리는 모든 항목을 방문하기 위해 왼쪽 포인터와 오른쪽 포인터가 존재한다. 트리의 순회를 위한 방법으로는 선순위(pre-order), 후순위(post-order), 중순위(in-ordere), 단계순위(level-order)이 있다,

선순위 순회

루트, 왼쪽, 오른쪽순으로 노드를 방문하는 순회이다. 재귀적으로 트리를 방문하면 된다. 이때, 왼쪽을 먼저 탐색한 뒤에 오른쪽을 탐색해야 한다.
자식 노드가 없는 노드를 방문하기 전에 루트를 조사할 필요가 있는 경우 선 순위 순회를 사용한다. 그래야 모든 루트를 방문하기 때문이다.

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(node){
    if(!node)
      return;
    traverserInOrderHelper(node.left); //가장 먼저 맨 왼쪽의 노드를 방문한다. 
    console.log(node.value);
    traverseInOrderHelper(node.right);
  }
}

후순위 순회

왼쪽, 오른쪽, 루트 순으로 노드를 방문한다. 조건문을 통해 왼쪽이 있다면 처리하고 그 다음에 오른쪽이 있는지 검사한다. 부모노드를 방문하기 전에 잎 노드를 먼저 조사해야 하는 경우에 사용한다. 잎 노드를 검색할 때 루트를 조사하느라 시간을 낭비하지 않기 때문이다.

BinaryTree.prototype.traversePostOrder = function(){
  traversePostOrder(this._root);
  function traversePostOrderHelper(node){
    if(node.left)
    	traversePostOrderHelper(node.left);
    if(node.right)
    	traversePostOrderHelper(node.right);
    console.log(node.value);
  }
}

단계순위 순회

단계순위 순회는 너비 우선 탐색(Breadth first search)이라고도 부른다.

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

이진검색트리(Binary Search Tree)

BST는 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 큰 트리이다. 검색과 삽입, 특정 값을 지닌 노드 제거의 시간 복잡도가 O(log2(n))이기 때문이다. 하지만 모든 노드가 한쪽에만 몰려있는 불균형 이진 검색 트리가 되면 시간복잡도가 O(n)이 된다.
다음 코드는 삽입 코드이다.

BinarySearchTree.prototype.insert = function(value){
  var thisNode = {left: null, right: null, value: value};
  if(!this._root){ // 루트 노드가 없으면
	this._root = thisNode;
  }else{
    var currendRoot = this._root;
    while(true){
     if(currentRoot.value > value){ 
       //현재 루트가 null이 아닌 경우 증가시키고, null인 경우 삽입
       if(currentRoot.left != null){
         currentRoot = currentRoot.left;
       }else{
         currentRoot = thisNode;
         break;
      }
    }else if(currentRoot.value < value){
      //현재 노드보다 큰 경우 오른쪽에 삽입한다. null이면 증가시키고, null이면 삽입
      if(currentRoot.right != null){
      	currentRoot = currentRoot.right;
      }else{
      	currentRoot.right = thisNode;
        break;
      }
    }else{
      //현재 루트와 값이 같은 경우
     break; 
    }
  }
}

다음 코드는 삭제코드이다. BST에서 노드를 삭제하기 위해서는 3가지 경우를 검토해야 한다.
1. 노드에 자식이 없다.
자식이 없을 경우 null을 반환한다.
2. 노드에 자식이 하나 있다.
현재 자식을 반환한다. 해당 자식이 위 단계로 올라가서 부모를 대체한다.
3. 노드에 자식이 두 개 있다.
노드에 자식이 두 개 있는 경우 왼쪽 하위 트리의 최대치를 찾거나 오른쪽 하이 트리의 최소치를 찾아서 해당 노드를 대체한다.

BinarySearchTree.prototype.remove = function(value){
  return deleteRecursiveley(this._root, value);
  
  function deleteRecursively(root, value){
    if(!root){
    	return null;
    } else if(value < root.value){
    	root.left = deleteRecursively(root.left, value);
    } else if(value > root.value){
    	root.right = deleteRecursively(root.right, value);
    } else{
     	//자식이 없는 경우
      	if(!root.left && !root.right){
          return null;
        } else if(!root.left){ // 자식이 오른쪽인 경우
          root = root.right;
          return root;
        } else if(!root.right){ // 자식이 왼쪽인 경우
          root = root.left;
          return root;
        } 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;
  }
}

마지막으로 BST의 검색이다. BST는 큰 값이 오른쪽, 작은 값이 왼쪽에 있다는 특성을 이용해 시간복잡도 O(log2(n))을 가진다.
현재 루트가 검색 값보다 작은 경우 오른쪽, 큰 경우 왼쪽 자식을 방문한다.

BinarySearchTree.prototype.findNode = function(value) {
    var currentRoot = this._root;
    var found = false;
    while(currentRoot){
        if(currentRoot.value > value){ // 현재 값보다 작으면 왼쪽
            currentRoot = currentRoot.left;
        }else if(currentRoot.value < value){ // 크면 오른쪽
            currentRoot = currentRoot.right;
        }else{ //아니라면 값을 찾았다.
            found = true;
            break;
        }
    }
    return found;
}

AVL트리

이름은 AVL트리를 고안해낸 사람들을 따서 지어졌기 때문에 큰 의미가 없다.

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

AVL트리는 자식의 높이를 기반으로 하며 다음 코드를 통해서 높이를 계산한다.

AVLTree.prototype.setDepthBasedOnChildrend = function(){
    if(this.node == null){
        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;
    }
}

AVL트리는 이진트리의 불균형을 해소하기 위해 회전(Rotation)이라는 방식을 사용하여 자식들을 회전시킨다.

왼쪽 회전

트리의 자식 중 오른쪽 불균형 트리가 되었을 때

AVLTree.prototype.rotateRR = function(){
    var valueBefore = this.value;
    var leftBefore = this.left;
    this.value = this.right.value;
    
    this.left = this.right;
    this.right = this.right.right;
    this.left.right = this.left.left;
    this.left.left = leftBefore;
    this.left.value = valueBefore;

    this.left.setDepthBasedOnChildrend();
    this.setDepthBasedOnChildrend()
}

오른쪽 회전

AVLTree.prototype.rotateLL = function(root){
    var valueBefore = this.value;
    var rightBefore = this.right;
    this.value = this.left.value;
    
    this.right = this.left;
    this.left = this.left.left;
    this.right.left = this.right.right;
    this.right.right = rightBefore;
    this.right.value = valueBefore;

    this.right.setDepthBasedOnChildrend();
    this.setDepthBasedOnChildrend()
}

트리 균형 잡기

AVL 트리의 균형을 확인하기 위해서는 왼쪽 자식과 오른쪽 자식의 높이를 간단히 비교하면 된다.

AVLTree.prototype.balance = function(){
    var ldepth = this.left == null ? 0 : this.left.depth;
    var rdepth = this.right == null ? 0 : this.right.depth;

    if(ldepth > rdepth + 1){
        var lldepth = this.left.left == null ? 0 : this.left.left.depth;
        var lrdepth = this.left.right == null ? 0 : this.left.right.depth;

        if(lldepth < lrdepth){
            this.left.rotateRR(); //현재 노드의 LL회전은 무조건 일어난다.
        }
        this.rotateLL()
    } else if(ldepth + 1 < rdepth){
        var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
        var rldepth = this.right.left == null ? 0 : this.right.left.depth;

        if(rrdepth > rldepth){
            this.left.rotateLL(); //현재 노드의 RR회전은 무조건 일어난다.
        }
        this.rotateRR()
    }
}

삽입

BST와 비슷하지만 깊이 값을 설정해줘야 한다. 시간복잡도는 O(nlog2(n)이다.

AVLTree.prototype.insert = function(value){
    var childInserted = false;
    if(value == this.value){
        return false; //모든 값은 고유해야 한다.
    } else if(value <= this.value){
        if(this.left == null){
            this.left = new AVLTree(value);
            childInserted = true;
        } else{
            childInserted = this.left.insert(value);
            if(childInserted == true) this.balance();
        }
    } else if(value > this.value){
        if(this.right == null){
            this.right = new AVLTree(value);
            childInserted = true;
        } else{
            childInserted = this.left.insert(value);
            if(childInserted == true) this.balance();
        }
    }
    if(childInserted == true) this.setDepthBasedOnChildrend();
    return childInserted;
}