[자료구조] 트리 Tree - 자바스크립트(Javascript)로 구현하기

트리(Tree)

트리는 비순차적인 자료 구조로 정보 검색에 용이하다. 
부모 자식 관계를 가진 다수 노드로 구성된다. 

밑의 그림과 같이 트리 모양의 자료구조를 트리라고 하는 것이다.

루트 root:  트리의 최상위 노드로 루트라고 한다. 그림에서는 12값을 가진 노드에 해당한다. 

서브트리: 노드와 자식 노드로 구성되어있다. 그림에선 5,3,6 / 9,8,10 / 17,14,22 등이 해당한다. 

 

노드

위에서 트리는 노드로 구성되어 있다고 하였다. 노드는 왼쪽 자식과 오른쪽 자식의 참조(포인터)를 가리킨다.

위의 그림에서 3,6,8,10,13,15,18,23 키에 해당하는 노드들은 자식이 없으므로 왼쪽 자식 참조 값과 오른쪽 자식 참조 값이 null이 된다. 

루트 노드를 그림으로 나타내면 위와 같다. 

이때 노드에서 루트의 값 12를 Key라고 한다.

그리하여 노드를 생성하기 위한 코드는 다음과 같다.

class Node {
  constructor(key) {
    this.key = key; // 키 값
    this.left = null; // 왼쪽 자식 포인터
    this.right = null; // 오른쪽 자식 포인터
  }
}

왼쪽 자식 참조(포인터), 오른쪽 자식 참조(포인터)라는 말이 이해가 안간다면
왼쪽 자식이 누구인지 가리키는 화살표, 오른쪽 자식이 누구인지 가리키는 화살표 즉 화살표 역할이라고 생각하면 된다. 
코드 상에선 left 와 right로 표기한다. 

 

이진 트리

이진 트리의 노드는 왼쪽, 오른쪽 자식 총 하나씩 즉 최대 2개의 자식 노드를 가질 수 있다.

이진 탐색 트리

이진 트리에서 파생된 이진 탐색 트리는 항상 왼쪽 자식 노드엔 작은 값을 오른쪽 자식 노드에는 큰 값을 가진다. 

우리는 이진 탐색 트리에 대해 자바스크립트로 코드를 만들어 볼 것이다. 

 

트리 구현 시 필요한 메소드는 다음과 같다.

• 삽입 ( 새로운 키를 삽입 )
• 삭제 ( 키를 삭제 )
• 검색 ( 찾고자 하는 값이 트리에 존재하는지 확인 )
• 최솟값 찾기
• 최댓값 찾기

삽입

  insert(val) {
    let newNode = new Node(val);  // 추가할 "새 노드" 생성
    if (this.root === null) { // 루트가 비어있는 경우
      this.root = newNode;
    } else { // 루트가 비어있지 않은 경우
      insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) { // 비교 노드와 새 노드를 인자로 받는다. 
    if (newNode.key < node.key) { // "새 노드" 값이 비교 노드 값보다 작으면
      if (node.left === null) { // 비교 노드의 왼쪽 자식 자리가 비어있는 경우
        node.left = newNode; // 비교 노드의 왼쪽 자식 자리에 "새 노드"를 넣는다.
      } else { // 비교 노드의 왼쪽 자식 자리가 비어있지 않으면
        this.insertNode(node.left, newNode); // 비교 노드의 왼쪽 자식 노드와 다시 비교한다.
      }
    } else {
      if (node.right === null) { // 만약 비교 노드의 오른쪽 자식이 비어있으면
        node.right = newNode; // 비교할 노드의 오른쪽 자식 자리에 "새 노드"가 추가된다. 
      } else { //  아니라면
        this.insertNode(node.right, newNode); // 비교 노드의 오른쪽 자식과 다시 비교한다. 
      }
    }
  }

 

삭제

삭제 메소드는 삽입 메소드보다 복잡하다. 많은 경우의 수를 고려한다.

  remove(val) { 
    this.root = removeNode(this.root, val); // 우선 루트에 removeNode(this.root, val)을 할당한다. 
  }

  removeNode(node, key) { 
    if (node === null) return null; // 노드가 비어있는 경우는 null을 반환한다. 
    if (key < node.key) { // 삭제할 값이 노드의 키값보다 작은 경우
      node.left = this.removeNode(node.left, key); // 노드 왼쪽에 removeNode(node.left, key)를 할당한다. 
      return node; // 왼쪽 자식이 새롭게 할당된 노드를 반환한다. 
    } else if (key > node.key) { // 삭제할 값이 노드 키 값보다 큰 경우,
      node.right = this.removeNode(node.right, key); // 노드의 오른쪽에 removeNode(node.right, key)를 할당한다. 
      return node;  // 오른쪽 자식이 새롭게 할당된 노드를 반환한다. 
    } else { // 삭제할 값과 노드의 키 값이 같은 경우
      if (node.left === null && node.right === null) { // 노드가 자식이 없는 경우
        node = null;
        return node;
      }
      if (node.left === null) { // 노드의 왼쪽 자식: 비어있음, 오른쪽 자식: 있음
        node = node.right;
        return node;
      } else if (node.right === null) { // 노드의 왼쪽 자식: 있음, 오른쪽 자식: 비어있음
        node = node.left;
        return node;
      }
      let aux = this.findMinNode(node.right); // 노드의 오른쪽 자식 노드에서 최솟값을 찾는다.
      node.key = aux.key; // 찾은 최솟값을 노드의 키 값으로 변경한다.
      node.right = this.removeNode(node.right, aux.key); // 오른쪽 자식에 removeNode(node.right, aux.key)를 할당한다. 
      return node; // 변경된 노드를 반환한다. 
    }
  }

  findMinNode(node) { // 받은 노드 인자를 주축으로 최솟값을 찾는 메소드이다. 
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node;
    }
    return null;
  }

 

검색

키 값으로 그 키 값을 가진 노드를 검색한다. 

  search(key){
    return this.searchNode(this.root.key); // 루트에서부터 검색한다.
  }

  searchNode(node, key) {
    if (node === null) return null;
    if (key < node.key) {
      return this.search(node.left, key);
    } else if (key > node.key) {
      return this.search(node.right, key);
    } else {
      return true; // 찾고자하는 노드를 찾아 true를 반환
    }
  }

 

최댓값 찾기

이진 검색 트리에서 최댓값은 트리의 맨 오른쪽 하단에 위치하게 된다. 따라서 최댓값을 구하려면 루트부터 맨 오른쪽으로 점진적으로 이동하면서 맨 오른쪽 하단 노드를 찾아내면 된다.

  max() {
    return MaxNode(root); // 루트부터 탐색
  }

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

 

최솟값 찾기

위의 최댓값 찾기와 마찬가지로 최솟값은 트리의 맨 왼쪽 하단에 위치한다. 따라서 코드는 다음과 같다.

  min() {
    return minNode(root); // 루트부터 탐색
  }

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

 

---

도움이 되셨다면 ♥︎ 눌러주세요