2015년 4월 20일 월요일

[data structure javascript] binary tree


  • 실행환경 : nodejs
전체 코드는 길어서 github로 대체합니다.
데모는 여기
  • javascript를 이용한 binary tree구현
    • node를 구현, left와 right 자식엘리먼트의 주소와 엘리먼트를 저장할 data로 구성
    • tree에는 root를 가르키며, 이후 subtree을 가르키며 트리를 구성
      • javascript에서는 object(객체)에 대해서는 call by reference로 작동된다.
  • binary tree의 특징
    • 탐색시간이 log n(밑2) 이다.
    • 한 node의 subtree는 2개 이하이다.
      • 구현에서는 정렬을 위해, 
        • 왼쪽 노드는 부모노드 보다 작은 값을,
        • 오른쪽 노드는 부모 노드보다 큰 값을 넣는다.
  • 위와 같은 방식을 사용할 경우 문제,
    • 트리의 균형이 보장되지 않는다.
  • 해결방법
    • avl, red black 트리 등이 있다.
  • 삽입,
    • case 1. root가 비어있을 경우
      • root에 값을 넣는다.
    • case 2. root(node)에 값이 있을 경우
      • 1-1) 값을 비교하여 작을 경우 왼쪽 노드를 따라 간다.
      • 1-2) 값을 비교하여 클 경우 오른쪽 노드를 따라간다.
      • 2-1) 해당 위치가 비어 있지 않다면 case 2를 반복한다.
      • 2-2) 해당 위치가 비어 있다면 값을 넣어준다.
        • 부모노드의 해당 위치에 노드를 연결한다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
tree.prototype.add = function(element,node){
 //루트 부터 시작
 var node = node||this.root;

 //루트가 null, 즉 트리가 비어있을 경우
 if(this.root == null){
  this.root = new NODE(element);
 }

 //루트가 비어있지 않을 경우
 else{
  if(element<node.data){
   if(node.left == null){
    node.left = new NODE(element);
   }
   else{
    this.add(element,node.left);
   }
  }
  else if(element>=node.data){
   if(node.right == null){
    node.right = new NODE(element);
   }
   else{
    this.add(element,node.right);

   }
  }
 }

 console.log("-------------------------------------------------------------");
 console.log("insert ",element);
 console.log("-------------------------------------------------------------");
 this.print();
}

  • 탐색
    • 1. 찾으려는 값과 root(node)와 값을 비교한다.
    • 2-1) 작을 경우 왼쪽 node를 따라간다.
    • 2-2) 클 경우 오른쪽 node를 따라간다.
    • 3. 같은 값이 나올때까지 1-2를 반복한다. 가르키는 노드가 비어있다면 null를 비교한다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
tree.prototype.search = function(element, node){
 var node = node||this.root;

 target = null;
 if(node.data == element){
  target = node;
 }
 else if(element < node.data){
  target = this.search(element,node.left);
 }
 else{
  target = this.search(element,node.right);
 }

 return target;

}

  • 삭제
    • 해당 노드를 찾는다. 이때 부모 노드도 기억한다.
      • stack을 이용하여 찾으려는 노드의 모든 경로를 기억한다.
      • 부모노드는 stack의 top에 해당하는 노드의 바로 아래에 위치해 있을 것이다.
    • case 1, subtree가 없을 경우
      • 부모노드로부터 해당 노드를 삭제한다.
    • case 2, subtree가 1개 이상일 경우 후보를 찾는다.
      • 해당 노드 자리에 후보노드를 대체한다.
------------

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
tree.prototype.search2 = function(stack,element,node){
 var node = node||this.root;
 stack.push(node);

 if(node.data == element){
 }
 else if(element < node.data){
  this.search2(stack,element,node.left);
 }
 else{
  this.search2(stack,element,node.right);
 }
}


tree.prototype.del = function(element,node){
 node = node||this.root;
 // console.log(target);
 console.log("-------------------------------------------------------------");
 console.log("del "+element);
 console.log("-------------------------------------------------------------");

 target = null;
 parent = null;
 selected_node = null;
    

 var S = new stack();
    this.search2(S,element);
    // S.print();
    target = S.pop();
    parent == null;
    if(!S.isEmpty()){
     parent = S.pop();
    }

 this.renewDH(target);

 left_parent = target;
 left_node = target.left;
 if(left_node){
  while(left_node.right){
   left_node = left_node.right;
  }
 }

 right_parent = target;
 right_node = target.right;
 if(right_node){
  while(right_node.left){
   right_parent = right_node;
   right_node = right_node.left;

  }
 }

 left_depth = left_node==null?0:left_node.depth;
 right_depth = right_node==null?0:right_node.depth;



 if(target.height == 1){
  if(parent == null){
   this.root = null;
  }
  else if(parent.left == target){
   parent.left = null;
  }
  else{
   parent.right = null;
  } 
 }
 else if(left_depth>right_depth){
  selected_node = left_node;
  selected_parent = left_parent;
  if(left_depth == 1){
   selected_node.right = target.right;
   if(parent == null){
    this.root = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
  else if(left_depth >= 2){
   selected_parent.right = selected_node.left;
   selected_node.left = target.left;
   selected_node.right = target.right;
   if(parent == null){
    this.root  = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
 }

 else if(left_depth<=right_depth){
  selected_node = right_node;
  selected_parent = right_parent;
  if(right_depth == 1){
   selected_node.left = target.left;
   if(parent == null){
    this.root = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
  else if(right_depth >= 2){
   selected_parent.left = selected_node.right;
   selected_node.left = target.left;
   selected_node.right = target.right;
   if(parent == null){
    this.root  = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
 }

    this.print();

}

  • 후보노드
          • 이것은 만드는 사람이 정하기 나름!
    • 왼쪽 방향
      • 해당노드의 left node를 시작으로 right node가 null일 경우 까지 계속 따라 내려간다.
    • 오른쪽 방향
      • 해당노드의 right node를 시작으로 left node가 null일 경우 까지 계속 따라 내려간다.
    • 두 노드 중에 depth가 큰 노드를 후보노드로 선정한다.

  • 구현에 있어서의 특징,
    • javascript의 특성상 closure의 특징 때문에 height를 구하는 점에 있어서 문제가 생긴다.  (node_left, node_right의 값이 recursive하며 계속하여 달라진다.)
      • 이를 해결하기 위해 stack를 사용함.
    • 출력에 있어서 깊이 우선 탐색을 하여 높은 노드부터 순차적으로 출력하도록 하였다. 부모노드 부터 순차적으로 기록하기 위해 queue를 사용하였다.




코드는 길어서 github로 대체합니다.
아래 github또는 블로그 내에 다른 linked list, stack, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure
작성자: 시간:
라벨: , , , , ,

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)