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
작성자: 시간: 댓글 없음:
라벨: , , , , ,

2015년 4월 19일 일요일

[data structure javascript] Linked List


  • 실행환경 : nodejs

  • javascript를 이용한 linked list구현
    • node를 구현, 단순 linked list 이기 때문에 다음 느드를 가르키는 next와, 엘리먼트를 저장할 data로 구성
    • node를 출력하면 다음 노드, 다음 노드의 다음노드, 다음 노드의 다음 노드의 다음 노드..... 쭈욱 출력이 되지만, 실제로는 객체 값이 저장되는 것이 아니라 주소를 가르키고 있다.
      • javascript에서는 object(객체)에 대해서는 call by reference로 작동된다.
  • linked_list의 특징
    • 노드로 구성
    • 노드에는 값과 다음 값에 대한 주소를 가지고 있다.
  • 장정
    • 크기에 제한을 가지고 있지 않다.
    • 중간 삽입, 삭제가 array에 비하여 쉽다.
    • 삽입, 삭제에 대한 비용이 적다. O(1)
    • 때문에 c,c++ 등에서 자료구조를 구현할때 linked list를 주로 활용한다.
  • 단점
    • 탐색에 있어서 단방향이다.
    • 탐색에 대하여 비용이 크다. O(n)
    • 때문에 삽입,삭제 에 있어서 이전 노드의 주소(객체)의 정보를 가지고 있어야 한다.
    • 이중 연결 리스트가 방안이 될 수 있다.
  • linked list용어
    • node
      • 하나의 객체로, 값과 다음 값으로 이루어 져 있다.
  • 자매품
    • 환영 연결 리스트
    • 이중 연결 리스트
  • 삽입 방법
    • 삽입 할 노드의 앞의 노드를 찾는다. (이전노드)
    • 이전 노드의 next의 주소를 삽입할 노드의 next로 넣는다.
    • 이전 노드의 next의 주소를 삽입할 노드의 주소를 넣는다.

  • 삭제 방법
    • 삽입 반대로.





  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
var linkedList = function(){
 this.length = 0;
 this.headNode = new node(null);
}


var node = function(element){
 this.data = element;
 this.next = null;
}

linkedList.prototype.add = function(element,position){
 
 //position이 null일 경우 마지막위치로
 var position = position==undefined?this.length+1:position;
 
 //입력값으로 node 생성

 var newNode = new node(element);

 var preNode = this.headNode;
 for(i = 1;i<position;i++){
  preNode = preNode.next;
 }
 newNode.next = preNode==null?null:preNode.next;
 preNode.next = newNode;

 this.length++;

 // console.log("-------------------------------------------");
 // console.log("add",element);
 // console.log("position",position);
 // console.log("-------------------------------------------");
 // this.print();
}

linkedList.prototype.remove = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;
  preNode.next = preNode.next.next;
  
  this.length--;
 }
 else{
  console.log("index error");
 }

 // console.log("-------------------------------------------");
 // console.log("position",position);
 // console.log("remove",ret);
 // console.log("-------------------------------------------");
 // this.print();
 return ret;
}


linkedList.prototype.peek = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;

 }
 else{
  console.log("index error");
 }

 return ret;
}

linkedList.prototype.print = function(position){
 var str = "linkedList : ";
 var node = this.headNode.next;
 while(node != null){
  str += node.data;
  str += " -> ";
  node = node.next;
 };
 console.log(str);
}


linkedList.prototype.isEmpty = function(){
 var ret = false;
 if(!this.length){
  ret = true;
 }

 return ret;
}

// list = new linkedList();

// list.add(1);

// list.add(2);

// list.add(3);

// list.add(3,1);

// list.add(1);

// list.remove();
// list.remove(3);

아래 github또는 블로그 내에 다른 tree, stack, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure
작성자: 시간: 댓글 없음:
라벨: , , , , ,

[data structure javascript] Stack

  • 실행환경 : nodejs
  • javascript를 이용한 stack 구현
    • 배열의 구조,api를 활용
    • javascript의 약한 언어의 특징 때문에 쉬운 구현이 가능
      • 때문에 크기에 제한을 두지 않는다.(메모리 크기까지 가능)
      • javascript의 array 메소드에 push, pop을 활용하여 간단한 구현을 하였습니다.
  • stack의 특징
    • last in first  out, first in last out 특징
    • 인터럽트, tree의 전위 순회 등에 쓰인다.
      • (제 tree의 구현에 사용했습니다.)
  • stack용어
    • push(,= put)
      • 삽입, stack의 맨 위에 해당 엘리먼트를 삽입한다.
    • pop(,= get)
      • 삭제, stack의 맨 위에 해당하는 엘리먼트를 리턴, 삭제한다.
    • top
      • 맨 위의 값, push한 값, pop이 될 값이 된다.
    • buttom
      • 맨 아래, top == buttom이라면 stack이 비었음을 의미한다.


 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
var stack = function(){
 this.datas = [];
}


stack.prototype.isEmpty = function(){
  return this.datas.length==0?true:false;
}
stack.prototype.length = function(){
 return this.datas.length;
}
stack.prototype.push = function(element){

 this.datas.push(element);
 // console.log("-------------------------------------------------------------");
 // console.log("push ",element);
 // console.log("-------------------------------------------------------------");
 // this.print();

}
stack.prototype.pop = function(){
 element = this.peek();
 this.datas.pop();
 // console.log("-------------------------------------------------------------");
 // console.log("pop!");
 // console.log("return",element);
 // console.log("-------------------------------------------------------------");
 // this.print();
 return element;
}
stack.prototype.peek = function(){
 element = this.datas[this.datas.length-1]==undefined?null:this.datas[this.datas.length-1];
 return element;
}
stack.prototype.toArray = function(){
 return this.datas;
}
stack.prototype.print = function(){
 var tmp = this.datas;
 for(i=tmp.length-1;0<=i;i--){
  console.log("│ "+this.datas[i]+" │");
 }
 console.log("└---┘");
}

stack.prototype.delAll = function(){
 this.datas = [];
}

// S = new stack();

// S.push(3);
// S.push(5);
// S.push(1);
// S.push(6);

// S.pop();

// S.pop();

// S.push(9);
// S.push(8);

module.exports = stack;


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

[data structure, javascript] Queue


  • 실행환경 : nodejs
  • javascript를 이용한 queue 구현
    • 배열의 구조,api를 활용
    • javascript의 약한 언어의 특징 때문에 쉬운 구현이 가능
      • 때문에 크기에 제한을 두지 않는다.(메모리 크기까지 가능)
      • 같은 의미로서 linked list로 구현하는 큐의 장점( 큐의 크기에 제한이 적다)라는 점 역시 가지고 있다.
      • splice라는 array함수를 이용하여 중간 삽입도 쉽게 구현이 가능하다.
        • (구현 안 한건 비밀)
      • shift 함수를 이용하여 font,rare의 인덱스를 관리하지 않아도 되게끔 구현하였다.
  • queue의 특징
    • first in first  out, last in last out 특징
    • tree의 깊이 우선탐색, sliding window 등 주로 순서 처리의 시스템에 쓰인다.
  • queue 용어
    • enqueue (,= put)
      • 삽입, queue의 맨뒤에 해당 엘리먼트를 삽입한다.
    • dequeue (,= get)
      • 삭제, queue의 맨 앞에 해당하는 엘리먼트를 리턴, 삭제한다.
    • rare
      • 맨 뒤의 값, enqueue 한 값을 가르키게 된다.
    • front (,= head)
      • 맨앞의 값, dequeue의 대상이 된다.


 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
 var queue = function(){
  this.datas = [];
 }

 queue.prototype.isEmpty = function(){
   return this.datas.length==0?true:false;
 }
 queue.prototype.length = function(){
  return this.datas.length;
 }
 queue.prototype.enqueue = function(element){
  this.datas.push(element);
  // console.log("-------------------------------------------------------------");
  // console.log("enqueue ",element);
  // console.log("-------------------------------------------------------------");
  this.print();

 }
 queue.prototype.dequeue = function(){
  element = this.peek();
  this.datas.shift();
  // console.log("-------------------------------------------------------------");
  // console.log("dequeue, return ",element);
  // console.log("-------------------------------------------------------------");
  // this.print();
  return element;
 }
 queue.prototype.peek = function(){
  element = this.datas[0]==undefined?null:this.datas[0];
  return element;
 }
 queue.prototype.toArray = function(){
  return this.datas;
 }
 queue.prototype.print = function(){
  console.log(this.datas);
 }

 queue.prototype.delAll = function(){
  this.dats = [];
 }

 // Q = new queue();

 // Q.enqueue(5);
 // Q.enqueue(3);
 // Q.dequeue();
 // Q.enqueue(8);
 // Q.enqueue(7);
 // Q.dequeue();
 // Q.enqueue(9);
 // Q.enqueue(10);
 // Q.dequeue();

 module.exports = queue;



아래 github또는 블로그 내에 다른 stack, linked list, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure
작성자: 시간: 댓글 없음:
라벨: , , , , ,
피드 구독하기: 글 (Atom)