자료 구조 구현하기 - BST, graph, tree

BST : Binary Search Tree

 

pseudocode && implementation

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

1. insert(value)

• 전달 인자로 받은 value 값이 현재 노드의 값보다 작으면
  •  this.left 가 있는지 확인해서 있으면 this.left에 대해서 재귀하고
  • 없으면 this.left에 새 노드를 추가한다.

• 전달 인자로 받은 value 값이 현재 노드의 값보다 크면
  • this.right 가 있는지 확인해서 있으면 this.right에 대해서 재귀하고
  • 없으면 this.right에 새 노드를 추가한다.

insert(value) {
    // 이진 탐색 트리에 노드를 추가한다.
    if(value < this.value){
      if(this.left){
        return this.left.insert(value);
      }else{
        this.left = new BinarySearchTreeNode(value);
      }
    }else if(value >= this.value){
      if(this.right){
        return this.right.insert(value);
      }else{
        this.right = new BinarySearchTreeNode(value);
      }
    }
  }

 

2. contains(value)

 // 해당 노드가 존재하는지 여부를 판단한다.

 

• 전달인자가 this.value와 같으면 true를 리턴한다.
• 전달인자가 this.value보다 작은 경우
  • this.left가 빈 노드가 아니면 this.left에 대해서 contains(value) 메소드를 실행하고
  • 빈 노드이면 false를 리턴한다.(값을 찾지 못하고 끝났으니 노드가 존재하지 않는다고 판단)
• 전달인자가 this.value보다 큰 경우
• this.right가 빈 노드가 아니면 this.left에 대해서 contains(value) 메소드를 실행하고 
• 빈 노드이면 false를 리턴한다.(값을 찾지 못하고 끝났으니 노드가 존재하지 않는다고 판단)

 

contains(value) {
    // 해당 노드가 존재하는지 여부를 반환한다.
    if(value === this.value){
      return true;
    }
    else if(value < this.value){
      if(this.left){		// ref: return !!(this.left&& this.left.contains(value))
        return this.left.contains(value);
      }
      else{
        return false;
      }
    }
    else if(value > this.value){
      if(this.right){		// ref: return !!(this.right&& this.right.contains(value))
        return this.right.contains(value);
      }
      else{
        return false;
      }
    }
  }
  
 

 

reference code 중

return !! (this.left && this.left.contains(value)) 의 double not(!!) operator

: 아무 값이나 boolean 원시값으로 강제 변환할 수 있다. 변환의 결과는 피연산자 값의 truthyness, falsyness를 따른다.

 

 

3. inorder(callback) 

// 이진 탐색 트리를 중위 순회한다. (왼쪽 - 부모 - 오른쪽 순)

 

• 왼쪽 노드가 비어 있지 않으면
  • 왼쪽 노드에 대해 재귀한다.
• 현재 노드의 값으로 콜백함수를 실행한다.
• 오른쪽 노드가 비어 있지 않으면
  • 오른쪽 노드에 대해 재귀한다.

inorder(callback) {
    //왼쪽 - 부모 - 오른쪽 순회
    if(this.left){
    this.left.inorder(callback);
    }
    callback(this.value);
    if(this.right){
    this.right.inorder(callback);
    }
  }

 

 

graph

pseudocode && implementation

class Graph {
  constructor() {
    /*
     *  ex)
     *    nodes = {
     *      0: [ 1, 2 ],  // 노드를 키로, 이웃들을 배열에 넣음
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }
     */
    this.nodes = {};
  }

 

 

1. addNode(node)

// 그래프에 노드를 추가한다.

노드들의 집합인 nodes 객체는 각 노드를 키로, 엣지들을 담은 배열을 값으로 가진다.

 

• this.nodes[node]가 참이면 즉, 값이 있으면 그걸 활용하고 없으면 새 배열을 만든다.

addNode(node) {
    this.nodes[node] = this.nodes[node] || [];  // OR 연산자*
  }

 

 

2. contains(node)

// 그래프에 해당 노드가 존재하는지 여부를 판단한다.

• this.nodes[node]가 참이면 즉, 값이 있으면 true를, 없으면 false를 리턴한다.

contains(node) {
    return ((node in this.nodes)? true : false);
  }
  
  // reference
  return !!this.nodes[node];

 

3. removeNode(node)

// 그래프에서 노드를 삭제한다.

• 객체에서 값을 삭제하는 것처럼 해당 노드를 삭제한다.
• 노드가 없어졌으므로 인접한 노드들과 간선도 삭제한다.
  • for loop를 통해 모든 키(노드)를 조회해서 해당 노드가 삭제된 노드를 값(배열)에 포함하고 있는지 확인한다.
    • 포함하고 있으면 배열에서 삭제한다.
      • array.splice(start index, delete count) 를 활용해서 몇 번째 인덱스에서 삭제할 인덱스의 갯수를 정할 수 있다.
        • array : this.nodes[key]
        • start index : this.nodes[key].indexOf(node)
        • delete count : 1

removeNode(node) {
    delete this.nodes[node];
    for(let key in this.nodes){
      if(this.nodes[key].includes(node)){
        //delete this.nodes[key];
        this.nodes[key].splice(this.nodes[key].indexOf(node),1)
        
      }
    }
  }
  
  //reference
  if(this.contains(node)){
  	for(let i=0; i < this.nodes[node].length; i+=1){
    	this.removeEdge(this.nodes[node][i], node);
       }
       delete this.nodes[node];
     }
   }

 

 

 

4. hasEdge(fromNode, toNode)

// fromNode와 toNode 사이의 간선 존재 여부를 반환한다.

 

• fromNode 라는 키가 가지는 값(배열)에 toNode를 포함하고 있는지 확인한다.

hasEdge(fromNode, toNode){
  return (this.nodes[fromNode].includes(toNode) && this.nodes[toNode].includes(fromNode));
}


//reference
if(!this.contains(fromNode)){
  return false;
 }
 return !!this.nodes[fromNode].includes(toNode);
 }

 

 

5. addEdge(fromNode, toNode)

// fromNode와 toNode 사이의 간선을 추가한다.

 

• 중복으로 추가되는 것을 방지하기 위해 fromNode에 값으로 toNode를 포함하고 있지 않은 경우에
  • fromNode가 값으로 가지는 배열에 toNode를 푸쉬한다.
  • toNode를 값으로 가지는 배열에 fromNode를 푸쉬한다.

addEdge(fromNode, toNode){
if(!this.hasEdge(fromNode, toNode){ // 여기를 hasEdge를 써서 바꿀 수 있나?
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }
}

//reference
if (!this.contains(fromNode)) {
      return false;
    }
    return !!this.nodes[fromNode].includes(toNode);
  }

  addEdge(fromNode, toNode) {
    if (!this.contains(fromNode) || !this.contains(toNode)) {
      return;
    }

    // Add an edge to each node pointing to the other
    if (!this.hasEdge(fromNode, toNode)) {
      this.nodes[fromNode].push(toNode);
    }

    if (!this.hasEdge(toNode, fromNode)) {
      this.nodes[toNode].push(fromNode);
    }
  }

 

 

6. removeEdge(fromNode, toNode)

// fromNode와 toNode 사이의 간선을 삭제한다.

 

• fromNode가 값으로 toNode를 포함하고 있으면
  • fromNode가 값으로 가지는 배열에서 toNode를 삭제한다.
  • toNode가 값으로 가지는 배열에서 fromNode를 삭제한다.

removeEdge(fromNode, toNode) {
    if(this.hasEdge(fromNode, toNode){
      this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode),1);
      this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode),1);
    }
  }
  
  //reference
  
  if (!this.contains(fromNode) || !this.contains(toNode)) {
      return;
    }

    // Remove edges from each node's edge list
    if (this.hasEdge(fromNode, toNode)) {
      const index1 = this.nodes[fromNode].indexOf(toNode);
      this.nodes[fromNode].splice(index1, 1);
    }

    if (this.hasEdge(toNode, fromNode)) {
      const index2 = this.nodes[toNode].indexOf(fromNode);
      this.nodes[toNode].splice(index2, 1);
    }
  }

 

 

 

tree

pseudocode && implementation

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

 

1. insertNode (value)

// 트리에 노드를 추가한다.

 

• new 키워드를 사용해서 'node'라는 이름의 instance를 만든다.
• 자식 노드들의 집합인 this.children 배열에 푸쉬한다.

insertNode(value) {
    let node = new TreeNode(value);
    this.children.push(node)	//this.children.push(new TreeNode(value))
  }

 

2. contains (value)

// 트리에 해당 노드가 존재하는지 여부를 반환한다.

 

• 결과값을 담을 변수를 선언하고 기본값으로 false를 할당한다.
• 전달인자로 받은 value가 현재 값과 같으면 result에 true를 담는다.
• 그렇지 않을 경우
  • 자식 노드가 있으면 for loop를 돌려서 this.children[i]에 대해 재귀한 후 값을 찾으면 true를 result에 담도록 한다.
• 그렇지 않을 경우 default인 false를 리턴하도록 한다.

contains(value) {
    // this.children 배열을 이용해서 순회하도록 for loop
    let result = false;
    if(this.value === value){
      result = true;
    }else{
      if(this.children.length > 0){
        for(let i = 0; i < this.children.length; i++){
          result = this.children[i].contains(value);
          if(result) break;
       }
      }
    }
    return result;
  }
  
  //reference
  
  if (this.value === value) {
      return true;
    }

    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
    return false;
  }

 

 

 

과제를 마치며 배운 점

 

• 클래스에서 인스턴스를 생성하고 활용하는 법
• 클래스에서 메소드를 만드는 방법
• 클래스에서 this 활용하는 법
• 수도코드를 작성하면 확실히 가이드가 잡힌다.
• 코드를 구현하고 테스트파일에 있는 테스트 케이스들을 활용해서 테스트 하는 법
• 페어와 깃헙을 이용해 협업하는 법
  • git remote 명령어에 대해 조금 더 알아보았다.
  • git pull pair master 를 통해 상대방의 repository에서 pull 해 오기
  • pull 한 후 내가 다시 커밋하고 푸쉬해야 github에 상대방의 commit 기록도 나온다는 사실!
  •  conflict 해결도 해 보았다.
• double not operator