[TIL] Day77 #Tree #Graph #BST

2022.08.16(Tues)

[TIL] Day77
[SEB FE] Day76

☑️ Tree

그래프의 여러 구조 중 단뱡향 그래프 구조
👉 Cycle이 없는 하나의 연결 그래프 (Connected Graph)

• 데이터에 1개 경로와 한 방향으로만 연결된 계층적 자료구조
• 하나의 데이터 아래에 여러 개의 데이터가 존재 가능한 비선형 구조
  (순차적 나열 선형 구조 ❌)
• 트리 구조는 계층적으로 표현, 아래로만 뻗어나가기 때문에 Cycle 없음

➕ Cycle: 한 정점에서 출발하여 다시 출발했던 정점으로 돌아갈 때, 다른 정점과 간선을 거쳐서 돌아가는 것
➕ 자기 루프(self loof): 다른 정점을 거치지 않고 정점에서 진출하는 간선이 다시 자신에게 진입하는 경우

🔷 Tree 구조 & 특징

• Root라는 하나의 꼭짓점 데이터를 시작으로 여러 데이터를 간선(edge)으로 연결
• 2개의 Node가 상하 계층으로 연결되면 부모/자식 관계
• Leaf Node: 자식이 없는 노드
  
  

• 깊이(depth): 루트로부터 하위 계층의 특정 노드까지의 깊이(depth) 표현 ⬇️
  • 루트 노드 깊이는 0
• 레벨(Level): 트리 구조에서 같은 깊이를 가지고 있는 노드들
  • 형제 노드(Sibling Node): 같은 레벨에 나란히 있는 노드
• 높이(Height): 리프 노드를 기준으로 루트까지의 높이(Height) 표현 ⬆️
  • 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로!
  • 각 리프 노드 높이를 0으로!
• Sub tree: root에서 뻗어 나오는 큰 트리 내부의 트리 구조를 갖춘 작은 트리
  
  

• Node: 트리 구조를 이루는 모든 개별 데이터
• Root: 트리 구조 시작점이 되는 노드
• Parent node: 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• Child node: 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• Leaf: 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
  
  

// Class로 Tree 구현 예제

class Tree {
  // constructor로 만든 객체 = 트리 node!
  constructor(value) {
    this.value = value;
    this.children = []; // 노드의 자식 노드들을 담을 수 있도록
  }

  // [트리 삽입 메서드 생성]
  insertNode(value) {
    const childNode = new Tree(value); // tree의 자식 노드 생성
    this.children.push(childNode);
  }

  // [tree에서 value값 탐색]
  // 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드
  contains(value) {
    // 현재 노드의 value 값과 찾는 값이 일치한다면 (값이 포함되어 있다면)
    if (this.value === value) {
      return true;
    }

    // 값을 찾을 때까지 자식 노드 순회 => 노드의 children 배열 탐색
    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }

    // 전부 탐색했음에도 값을 찾지 못하면 false 반환
    return false;
  }
}

// ---------------------------------------------------

// Tree 사용 예제
const rootNode = new Tree(null);

for (let i = 0; i <= 4; i++) {
  if (rootNode.children[i]) {
    rootNode.children[i].insertNode(i);
  }
  rootNode.insertNode(i);
}
rootNode; // {value: null, children: Array(5)}
rootNode.contains(5); // false
rootNode.contains(1); // true

---

☑️ Binary Search Tree (BST)

➰ 이진 트리(Binary tree): 자식 노드가 최대 2개인 노드들로 구성된 트리
➰ BST: 이진 탐색(binary search) & 연결 리스트(linked list)를 결합한 이진트리

• 정이진 트리(Full binary tree): 각 노드가 0개 / 2개 자식 노드 갖음
• 포화 이진 트리(Perfect binary tree): 정 이진 트리 & 완전 이진 트리인 경우
  • 모든 리프 노드 레벨 동일하고, 모든 레벨이 가득 채워져 있는 트리
• 완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함

🔷 BST 특징

• 각 노드에 중복되지 않는 Key 존재
• 루트노드의 왼쪽 서브 트리는 해당 노드 키보다 작은 키를 갖는 노드로 구성
• 루드노드의 오른쪽 서브 트리는 해당 노드 키보다 큰 키를 갖는 노드로 구성
• 좌우 서브트리도 모두 이진 탐색 트리여야 함
  👉 모든 왼쪽 자식 값이 루트나 부모보다 작고, 모든 오른쪽 자식 값이 루트나 부모보다 큰 값을 가짐
• 기존 이진 트리보다 탐색 빠름
  • 트리 높이 h → O(h) 복잡도

1. 루트 노드 키와 찾고자 하는 값 비교 (만약 찾고자 하는 값이면 탐색 종료)
2. 찾고자 하는 값이 루트 노드 키보다 작다면 왼쪽 서브 트리로 탐색 진행
3. 찾고자 하는 값이 루트 노드 키보다 크다면 오른쪽 서브 트리로 탐색 진행

    ✋ 트리 안에 찾고자 하는 값이 없더라도 최대 h번 연산/탐색 진행

// Class로 이진탐색트리(BST) 구현 예제

class BinarySearchTree {
  // constructor로 만든 객체는 이진 탐색 트리의 Node가 됨
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  // [이진 탐색 트리 삽입 메서드]
  // tree에 value 추가
  insert(value) {
    // 입력값이 현재 노드 값보다 작다면, 왼쪽 노드에서 진행
    if (value < this.value) {
      // 왼쪽이 비어있는지 확인 후 값 삽입 (즉, this.left에 아무것도 없을 경우, 새로운 자식 노드 추가)
      if (this.left === null) {
        this.left = new BinarySearchTree(value);
      }
      // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀 사용
      else {
        this.left.insert(value);
      }
    }

    // 입력값이 현재 노드보다 크다면, 오른쪽 노드에서 진행
    else if (value > this.value) {
      // this.right에 아무것도 없을 경우, 새로운 자식 노드 추가
      if (this.right === null) {
        this.right = new BinarySearchTree(value);
      }
      // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀 사용
      else {
        this.right.insert(value);
      }
    } else {
      // 이미 value값을 포함하고 있으므로 아무것도 하지 않음
    }
  }

  // [이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인 메서드]
  // tree의 value값 탐색
  contains(value) {
    // 찾는 value값이 노드의 value와 일치한다면, true 리턴
    if (value === this.value) {
      return true;
    }
    // 찾는 value 값이 현재 노드의 value보다 작다면, 왼쪽에서 contains 재귀 진행
    if (value < this.value) {
      return !!(this.left && this.left.contains(value));
    }
    // 찾는 value 값이 현재 노드의 value보다 크다면, 오른쪽에서 contains 재귀 진행
    if (value > this.value) {
      return !!(this.right && this.right.contains(value));
    }
  }

  // --------------------------------------------

  // [Tree 전위 순회]
  preorder(callback) {
    callback(this.value);

    if (this.left) {
      this.left.preorder(callback);
    }
    if (this.right) {
      this.right.preorder(callback);
    }
  }

  // [Tree 중위 순회]
  inorder(callback) {
    if (this.left) {
      this.left.inorder(callback);
    }
    callback(this.value);
    if (this.right) {
      this.right.inorder(callback);
    }
  }

  // [Tree 후위 순회]
  postorder(callback) {
    if (this.left) {
      this.left.postorder(callback);
    }
    if (this.right) {
      this.right.postorder(callback);
    }
    callback(this.value);
  }
}

---

☑️ Tree Traversal

• 트리 순회: 특정 목적을 위해 트리의 모든 노드를 1번씩 방문하는 것

✋ 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽 → 오른쪽

🔹 전위 순회 (preorder traverse)

• 루트에서 시작해 왼쪽 노드들을 순차적으로 둘러본 뒤, 왼쪽 노드 탐색 → 오른쪽 노드 탐색
  👉 부모 노드가 제일 먼저 방문되는 순회 방식
• 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용

🔹 중위 순회 (inorder traverse)

• 루트를 가운데에 두고 순회함.
• 루트 기준으로 왼쪽 노드 순회가 끝나면 루트를 거쳐 오른쪽 노드로 이동하여 마저 탐색
  👉 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식
• 오름차순으로 이진 탐색 트리 값을 가져올 때 사용

🔹 후위 순회 (postorder traverse)

• 루트 가장 마지막에 순회
• 제일 왼쪽 끝 노드부터 루트를 거치지 않고 오른쪽을 순회한 뒤, 제일 마지막에 루트 방문
• 트리 삭제시 사용 (why? 자식 노드가 먼저 삭제되어야 상위 노드 삭제가 가능하므로)
  
  

---

☑️ Graph

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선 존재
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐

• 정점(vertex): 하나의 점
• 간선(edge): 하나의 선

🔹 Graph 표현 방식

🔸 인접 리스트

: 각 정점이 어떤 정점과 인접하는지 리스트 형태로 표현

• 각 정점마다 하나의 리스트를 가지고 있고, 이 리스트는 자신과 인접한 정점을 담고 있음
• 메모리를 효율적으로 사용하고 싶을 때 사용
  • ↔️ 인접 행렬은 연결 가능한 모든 경우의 수를 저장하므로 메모리 많이 차지

🔸 인접 행렬

: 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로, 2차원 배열 형태로 나타냄

• 두 정점은 인접하다: 두 정점을 바로 이어주는 간선 존재
• 두 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시

• 두 정점 사이의 관계 유무 확인시 용이
• 가장 빠른 경로를 찾고자 할 때 주로 사용

// Class로 인접행렬 구현 예제

// Directed graph(방향 그래프)
// unweighted(비가중치)
// adjacency matrix(인접 행렬)
// 기존 배열의 인덱스를 정점으로 사용(ex. 0, 1, 2, ... --> 정점)

class GraphWithAdjacencyMatrix {
  // constructor 구현
  constructor() {
    this.matrix = [];
  }

  // [vertex(정점) 추가]
  addVertex() {
    const currentLength = this.matrix.length;
    for (let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0);
    }
    this.matrix.push(new Array(currentLength + 1).fill(0));
  }

  // [vertex(정점) 탐색]
  contains(vertex) {
    // this.matrix에 vertex 존재 -> true, 아니면 -> false 리턴
    return !!this.matrix[vertex];
  }

  // [1. vertex(정점)과 edge(간선) 추가]
  addEdge(from, to) {
    const currentLength = this.matrix.length - 1;

    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }

    // 간선을 추가할 수 없는 상황에선 추가 X
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면 return
    if (from > currentLength || to > currentLength || from < 0 || to < 0) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }

    // this.matrix[from][to]의 값을 1로 바꿔줌 -> edge으로 연결이 되어 있음 표시
    this.matrix[from][to] = 1;
  }

  // 2. from vertex와 to vertex 사이에 edge를 가지고 있는지 판단
  hasEdge(from, to) {
    return !!this.matrix[from][to];
  }

  // [3. edge(간선) 제거]
  // from vertex와 to vertex 사이에 관련이 없다면, edge 제거
  removeEdge(from, to) {
    const currentLength = this.matrix.length - 1;

    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }

    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면 return
    if (from > currentLength || to > currentLength || from < 0 || to < 0) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }

    // 간선 삭제
    // this.matrix[from][to]의 값을 0으로 바꿔줌 -> 관련 없음을 표시
    this.matrix[from][to] = 0;
  }
}

• 연결 그래프: 정점들이 간선으로 전부 연결되어 있는 그래프
• 비연결 그래프: 정점이 하나라도 연결되어 있지 않은 그래프
• 비가중치 그래프: 추가적인 정보를 파악할 수 없는 그래프
• 가중치 그래프: 간선에 연결 강도를 표현한 그래프
  
  

---

☑️ BFS & DFS

🔷 BFS(Breadth-First Search)

: 너비 우선 탐색으로, 주로 두 정점 사이 최단 경로를 찾을 때 사용
✋ 출발하는 정점과 가장 가까운 정점부터 탐색하므로 경로 탐색시 가장 먼저 찾아지는 해답이 곧 최단거리!

🔷 DFS(Depth-First Search)

: 깊이를 우선적으로 탐색하는 방법으로, 한 정점에서 다음 경로로 넘어가기 전에 해당 경로를 완벽히 탐색할 때 사용
✋ BFS보단 탐색 시간이 더 걸릴지라도 모든 노드를 완전히 탐색 가능