[ DS ] 트리 & 이진트리

1. 트리(Tree)란?

- 이전에 다뤄왔던 것들과는 다르게 "비선형" 구조인 계층 구졸르 가진 자료구조입니다.
- 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타날 때 사용됩니다.

 

  

2. 용어정리(트리)

- 루트(Root) : 가장 상위에 있는 노드를 뜻합니다.

- 노드(Node) ; 트리 안에 들어있는 각 항목을 말합니다.

- 리프(Leaf) : 자식이 없는 가장 끝에 있는 노드를 의미합니다.

 

3. 트리의 특징

 

• left = index * 2
• right = index * 2 + 1
• parent = floor(index / 2)

 

 

 

 

4. 트리의 종류

 

- 이진트리

정점이 최대 2개의 자식을 가지는 트리를 의미한다.

 

- 완전 이진트리
리프 노드를 제외하고 모든 정점이 채워져있다.

 

- 포화 이진트리
완전 이진트리 + 마지막도 채워져있다면, 포화 이진 트리라고 한다.

 

- 이진트리의 특징

 

- N개의 정점을 가진 편향 트리가 될 수 있다.
- 정점이 N개인 포화 또는 완전 이진 트리의 높이는 로그 N이다.
- 높이가 h인 포화 이진 트리는 2^h -1 개의 정점을 가진다.

- 이진 탐색 트리와 다르게 좌/우에 따른 값의 차이는 없다.
 

 

 

 

5. 기본 트리 구현

 

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

  add(data) {
    this.children.push(new Node(data));
  }

  remove(data) {
    this.children = this.children.filter((child) =>
      child.data === data ? false : true
    );
  }
}

class Tree {
  constructor() {
    this.root = null;
  }
}

const t = new Tree();
t.root = new Node("a");
t.root.add("b");
t.root.add("c");
t.root.children[0].add("d");

  

  \ 

  

6. 트리의 순회 [ 전위, 중위, 후위 ]

 

class Tree {
  constructor(val) {
    this.val = val;
    this.leftNode = null;
    this.rightNode = null;
  }

  setLeftNode(node) {
    this.leftNode = node;
  }

  setRightNode(node) {
    this.rightNode = node;
  }

  // 중위순회 [ left -> root -> right]
  inOrderTree(node) {
    if (!node) {
      return;
    }

    return [
      ...this.inOrderTree(node.leftNode),
      node.val,
      ...this.inOrderTree(node.rightNode),
    ];
  }

  // 전위순회 [ root -> left -> right]
  preOrderTree(node) {
    if (!node) {
      return;
    }
    return [
      node.val,
      ...this.inOrderTree(node.leftNode),
      ...this.inOrderTree(node.rightNode),
    ];
  }

  // 후위순회 [ left -> right -> root ]
  postOrderTree(node) {
    if (!node) {
      return;
    }
    return [
      ...this.inOrderTree(node.leftNode),
      ...this.inOrderTree(node.rightNode),
      node.val,
    ];
  }
}

const root = new Tree("A");
let node = new Tree("B");
root.setLeftNode(node);

node = new Tree("C");
root.setRightNode(node);

node = new Tree("D");
root.leftNode.setLeftNode(node);

node = new Tree("E");
root.leftNode.setRightNode(node);

node = new Tree("F");
root.rightNode.setLeftNode(node);

node = new Tree("G");
root.rightNode.setRightNode(node);

// 중위 순회 left -> root -> right
root.inOrderTree(root);
console.log();

// 전위 순회 root -> left sub -> right sub
root.preOrderTree(root);
console.log();

// 후위 순회 왼쪽 -> 오른쪽 -> root
root.postOrderTree(root);

 

 

 

7. 이진 탐색 트리 구현

 

- 특징

 

1) 왼쪽 자식은 부모보다 작은 값을 가지고 있습니다.

2) 오른쪽 자식은 부모보다 큰 값을 가지고 있습니다.

 

 

- 부작용

 

작은 값 또는 큰 값만 들어오는 경우 한 쪽으로 치우친 트리가 나올수 있습니다.

 

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);

    if ( this.root === null ) {
      this.root = newNode;
      return;
    }

    let currentNode = this.root;

    while ( currentNode !== null ) {

      if ( currentNode.value > value ) {
        if ( currentNode.left === null ) {
          currentNode.left = newNode;
          break;
        }
        currentNode = currentNode.left;
      } else {
        if ( currentNode.right === null ) {
          currentNode.right = newNode;
          break;
        }
        currentNode = currentNode.right;
      }
    }

  }

  has(value) {
    let currentNode = this.root;

    while ( currentNode !== null ) {
      if ( currentNode.value === value ) {
        return true;
      }

      if ( currentNode.value < value ) {
        currentNode = currentNode.right;
      } else{
        currentNode = currentNode.left;
      }
    }
    return false;
  }
}