dev-waterparsley

01. m원 탐색 트리

🔸이진 탐색 트리(BS 트리; binary search tree)

• 트리에서 특정 데이터를 검색하고, 노드의 삽입/삭제 연산이 자주 발생하는 응용 문제에 가장 효과적인 이진 트리
• 왼쪽과 오른쪽이라는 방향성을 가지며 다루기가 매우 편리함
• 부모 노드를 중심으로[부모 보다 큰 데이터 노드]와 [부모 보다 작은 데이터 노드]로 구분됨
  • =왼쪽 서브 트리와 오른쪽 서브 트리의 중간 값은 이들의 부모 노
• 일반적으로 노드의 개수가 많아지면 트리의 높이가 커지게 됨
• BS 트리가 2원(2-way) 탐색 트리임

✅ m원 탐색 트리

• 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 => 같은 수의 노드를 갖는 이진트리보다 낮은 높이의 m원 트리
  • m원: 탐색 트리가 가질 수 있는 자식 노드들의 개수
• 이진 탐색 트리의 확장된 형태
• 탐색 트리의 제한을 따르되 2개 이상(m개 이하)자식을 가질 수 있음

✅ m원 탐색 트리의 제한 조건

▪️ m원 탐색 트리 - 3원 탐색 트리

• 3원 탐색 트리는 최대 3개의 자식 노드를 가질 수 있음 == (정렬된) 키 값은 최대 2개
• 키 값들과 서브트리들의 값의 관계 확인 (어떤 것은 작고, 어떤 것은 크고, 어떤 것은 사잇값인지를 확인)
  • 만약 키값이 60, 62이면 첫번째 자식 노드의 값은 60보다 작아야 하고, 두번째 자식 노드는 60과 62 사이의 값이어야 하고, 세번째 자식 노드는 62보다 큰 값이어야 함

🔸m원 탐색 트리 노드의 구조

🔸m원 탐색 트리의 탐색 연산

🔸m원 탐색 트리의 탐색

• 일반적으로 노드의 가지 개수가 많을수록(서브트리가 많을 수록), 최대 탐색 길이는 짧아짐(트리의 깊이가 얕으므로 더 빨리 찾을 수 있음)
• 예를 들어, 키가 255개인 경우 4원 트리로 구성하면 최대 경로 길이가 4가 됨

02. B 트리

✅ B 트리

• m원 탐색 트리는 서브트리의 균형에 대해서는 특별히 제한하지 않았음
• 각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상할 수 있음
• m원 탐색트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 사용함
• 차수  m인 B 트리의 탐색 경로 길이는 같은 개수의 키를 가지는 이상적인 m원 탐색 트리보다 길 수 있지만 키값을 삽입/삭제할 때 B트리를 유지하는 것이 더 쉬움

✅ B 트리의 조건

• 루트와 잎노드를 제외한 트리의 각 노드는 최소 [ m/2 ]개의 서브트리를 갖는다
  • 루트와 잎노드를 제외한 트리의 각 노드는 언제나 하나의 키값 혹은 두 개의 자식 노드를 가져야 함
• 트리의 루트는 최소한 2개의 서브트리를 갖는다
• 트리의 모든 잎노드는 같은 레벨에 있다

* [ ] 가우스 함수: 소수점을 포함하는 수를 그것보다 1큰 정수로 바꿈
예) [3/2] = [1.5] = 2

🔸B 트리에 키를 삽입하는 알고리즘

🔸B 트리의 노드 삽입

🔸B 트리에서 키를 삭제하는 알고리즘 - 잎노드에서 삭제

삭제할 키값을 포함한 노드를 찾는다

• 잎노드에서 삭제하는 경우
  1. 노드에서 키값을 삭제한다.
  2. 필요하면 재배열한다.

🔸B 트리에서 키를 삭제하는 알고리즘 - 내부노드에서 삭제

내부노드의 키값은 하위 노드에 대한 기준값(중간값)이기 때문에 삭제 시, 대체할 수 있는 적절한 값을 찾아야 한다.
보통 왼쪽 서브트리의 가장 큰 키값 또는 오른쪽 서브트리의 가장 작은 키값으로 대체할 수 있다. 이들은 모두 잎노드에 위치한다.

• 새로운 기준값(삭제된 자리에 올 키값)을 선택하여 해당 (잎)노드에서 삭제하고 그 값을 현재 키값을 삭제한 자리로 옮긴다. 즉 대체한 것이다.
• 기준값으로 대체하기 위해 키를 삭제한 잎노드가 정해진 개수의 키값을 갖지 않으면 트리를 재배열 한다.

▪️ 40 삭제(내부노드에서 삭제)

• 40을 삭제하면 중간값을 오른쪽 서브트리의 가장 앞에 있는 값을 올려줌
  • 키값이 부족한 노드의 오른쪽 형제가 존재하고 키 개수가 여유있다면 오른쪽 키값의 가장 앞에 있는 것을 부모 노드로 한다는 규정

03. B*, B+ 트리

✅ B* 트리의 정의

• 노드의 약 2/3 이상이 채워지는 B 트리 → 높이가 더 줄어듬(B트리는 1/2)
• 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김
• 삽입/삭제 시 발생하는 노드 분리를 줄이려고 고안됨

✅ B* 트리의 조건

차수가 m인 B* 트리는 다음 조건을 만족하는 B트리이다

① 공집합이거나 높이가 1 이상인 m원 탐색 트리이다
② 루트 노드는 2개 이상 2 ⌊ (2m-2)/3 ⌋ + 1개 이하의 자식노드를 갖는다
③ 내부노드는 최소한 ⌈ (2m-1)/3 ⌉개의 자식노드를 갖는다
④ 모든 잎노드는 동일한 레벨에 놓인다
⑤ 포인터가 k개인 잎이 아닌 노드는 k-1개의 키를 갖는다(루트노드 포함)

✅ B+ 트리의 정의

• 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만, 전체 데이터를 차례로 처리하기는 불편함
  • => 데이터 전체를 이진 탐색 트리로 구성해놓으면 검색은 빠르지만! 전체 데이터를 다 찾아서 제일 큰 값부터 차례로 출력할 때는 굉장히 복잡
  • 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가면서 처리해야 함
  • 스택을 써서 프로그래밍 하기 때문에 pop(), push() 연산이 추가되면 속도가 굉장히 느려짐
• B+ 트리는 인덱스된 순차 파일을 구성하는데 사용됨
• B 트리와 같이 각 노드의 키가 적어도 1/2이 채워져야 하는 점은 같음
• 잎노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다름
  • 잎노드의 마지막 포인터를 다음 키값을 갖는 노드를 가리킴
  • 순차 처리를 할 때는 이 포인터를 이용해서(키값을 비교하지 않고) 차례로 다음 데이터에 접근해서 처리
• 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터(파일 내용)에 대한 주소를 잎노드만이 가지고 있음
  • 직접 탐색은 잎노드에 도달해야 종료
  • 중간노드는 잎노드를 찾아가기 위한 징검다리 역할

01. 이진 탐색 트리

✅ 이진 탐색 트리(binary search tree)

• 특정 데이터를 검색하고, 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 이진 트리
• 탐색에 최적화된 이진 트리
• 키: 이진 트리 노드의 데이터(노드를 특정할 수 있는 값)

노드 Vᵢ의 키를 Kᵢ라 할 때 각 노드 Vᵢ가 다음을 만족하는 이진트리를 이진 탐색 트리(BS 트리)라고 함

1. Vᵢ의 왼쪽 서브트리에 있는 모든 노드의 키값은 Vᵢ의 키값보다 작다
2. Vᵢ의 오른쪽 서브트리에 있는 모든 노드의 키값은 Vᵢ의 키값보다 크다

같은 순서 데이터에 대해서 BS 트리를 다양하게 만들 수 있음

✅ BS 트리 순회

🔸BS 트리를 위한 노드 정의

🔸BS 트리의 중위 순회

🔸BS 트리의 노드 탐색

 BS 트리에서 키값이 K인 노드를 찾는 과정

① 트리가 비어있다면 탐색 실패, 비어있지 않다면 k와 현재 루트 노드의 키값 kᵢ를 비교한다.

② k = kᵢ 일 경우 탐색 성공, 이때 찾은 정점은 vᵢ 이다.

③ k < kᵢ 이면 vᵢ의 왼쪽 서브 트리를 탐색한다. 즉, vᵢ = vᵢ ,left로 바꾸고 ①로 간다.

④ k > kᵢ 이면 vᵢ의 오른쪽 서브 트리를 탐색한다. 즉, vᵢ = vᵢ ,right로 바꾸고 ①로 간다. 

🔸BS 트리의 노드 삽입 연산

BS 트리의 노드 삽입 연산

① 트리가 비어있다면 키 k를 가지는 노드를 삽입한다. 그렇지 않으면 k와 현재 루트 노드의 키 kᵢ를 비교한다.

② k = kᵢ 일 경우 멈춘다.

③ k < kᵢ 이면 vᵢ의 왼쪽 서브 트리에 삽입해야 하므로 vᵢ = vᵢ → left로 바꾸고 ①로 간다.

④ k > kᵢ 이면 vᵢ의 오른쪽 서브 트리에 삽입해야 하므로 vᵢ = vᵢ → right로 바꾸고 ①로 간다.

예)

🔸BS 트리의 노드 삭제

• 자식을 하나만 갖는 노드를 삭제하는 경우, [삭제한 노드를 가리키던 포인터]가 [그 노드의 null이 아닌 서브트리의 루트]를 가리키게 할당함
• 리프 노드의 경우 추가적인 작업 없이 바로 삭제 

• 두 개의 자식 노드를 가지는 노드는 삭제 시, 항상 특정 방향의 자식 노드를 올리는 방법으로 구현(항상 오른쪽(왼쪽) 자식 노드를 삭제 위치로 이동)
  • 특정 방향은 PM이 프로젝트 전에 미리 결정해둔대로 따름
• 구조를 가장 최소로 변화시키는 노드를 선택해서 삭제!

• 이진 트리 탐색을 사용하다 보니 탄생한 여러 트리들
  • splay 트리: 데이터 또는 키값을 찾을 때 예전에 찾았던 값을 또 찾는 경우가 생각보다 빈번하다는 입장에서 탐색 속도를 높이기 위해 만듬
  • BB 트리와 AVL 트리: 트리의 균형을 맞춤으로써 탐색의 속도를 높이려고 만듬

🔸이진 탐색 트리의 단점

• BS 트리의 성능은 트리의 구조와 특정 노드에 접근할 확률에 영향을 받음
• 트리의 성능이 구조에 영향을 받기 때문에 어떤 노드의 탐색/삽입/삭제를 위한 접근정보를 예측할 수 없는 상황에서는 최적의 BS 트리구조를 결정하기 어려움
• 휴리스틱 알고리즘(=경험적 알고리즘)을 사용하여 구축한 BS 트리의 성능이 최적에 가까움

🔸좋은 성능의 BS 트리를 구축하는 방법(휴리스틱)

1. 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다.
2. 트리가 균형(balance)이 되도록 유지한다. 즉, 각 노드에 대해 왼쪽과 오른쪽 서브트리가 가능한 같은 수의 노드를 갖게 한다.

02. Splay 트리

✅ Splay 트리

• 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 BS 트리
• Splay 연산: 최근에 접근한 노드 x를 (곧 사용할 것으로 예상하여) 루트에 위치시켜 트리를 재구성하는 연산
• Splay 트리: 가장 퇴근에 사용한 노드 x가 트리의 루트에 올 때까지 Splay 연산을 반복 적용하여 생성된 이진 트리

🔸Splay 트리의 연산

• 노드 x: 최근에 접근한 노드 
  노드 p: x의 부모 노드
• 노드 g: x의 조부모(부모의 부모) 노드

왼쪽 트리에 대해 7이 루트가 되도록 Splay연산을 적용

03. AVL 트리

✅ 변형 BS 트리 → AVL 트리

➡️ 노드의 삽입과 삭제가 일어날 때, 노드의 키값과 서브트리 키값 사이의 관계를 유지하면서 균형을 유지시키는 것이 쉽지 않음

🔸AVL 트리의 개념

• 제한 조건을 완화하여 트리가 (완전한) 균형이 아닌 것을 허용함
• 무너진 균형의 정도는 작아야 하고, 평균 탐색 길이도 완전 균형 트리의 탐색 길이와 크게 차이가 나지 않아야 함
• 거의 완전한 균형 트리의 한 형태로 높이가 균형 잡힌 높이 균형 트리(height balanced tree)
• 직접 탐색 성능이 매우 좋음

🔸AVL 트리의 조건

• 노드 vᵢ의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이가 남

04. BB 트리

✅ BB(bound-balanced)트리

• 거의 완전히(대략) 균형 잡힌 트리의 다른 종류로 무게가 균형 잡힌 트리
• 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

✅ 균형 트리

• AVL 또는 BB 트리에 대하여 각각 무게 또는 크기(높이) 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작음
• 십입이나 삭제 후에 트리를 완전히 균형합지게 유지하기 위해서는 O(n)의 노드를 옮겨야 하는 반면에 AVL 또는 BB트리는 O(log₂n)개의 노드를 옮기면 되는 것으로 알려져있음

➡️ 완벽한 균형이 아닌 적당히 허용된 균형(AVL, BB)이 여러모로 더 좋음

01. 선택 트리

✅ 합병 정렬

• 차례로 정렬된 k개의 데이터 리스트를 완전한 순서를 유지하는 하나의 데이터 리스트로 만드는 과정
• 일반적으로 데이터 리스트가 k개인 경우 k-1번 비교를 통해 데이터 리스트에서 가장 큰/작은 값을 결정함
  • 데이터가 많을 수록 엄청난 비교 횟수(오버헤드) => 선택 트리를 이용하여 비교 횟수를 줄일 수 있음

✅ 승자 트리

• 비교 횟수가 많은 합병 정렬 대신 선택 트리를 이용하여 구현
• 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리
• 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사
• 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
• 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨

=> 11 삭제 후, 24 추가하여 삭제되어 빈 부분을 비교하여 승자 트리 재구성

• 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교 단계부터는 비교 횟수가 감소됨
• 재구성 과정에서 빈 리스트가 생기면 큰 값을 넣어즘

✅ 패자 트리

• 승자 트리보다 구현하기 쉬운 자료구조를 구상하다가 탄생(효율은 비슷)
• 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진 트리라는 점은 승자 트리와 같지만! 패자 트리는 루트 노드 위에 최상위 0번 노드를 가짐
• 최상위 0번 노드에는 최종 승자를 저장함
• 트리의 각 내부 노드에는 승자가 아닌 패자를 저장(즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁)
• 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장

• 2레벨의 14는 4레벨의 14와 11을 비교해서 패자인 14를 넣은 것(2레벨 17은 4레벨의 12와 17을 비교)
• 1레벨의 12의 경우 2레벨의 내부 노드 값(패자)이 아닌 승자 값을 비교해서 패자인 12를 넣어줌(승자인 11은 0번 노드로)

• 재구성할 때는 자식과 자식간의 비교가 아니라 부모와 자식간의 비교!!

02. 숲

✅ 숲

• n(n>=0)개 이상의 분리된 트리 집합
• 트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있음 ↔ 숲을 연결하면 트리를 만들 수 있음

🔸숲의 이진트리 변환

🔸일반트리 → 이진트리(참고)

🔸숲 → 이진트리

• 숲을 하나의 통합된 자료구조에 넣어서 관리할 수 있음

03. 이진 트리 개수

🔸노드 개수에 따른 가능한 이진 트리

=> 순회 방법이 정해진 상태에서 출력되는 값들의 순서가 정해지면 이진트리는 제한된 개수만큼만 만들어짐

Q. 노드가 3개인 이진 트리에서 전위 순회 방문 순서가 1,2,3 이고 중위 순회 방문 순서가 1,3,2라면 위의 5개의 트리 중 어느 것일까?

A. 두번째 트리

▪️ 첫번째 트리 중위 순회 방문

▪️ 두번째 트리 중위 순회 방문

=> 어떤 이진 트리에 대한 [전위 순회와 중위 순회 방문 순서]가 주어지면 트리 구조는 유일하게(1개) 특정할 수 있음

01. 우선순위 큐

▪️ 큐: 먼저 들어간 데이터가 먼저 삭제되는 자료구조, 먼저 줄을 선 사람이 먼저 서비스를 받는 구조

▪️(힢을 이용한) 우선순위 큐: 대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조

🔸우선순위 큐의 배열 구현

• 데이터 삽입(Add_q()): 삽입 시, 우선순위를 고려하지 않고 순서대로 삽입

• 데이터 삭제(Delete_q()): 삭제 시, 우선순위 고려하여 삭제
  • Delete_q()에 의해 큐의 front 포인터에 있던 1이 삭제되면서 나머지 데이터 중에서 가장 작은 값인 2가 다음 삭제 위치(front가 가리키는 위치)로 이동됨

▪️ 우선순위 큐의 작동 방식

1. 삭제 명령이 실행되면 저장된 데이터 중에서 우선 순위가 가장 높은/낮은 데이터가 삭제됨
   • 10000건의 데이터가 있다고 가정했을 때 우선 순위대로 삭제 연산을 실행할 경우 9999번의 비교 필요 => 오버헤드 발생
   • 이를 해결하기 위해 자료구조 힢을 만듬 == 우선순위 큐를 구현하기 위해 힢을 고안
2. 나머지 데이터들은 어떤 순서로 저장되는 문제되지 않음

02. 힢

✅힢

• 피라미드 모양으로 쌓아 올린 더미이고 항상 맨 위에 있는 것을 먼저 꺼내는 구조
• 힢 추상 자료형
  • 힢 객체의 정의: 부모-자식 노드사이에서 부분적으로 정렬된 완전 이진트리로 부모노드는 자식노드보다 우선순위가 높음
  • 연산
    1. insert(element)::=힢에 데이터 삽입
    2. remove()::=힢(루트)에서 데이터 삭제
    3. peek()::=힢(루트)에서 데이터 읽어오기
    4. isEmpty()::=힢이 비었는지 확인
    5. size()::=힢에 저장한 데이터 개수 확인

🔸힢의 종류

① 최소 힢: 루트가 전체 노드 중에서 최소값을 가짐

• 트리의 모든 노드가 자식 노드보다 작은 값을 가짐(루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐)
• 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
• 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음(=형제 노드 사이에서 크기 제한 없음)

② 최대 힢: 루트가 전체 노드 중에 최대값을 가짐

• 트리의 모든 노드가 자식 노드보다 큰 값을 가짐(루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨)
• 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
• 탐색 트리처럼 왼쪽 노드와 오른족 노드 사이에 크기 제한도 없음

🔸힢이 아닌 경우

03. 힢 노드의 삭제 및 삽입

🔸힢 구현을 위한 자료구조

• 배열을 이용한 힢의 구현: 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
  • 연결 리스트보다 실행 속도 면에서 효율적임
  • 기억장소 측면에서도 장점을 가짐 → 포인터 부분에 대한 영역을 따로 관리하지 않으니까

🔸힢의 노드 삭제

== 우선순위 큐에서 front가 가리키는 데이터를 삭제 == 힢에서는 루트 노드

🔸힢의 노드 삽입

• 데이터 삽입 후 확인해야할 것
  • 완전 이진 트리가 맞는가? YES
  • 부모와 자식 간의 관계가 다른 노들과 같은가? NO => 데이터 교환

01. 스레드 트리의 정의

이진 트리의 노드를 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야 하는 번거로움이 발생함
*이진 트리의 노드 순회: 전위 순회, 중위 순회, 후위 순회

=> 이러한 방법을 사용하지 않고 놀고 있는 링크들을 사용하여 순회를 빠르게 하는 스레드 트리 탄생

✅ 스레드 트리

• '스레드'라는 포인터를 추가하여 트리 순회를 편리하게 한 것
• 스레드: 순회 방법에 따른 방문 순서를 유지하는 포인터

🔸세 가지 순회에 대한 스레드 트리

• 전위 순회(PLR)

• 중위 순회(LPR)

• 후위 순회(LRP)

02. 스레드 트리의 구현

🔸스레드의 구현 방법 - 포인터 필드의 추가

• 스레드를 저장하는 포인터를 추가하는 것

• 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함
  
  • 왼쪽 스레드: 해당 노드의 선행 노드를 가리킴
  • 오른쪽 스레드: 정해진 순회 순서에 따른 해당 노드의 후행노드를 가리킴
• 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회할 수 있지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 생김

▪️ 포인터 필드의 추가

▪️ 추가된 포인터 필드를 이용한 중위 순회 연산과정

① 순회할 트리에서 가장 먼저 접근해야하는 노드를 가리키는 포인터 firstin을 매개변수로 하는 함수의 이름을 inorder()로 지정

② 노드를 가리킬 수 있는 TNode 타입의 포인터 p를 생성하고 firstin에 담긴 노드를 가리키도록 함

③ 포인터 p가 가리키는 데이터(info)를 출력하고 p를 p의 오른쪽 스레드 값으로 바꾸어(p→right_thread) 중위 순회에 따른 다음 노드를 가리키도록 수정함

④ 이 과정을 p가 null이 될 때까지 반복함

스레드를 이용한 전위 순회

• 자기 자식을 가리키는 것과 스레드가 동일한 경우가 많기 때문에 전위 순회를 할 거면 굳이 스레드를 추가해서 사용할 필요가 없음을 깨달음

🔸스레드의 구현 방법 - 노드의 빈 포인터 필드를 활용

• 기존 이진 트리의 노드 구조를 그대로 사용하면서 노드에 있는 사용하지 않는 포인터를 활용하는 방법
• 추가 기억장소를 사용하지 않아도 되는 장점이 있음!

• 잎 노드의 빈 포인터 필드의 활용
  • 이진 트리의 포인터 갯수(노드의 개수를 n개라 가정): 왼쪽 서브트리를 가리키는 포인터 n개+오른쪽 서브트리를 가리키는 n개 = 2n개의 포인터
  • 루트 노드를 제외한 전체 노드의 진입 차수 1 = 루트 노드를 제외한 전체 노드 즉, 누군가로부터 가리켜져야 할 노드의 개수: n-1
  • null이 아닌 포인터 개수: n-1
  • null 포인터 개수: 2n - (n-1) = n+1 그래서 이 null 포인터를 스레드로 활용
• 각 노드에 대해 포인터가 스레드로 사용 중인지, 서브트리에 대한 포인터인지를 구분하기 위해 태그 필드가 필요함(삽입/삭제 연산에서 반드시 필요)

▪️스레드를 이용한 전위 순회

• 전위 순회: 각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정함
• 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 두고, null이면 전위 순회로 순회할 대 다음으로 순회되는 노드를 가리키도록 지정

▪️ 스레드를 이용한 중위 순회

• 어떤 노드 X에 대해 오른쪽 포인터가 null이면 이 포인터를 X 노드의 후행 노드를 가리키도록 하고, 왼쪽 포인터가 null이면 X 노드의 선행 노드를 가리키게 함

▪️ 스레드를 이용한 후위 순회

• 자식 노드를 가리키는 것과 스레드가 불일치할 경우 프로그램적인 처리가 추가 필요

01. 트리

• 트리
  • 검색의 편리함
  • 논리적 계층
  • 계급적 특성

02. 용어와 논리적 표현 방법

🔸트리의 구성

• 노드: 트리의 항목/트리에 저장되는 데이터의 묶음
• 부모노드-자식노드: 상하 계층구조가 있고 직접적으로 연결된 노드로서 상위 계층의 부모노드와 하위계층의 자식 노드
• 루트노드: 트리의 최상위 노드(부모가 없는 노드)
• 서브트리: 부모 노드를 삭제하면 생기는 트리들
• 리프노드: 트리의 맨 끝(바닥)에 있으면서 자신의 서브트리를 갖지 않는 노드

🔸진입/진출 차수

• 루트 노드: 진입차수 = 0
• 루트를 제외한 모든 노드의 진입 차수: 1
• 리프 노드: 진출 차수 = 0

🔸트리의 레벨

• 노드의 레벨: 루트로부터 그 노드까지 이어진 선(경로)의 길이

🔸트리의 높이

• 루트로부터 가장 멀리 있는 노드까지 이어진 선(경로)의 길이에 1을 더한 값

03. 이진 트리

✅ 이진 트리

• 모든 노드의 차수가 2이하인 트리
• 수학적으로 이진트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임
• 모든 노드가 2개 이하의 자식노드를 가지므로 일반성을 잃지 않고 '오른쪽', '왼쪽'이라는 방향 개념을 부여할 수도 있음
  • 오른쪽 노드, 왼쪽 노드의 개념적 접근도 있음

🔸포화 이진 트리

• 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리

🔸완전 이진 트리

• 높이가 k인 이진 트리가 '0 레벨'부터 'k-2 레벨'까지 다 채우고, 마지막 'k-1 레벨'에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진 트리

04. 이진 트리의 구현

🔸배열을 이용한 이진 트리의 구현

• 트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적임

• 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해짐

=> 완전 이진트리를 기본으로 만들어지는 자료 구조에서는 유용하지만 일반적으로 배열을 이용해서 이진트리를 구현하지 않음

🔸포인터를 이용한 이진 트리의 구현

05. 이진 트리 연산

▪️ 이진 트리의 순회

• 이진 트리의 각 노드를 빠짐없이 그리고 중복없이 한 번씩 방문하는 것
• 순회 단위
  1. 루트 방문(Print)
  2. 왼쪽 서브트리 순회(L)
  3. 오른쪽 서브트리 순회(R)
• 종류 
  1. 전위 순회(PLR)
  2. 중위 순회(LPR)
  3. 후위 순회(LRP)

🔸전위 순회

• 루트노드(P) - 왼쪽 자식노드(L) - 오른쪽 자식노드(R)

① 루트를 방문

② 왼쪽 서브트리를 전위 순회로 순회

③ 오른쪽 서브트리를 전위 순회로 순회

🔸중위 순회

• 왼쪽 자식노드(L) - 루트노드(P) - 오른쪽 자식노드(R)

① 왼쪽 서브트리를 중위 순회로 순회

② 루트를 방문

③ 오른쪽 서브트리를 중위 순회로 순회

🔸후위 순회

• 왼쪽 자식노드(L) - 오른쪽 자식노드(R) - 루트노드(P)

① 왼쪽 서브트리를 후위 순회로 순회

② 오른쪽 서브트리를 후위 순회로 순회

③ 루트를 방문

🔸이진 트리의 순회 알고리즘

▪️ 이진트리의 생성과 삽입

• 일반적인 이진 트리를 생성할 때 연결 리스트 연산을 사용함
• 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하려면 연결 리스트의 삽입 연산을 사용함

▪️ 이진트리의 삭제

• 노드를 삭제할 때, 삭제하려는 노드가 리프노드인 경우는 해당 노드를 가리키는 포인터를 null로 지정하면 됨
• 리프노드가 아닌 경우에는 삭제하려는 노드의 자식노드에 대한 처리를 추가로 해주어야 함

▪️ 이진 트리의 노드 개수 세는 연산

▪️ 이진 트리의 리프 노드 개수 세는 연산

06. 일반 트리를 이진 트리로 변환

🔸일반 트리를 이진 트리로 변환하는 방법

=> 메모리 낭비를 막기 위해!

• 각 노드에 대하여 가장 왼쪽 링크만 남기고 모두 제거
• 루트 노드는 반드시 왼쪽 자식노드 하나만 갖도록 함 
• 형제 노드의 경우 오른쪽으로 연결

01. 연결 리스트의 변형

✅ 연결 리스트의 종류

단순 연결 리스트

• 하나의 링크만 있고 각각의  노드의 링크는 후행 노드만을 가리키는 구조
• 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점 발생

이중 연결 리스트

• 특정 노드는 선행 노드를 가리키는 링크와 후행 노드를 가리키는 링크를 가짐
• 특정 노드에서 선행 노드와 후행 노드에 간단한 프로그램 코드를 통해 접근할 수 있음

원형 연결 리스트

• 연결 리스트를 살펴보면 가장 마지막 노드의 링크 필드는 언제나 null 값임. 그래서 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해 원형 연결 리스트가 제안됨

※ null

== 아무것도 없다

!= 0

 

예) 정수형 변수 i를 선언하면 0이 아니라 null값이 들어감

02. 원형 연결 리스트

• 연결리스트의 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트가 제안됨

🔸정의 및 생성

🔸원형 연결 리스트의 노드 삽입

▪️ 삽입 연산

NewNode → data = x; //100
NewNode에는 주소값(7000)이 담겨있고 NewNode → data = x; 를 할당할 경우 해당 주소값으로 가서 data라는 변수에 x값을 넣어줌

함수 return 타입이 void 즉, 아무것도 반환하지 않아도 해당 함수에서 실행한 연산들은 고스란히 남아있음
왜냐면 매개변수로 포인터 변수를 공유했기 때문 => 참조 호출(call by reference)

03. 이중 연결 리스트

▪️ 단순 연결 리스트의 단점
 어떤 노드를 찾을 경우, 그 특정 노드의 후행 노드는 쉽게 찾을 수 있지만, 선행 노드를 찾으려면 복잡함

🔸이중 연결 리스트 노드 구조

• 양쪽 방향으로 순회할 수 있도록 링크 필드가 두개 필요함 → 시작점(head)도 두개의 링크 필요(Fhead, Lhead)
• 이중 연결 리스트의 노드 구조: 두 개의 링크 필드와 한 개의 데이터 필드

🔸이중 연결 리스트의 정의 및 생성

🔸이중 연결 리스트의 노드 삽입

01. 리스트의 개념

🔸리스트와 배열 개념 비교

• 배열: 논리적인 순서와 물리적인 순서가 같음
• 연결 리스트: 논리적인 순서와 물리적인 순서가 같지 않음
  • 개발자가 머릿 속에 있는 데이터 순서와 메모리에 적재된 순서는 다르지만 실제로 데이터를 접근할 때는 순서대로 접근

✅ 리스트

• 어떤 정의에 의해서 결정된 논리적인 순서의 나열

• 리스트의 순서: 데이터가 저장되는 물리적인 위치와 상관없이 원소들간의 논리적인 순서만 유지함
  • ↔️ 배열의 순서: 배열은 인덱스로 표현되는 순서가 배열 원소의 메모리 공간(주기억 장치, DDR)에서의 물리적인 위치를 의미함

• 리스트의 구현 방법
  1. 포인터를 이용한 리스트의 구현 방법: 원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법 => 연결리스트
  2. 배열을 이용한 리스트의 구현 방법

02. 배열을 이용한 리스트의 구현

예) 배열을 이용한 리스트의 구현과 원소 삽입/삭제

구현해야 할 리스트를 3.1운동(1919), 대한 독립(1945), 6.25(1950), 서울 올림픽(1988)의 순서라고 정의한다면

▪️ 리스트 구현

리스트 = {1919, 1945, 1950, 1988}

▪️ 리스트 원소 삽입

리스트 = {1919, 1945, 1950, 1988} 에 1936년에 '애국가 작곡'을 삽입한다면?

• 배열의 확장
  • 초기 배열 선언에서 크기를 충분히 크게 한다면 배열의 추가 확장은 피할 수도 있지만! 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩 뒤로 밀어야하는 상황이 발생함

▪️ 리스트 원소 삭제

리스트 = {1919, 1936, 1945, 1950, 1988} 에 1936년에 '애국가 작곡'을 삭제한다면?

• 모든 원소를 앞으로 당겨야함

🔸배열을 이용한 리스트의 원소 삽입/삭제

• 배열로 구현된 리스트는 원소의 순서가 연속적인 물리적 주소에 저장됨
  • → 원소를 삽입/삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야 됨
  • → 리스트 원소값의 이동은 원소 수가 많을수록 프로그램 수행 시간을 증가시킴

🔸 배열을 이용한 리스트의 원소 삽입/삭제 시 발생하는 문제점

• 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴
• 배열을 이용한 리스트의 구현은 실제 IT서비스 환경에서는 자주 사용되지 않고 있음
• 자료의 삽입과 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발

03. 포인터를 이용한 리스트의 구현

✅ 노드의 구조

• 노드(node): 리스트의 데이터 요소(원소, 값) + 다음 원소를 지시하는 포인터(주소, 링크(link))

🔸연결 리스트의 논리적 순서와 실제 메모리 표현

04. 포인터 변수

🔸노드 생성

• 정수값(data)과 링크(link)로 구성된 노드의 생성

🔸포인터의 할당과 반환 예

• malloc: 프로그램 실행 중에 내가 필요할 때마다 메모리를 받는 것. 배열 할당과 다름

05. 연결 리스트에서 노드의 삽입과 삭제

🔸 연결 리스트에서 노드의 삭제

• 연결 리스트의 초기 모습

• 연결 리스트의 노드 삭제

• 연결 리스트의 삭제 결과

▪️ 리스트의 원소 삭제 연산 단계

1. 삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다
2. 삭제할 노드를 메모리에 반환한다

🔸연결 리스트에서 노드의 삽입

• 연결 리스트의 초기 모습

• 연결 리스트의 삽입 노드

• 연결 리스트의 삽입 결과

▪️ 연결 리스트의 원소 삽입 연산 단계

1. 메모리 공간을 할당 받고 삽입할 내용을 저장하여 삽입할 x노드를 생성한다
2. x노드의 링크 부분이 후행 노드가 될 j노드를 가리키게 한다
3. 삽입될 x노드의 선행 노드가 될 i노드의 링크 필드가 x노드를 가리키게 한다

01. 큐의 개념 및 추상 자료형

✅ 큐

• 일상 생활에서의 큐 
  • 택시를 타기 위해 서 있는 행렬
  • 병원의 접수대
  • 은행의 예금 인출기
  • 백화점의 계산대 위에 놓인 상품들
• 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄(First-in-First-out) → 운영체제에서 사용하는 방법
• 한쪽에서는 삽입 연산만 발생 가능하고, 다른 한쪽에서는 삭제 연산만 발생 가능한 양쪽이 모두 터진 관

📌삽입/삭제가 다른 곳에서 발생한다는 것을 프로그래밍에서는 어떻게 표현할까?

A.
데이터에 접근하는 변수를 다르게 사용
예) 큐의 front(삭제)와 rear(삽입)

( ↔ 삽입/삭제가 같은 곳에서 발생 == 데이터에 접근할 때 같은 변수를 사용)

• 한쪽에서는 삽입 연산: 서비스를 받기 위한 기다림
• 다른 한쪽에서는 삭제 연산: 서비스를 받는 중

🔸큐의 추상 자료형

 ▪️ 큐의 삽입(Add_q) 연산

 ▪️ 큐의 삭제(Delete_q) 연산

▪️ 빈 큐 검사(IsEmpty_q) 연산

• 데이터 삭제 전에 확인!

▪️ 큐의 만원 검사(IsFull_q) 연산

• 데이터 삽입 전에 확인!

🔸Add/Delete 연산의 실행

① Create_q(4);
② Add_q(queue, 'A');
③ Add_q(queue, 'B');
④ Add_q(queue, 'C');
⑤ Delete_q(queue);
⑥ Delete_q(queue);
⑦ Delete_q(queue);
⑧ Add_q(queue, 'D');

02. 큐의 응용

✅ CPU의 관리 방법

• FCFS(First-Come First-Served) 스케줄링(FIFO 스케줄링) 기법: 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당 받도록 해주는 기법

• RR(Roud Robin) 스케줄링 기법: 대화형 시스템에 사용되는 스케줄링 방식

03. 배열을 이용한 큐의 구현

🔸큐의 구현

▪️ 큐의 생성

• 변수 rear의 초기값은 큐의 공백 상태를 나타내는 -1로 시작함

▪️ 큐의 삽입

• 삽입 연산이 발생하면 rear 변수만 오른쪽으로 이동하고, 삭제 연산이 발생하면 front 변수만 오른쪽으로 이동함

▪️ 큐의 삭제

• 삭제 연산의 수행 결과로 삭제된 원소를 Delete_q 연산자의 호출 프로그램에게 반환해 줌

04. 원형 큐

🔸큐의 만원 상태

✅ 원형 큐

• 배열의 문제점(일반 큐의 메모리 낭비 문제점)을 해결하기 위해 제안 됨
• 파이프의 입구와 출구 부분을 연결 시킨 형태

📌 추상 자료형 연산에서는 front와 rear 값이 같으면 해당 큐는 empty 상태라고 판단하는게 일반적이고 기본적
구현자 입장에서 메모리를 효율적으로 쓰기 위해 제안한 원형 큐의 경우, 해당 큐가 다 찬 건지 빈 것인지 구분이 안 되기 때문에 추가 구현이 필요

➡️ 원형 큐는 메모리 영역을 더 효율적으로 쓸 수 있지만, 만원 상태와 빈 상태를 구분해주는 프로그램 기법이 조금 더 필요함

01. 스택의 개념과 추상 자료형

✅ 스택

• 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형
  • 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현(First In Last Out, LIFO)
• 0개 이상의 원소를 갖는 유한 순서 리스트
• push(add)와 pop(delete)연산이 한곳에서 발생되는 자료구조

🔸스택의 추상자료형

• 스택 추상 자료형: 세 개의 연산(create, push, pop)만 해당 객체에 접근 가능하도록 제한하는 것
• 추상 자료형은 운영체제/컴파일러 개발자들이 만드는 것으로 소프트웨어/애플리케이션 개발자들이 다른 연산으로는 객체(데이터)에 접근할 수 없도록 막고, 이를 이용해서 OS나 프로그래밍언어가 효율적으로 작동하게 만듬

▪️ CreateS 연산

Stack CreateS(maxStackSize) ::= 스택의 크키가 maxStackSize인 빈 스택을 생성하고 반환;

▪️ Push 연산

Element Push(stack, item) ::= if( isFull(stack) ) then{ 'stackFull' 출력; }else{ 스택의 가장 위에 item을 삽입하고 스택 반환; }

▪️ Pop 연산

Element Pop(stack) ::= if( IsEmpty(stack) ) then{ 'stackEmpty' 출력; }else{ 스택의 가장 위에 있는 원소를 삭제하고 반환; }

🔸Pop/Push 연산 실행

• top: 현재 스택에서 제일 위에 있는 값만을 가리키는 변수로 top을 이용해서만 스택에 접근할 수 있음

02. 스택의 응용과 구현

🔸스택의 다양한 응용

• 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
• 서브루틴 호출 관리를 위한 스택
  • 예) main 함수에서 A 함수를 호출하고 A함수에서 B함수를 호출할 경우, B함수 실행 종료 후 돌아가야할 위치, A함수 실행 종료 후 돌아가야할 위치를 저장하는데 스택이 사용됨
• 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
• 인터럽트의 처리와 이후 리턴할 명령 수행 지점을 저장하기 위한 스택
• 컴파일러, 순환 호출(재귀호출) 관리

🔸스택의 삭제 연산

int a = 5;
int b = a--; //b = 5, a = 4

int a = 5;
int b = --a; //b = 4, a = 4

• top--에서 사용된 '--' 연산자의 위치에 따라 연산의 적용 순서가 달라질 수 있음

🔸스택의 구현

▪️ 스택의 생성

#define STACK_SIZE 10
typedef int element;
element stack[STACK_SIZE];
int top = -1;

▪️ 스택의 삭제 연산

element pop(){
	if(top == -1){
            printf("Stack is Empty!\n")
            return 0;
    }else{
    	return stack[top--]; //리턴 후, 삭제
    }
}

▪️ 스택의 삽입 연산

void push(element item){ //스택의 삽입 연산, item=400
	if(top >= STACK_SIZE-1){
            printf("Stack is Full!\n");
            return;
    }eles{
    	stack[++top] = item;
    }
}

03. 사칙 연산식의 전위/후위/중위 표현

📌 컴퓨터가 계산을 하기 위해 혹은 계산을 더 빠르게 하기 위해서 수식을 가지고 있어야 하는데 이는 사람이 사용하는 수식 표현 방법과 다름

🔸수식의 계산

• 연산자의 계산순서를 생각해야 함
• A+B*C+D ▶ ((A+(B*C))+D)

🔸수식의 표기 방법

• 중위 표기법(infix notation)
  • 연산자를 피연산자 사이에 표기하는 방법
  • A+B

• 전위 표기법(prefix notation)
  • 연산자를 피연산자 앞에 표기하는 방법
  • +AB

• 후위 표기법(postfix notation)
  •  연산자를 피연산자 뒤에 표기하는 방법
  • AB+

🔸중위 표기식의 후위 표기식 변환 방법

1. 먼저 중위 표기식을 연산자의 우선순위를 고려하여(피연산자, 연산자, 피연산자)의 형태로 괄호로 묶어줌
2. 각 계산 뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동시킴
3. 각 계산 뭉치를 하나의 피연산자로 고려하여 위의 작업을 반복함
4. 괄호를 모두 제거함

예)