[Non-Linear] 트리구조

트리구조는 위 그림과 같은 형태의 데이터 구조를 말한다.

 

1. 특징 

   1) 1개의 Root Node갖는다.

   2) Root Node는 0개 이상의 Child Node를 갖는다.

   3) Child Node 또한 0개 이상의 Child Node를 갖고 있고, 이는 반복적으로 정의된다.

   4) 트리에는 Cycle이 존재할 수 없다.

   5) 각 Node는 어떤 자료형으로도 표현 가능하며, 부모 Node로의 연결이 있을 수도 없을 수도 있다.

 

2. 종류

  1) 이진트리(Binary tree), 이진검색트리(Binary search tree), 완전이진트리(Complete binary tree),

     전 이진트리(Full binary tree), 포화이진트리(perfect binary tree) 로 구분된다.  

   2) 트리는 균형(balance)이나 비균형(unbalance)냐로 또 구분될 수 있다.

   3) 대표적인 balance 트리는 red-black tree, AVL tree 가 있다.

 

3. 설명

  1) 이진트리(binary tree) 

      (1) 각 Node가 최대 2개의 Child Node를 갖는 트리를 말한다. 사실 모든 트리가 이진트리는 아니다.

      (2) 자식을 3개 가지면 삼진(ternary tree)라고 부른다. 10개 가지면 10진 트리(10차 트리, 10-ary tree)라고 부른다.

예시) Binary Tree

  2) 이진탐색트리(binary search tree)

      (1) 이진트리와는 다르게 특정조건을 만족해야한다.

      (2) 조건 :  모든 왼쪽 Child Node <= 현재 Node < 모든 오른쪽 Child Node 

      (3) (2)사항의 조건은 모든 Node에 대해서 반드시 True 이어야 한다.

이진 탐색트리(좌), 이진탐색트리 아님(우)

  3) 완전이진트리(complete binary tree)

     (1) 트리의 모든 높이(또는 깊이) 에서 Node가 꽉 차있는 이진트리를 말한다.

     (2) 마지막 Child Node는 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

 

왼쪽은 완전이진트리 아님. 오른쪽은 완전이진트리가 맞음.

이것도 완전 이진트리

  4) 전 이진트리(full binary tree)

     (1) 모든 Node의 Child Node가 없거나 정확히 두개 있는 경우를 말함. 

  5) 포화 이진트리(perfect binary tree)

     (1) 전 이진트리 && 완전 이진트리인 경우를 말한다.

     (2) 노드의 갯수는 정확히 (2^K)-1 (K는 depth or height의 수)개 다. 

완전 이진트리 이자 포화 이진트리

4. Functional intantiation

function BinarySearchTree(){
  var Node = function(key){
    this.key = key;
    this.left = null;
    this.right = null;
  };
  
  var root = null;
  //삽입
  this.insert = function(key){
    var newNode = new Node(key);
    
    if(root === null){
      root = newNode;
    }else{
      insertNode(root,newNode);
    }
  }
  //검색
  this.search = function(key){  
    return searchNode(root, key); 
  };

  //삭제
  this.remove = function(key){ 
    root = removeNode(root, key); 
  };  
  //min
  this.min = function(){
    return minNode(root);
  }
  
  //max
  this.max = function(){
    return maxNode(root);
  }
  
  //in order 횡단
  this.inOrderTraverse = function(callback){
    inOrderTraverseNode(root,callback);
  }
  //pre order 횡단
  this.preOrderTraverse = function(callback){ 
    preOrderTraverseNode(root, callback); 
  };
  //post order 횡단
  this.postOrderTraverse = function(callback){  
    postOrderTraverseNode(root, callback); 
  };  
 
  
}

var insertNode = function(node,newNode){
  if(newNode.key < node.key){ //기존값하고 새로 넣는 값하고 비교해서 작으면 왼쪽, 크면 오른쪽
    if(node.left === null){
      node.left = newNode;
    }else{
      insertNode(node.left, newNode);
    }
  }else{
    if(node.right === null){
      node.right = newNode;
    }else{
      insertNode(node.right, newNode);
    }
  }  
};

var inOrderTraverseNode = function(node, callback){
  if(node !== null){
    inOrderTraverseNode(node.left, callback);
    callback(node.key);
    inOrderTraverseNode(node.right, callback);
  }
};


var preOrderTraverseNode = function(node, callback) { 
  if (node !== null) {   
    callback(node.key);   
    preOrderTraverseNode(node.left, callback);   
    preOrderTraverseNode(node.right, callback);  
  } 
};

var postOrderTraverseNode = function(node, callback) {  
  if (node !== null) {        
    postOrderTraverseNode(node.left, callback);                                                               postOrderTraverseNode(node.right, callback); 
    callback(node.key);                          
  } 
}; 

var minNode = function(node){
  if(node){
    while (node && node.left !== null){
      node = node.left;
    }
    return node.key;
  }
  return null;
}

var maxNode = function(node){
  if(node){
    while(node && node.right !== null){
      node = node.right
    }
    return node.key;
  }
  return null;
}

var searchNode = function(node, key){
  if (node === null){ 
    return false;  
  }  if (key < node.key){ 
    return searchNode(node.left, key); 
  } else if (key > node.key){     
    return searchNode(node.right, key);
  } else {    
    return true; 
  } 
}; 

var removeNode = function(node, key){
  if (node === null){ 
    return null;  
  }  if (key < node.key){   
    node.left = removeNode(node.left, key);     
    return node; 
  } else if (key > node.key){     
    node.right = removeNode(node.right, key);   
    return node; 
  } else { // 키값이 노드 키값과 같을 경우
    
    //노드가 마지막 노드일 경우  
    if (node.left === null && node.right === null){      
      node = null;       
      return node;    
    }
    //노드가 자식 1개가진 노드를 제거
    if (node.left === null){    
      node = node.right;       
      return node; 
    } else if (node.right === null){      
      node = node.left;     
      return node; 
    }
    //노드가 자식 2개가진 노드를 제거
    var aux = findMinNode(node.right);  
    node.key = aux.key;    
    node.right = removeNode(node.right, aux.key);    
    return node; 
  } 
};

var findMinNode = function(node){  
  while (node && node.left !== null) {    
    node = node.left;  
  }  
  return node; 
};


function printNode(value){
  console.log(value); 
} 


var tree = new BinarySearchTree(); 
tree.insert(11);
tree.insert(7); 
tree.insert(15); 
tree.insert(5); 
tree.insert(3); 
tree.insert(9); 
tree.insert(8); 
tree.insert(10); 
tree.insert(13); 
tree.insert(12); 
tree.insert(14); 
tree.insert(20); 
tree.insert(18); 
tree.insert(25);
tree.min();

tree.inOrderTraverse(printNode);