data-structure

양아름님께서 이 강좌를 듣고 너무나 정리를 잘 해주셔서 강의 교안을 거의 그대로 사용합니다.

시간복잡도

연결리스트

스택과 큐

트리와 이진트리 종류

⭐️이진탐색트리⭐️ : 재귀함수, 주석, 트리, 코드를 보면서 흐름을 파악해야한다.

---

5, 9, 4, 14, 19, 23, 7, 11, 8, 2, 16

1. 삽입에 대한 정리. insert()

1. 어떤 값을 넣으려고할 때, 일단 어디에 넣을지 모르겠다.
2. 그래서 왼쪽, 오른쪽에게 위임한다. ( 맡긴다, 처리하라고 한다. )
3. 근데 만약, 왼쪽 또는 오른쪽이 없다면 그 자리에 삽입한다.

5입장에서 11을 넣으려고 할 때, 9와 14에게 위임한 뒤, 11을 추가할 수 있다.
14에게 위임할 때, 왼쪽을 찾으려고 했더니 왼쪽이 없는 상황이다.
11을 넣고자 하는 상황에 왼쪽이 비어있다는 것을 인지한다.

1. 상위 값보다 넣으려는 값이 큰지, 작은지를 인지(조건문)하고 값을 넣는다.
   깔끔하고 명확하게 넣어줘야하기 때문에 추가적으로, 그 자리에 값이 있는지 없는지를 판단하는 조건을 추가한다.
2. 있다면 다시 재귀함수를 호출한다.
3. 없다면( 비어있다면 ), 그 자리에 값을 삽입한다.
   (이것이 재귀함수를 사용하는 것 이다.)

#insert(node, value) {
  if (node.value > value) {
    // 상위 값보다 넣으려고 하는 값이 작으면, 왼쪽
    if (node.left) {
      // 왼쪽에 값이 있으면, 왼쪽에 있는 값에게 처리를 넘김
      this.#insert(node.left, value);
    } else {
      // 만약 왼쪽이 비어있다면? 왼쪽에 추가
      node.left = new Node(value);
    }
  } else {
    // 상위 값보다 넣으려고 하는 값이 크면, 오른쪽
    if (node.right) {
      // 오른쪽에 값이 있으면, 오른쪽에 있는 값에게 처리를 넘김
      this.#insert(node.right, value);
    } else {
      // 만약 오른쪽이 비어있다면? 오른쪽에 추가
      node.right = new Node(value);
    }
  }
}

2. 검색(조회)에 대한 정리 search()

• 해당 값을 검사하고 찾아 처리해줘야하기 때문에, 모든 값을 return 해줘야한다.
• 수정은 검색(조회)를 활용한다.
• #insert()재귀함수와 동일한 조건의 틀을 가진다.
  • 찾는 값과 해당 node가 같은지(조건)와 결과를 return을 해줘야하는 부분만 다르다.

1. 11을 찾는다고 가정하고 코드의 흐름을 따라간다.
2. 또, 없는 값을 생각하고 어떻게 코드가 흐르는지도 파악한다. ( 어떻게 해서 null을 return 하는지 )

3. 삭제(제거)에 대한 정리 remove()

조건 : 제거하려는 값(value)과 트리 내부의 존재하는 값(node.value or root)이 동일한 경우

1. leaf일 경우
   결과 : null을 return한다.

2. 자식 Node가 1개일 경우
   2-1. 왼쪽 Node만 있을 경우
   결과 : (오른쪽 Node가 없을 경우) 왼쪽 Node를 return한다.
   2-2. 오른쪽 Node만 있을 경우
   결과 : (왼쪽 Node가 없을 경우) 오른쪽 Node를 return한다.
   

3. 자식 Node가 2개일 경우

• 만약, 어떠한 값을 제거한다면? ( root를 제거한다면 )
  3-1. 자신의 왼쪽 Node로부터 오른쪽 Node 중 가장 큰 수가 root자리로 오게된다.
  3-2. 그 후, root자리로 온 숫자의 자리로 원래 root였던 수가 들어간다.
  3-3. 그리고 제거된다.

• 풀이.

  1. 왼쪽 Node를 변수에 담아준다.
  2. 그 후, 최대한 오른쪽에 있는 Node를 찾아야한다. (node.left.right.right.right)
     2-1. 그렇기 위해선 while()문을 사용한다.
     2-2. 조건 : 오른쪽이 없을 때까지 계속 오른쪽으로 가야한다. ( 한글과 반대로 조건을 걸어준다. : 오른쪽에 Node가 있을 때까지 ) 2-3. 찾은 Node를 만든 왼쪽 Node변수에 담는다.
  3. 상위 Node와 찾은 오른쪽 가장 큰 수 Node를 바꿔준다.
     3-1. 중간역할을 위해 바뀔 값(node.value)을 변수(temp)에 담는다.
     3-2. 바뀔 값과 바꿀 값과 바꾼다. (node.value = 왼쪽 Node를 담은 변수의 value) 3-3. 왼쪽 Node를 담은 변수의 value값에 변수temp을 담는다.
  4. 바꿔줬다면, node.left에 담아 재귀함수를 호출한다.
  5. 마지막으로, 부모의 값을 유지해줘야하므로, node를 return한다.

조건 : 제거하려는 값(value)과 트리 내부의 존재하는 값(node.value or root)이 동일하지 않은 경우

• 지울 값을 찾지 못했을 경우, 좌우 Node에게 물어본다.
• 만약, 부모값이 삭제하려는 값보다 작을 때
  • 왼쪽 Node에 재귀함수를 호출한다.
• 만약, 부모값이 삭제하려는 값보다 클 때
  • 오른쪽 Node에 재귀함수를 호출한다.
• 마지막으로, 부모의 값을 유지하고 있어야해서 node를 return한다.

예외처리 : null을 return한다.

1. 찾으려는 숫자가 존재하지 않은 경우
2. leaf일 경우 ( 자식 Node가 0개일 경우 or 트리에 Node가 하나일 때 삭제하는 경우 )

return node가 왜 필요한가 ? 꼭 ! 정리한 이미지, 코드, 트리보고 흐름파악

힙

우선순위 큐 & 그래프 & 해시테이블

keypoint

1. 성능에 따라 시간복잡도가 변한다.
   Hash함수가 얼마나 잘 짜여졌는지(분배해 넣어주는 거)에 따라 각 메소드의 시간복잡도가 O(1), O(logn), O(n)이 될 수도 있다.
2. 해시함수를 짤 때는 해시함수만 생각하지않고, 데이터의 분포도 잘 파악해야한다.
   (데이터칸에 key와 value가 골고루 분포하도록.)
3. key값과 capa값을 나눠서 나머지 값을 구하는 법이 가장 간단한 hash함수 구현법이다.

트리순회 & BFS & DFS