알고리즘 )2장 문풀

 

#14~

 

 

---

 

리프에는 항상 가득차야하나,ㄴㄴ

뭐가 같아야한다고 햇더라,높이 

어떤 리프는 2노드, 어떤 리프는 3노드가 될수있나<ㅇㅇㅇ(대신 3노드의 자식은 3개여야함 ) 

 

 

높이별로 경우 나누고 

 

높이 2인경우는 이해가는데 -1가지 

높이 3인 경우는 아 마지막 남은 하나가 무조건 리프 노드에만 추가될수있어서 이런가, 리프가 아닌 노드에 추가되면, 자식의 갯수가 3개가 되어야하니깐, -4가지 

그리고 구조가 같더라도 다른노드면 다른 트리인데, *8!해야하나 ㄴㄴㄴ

 2-3 트리가 **"검색 트리(Search Tree)"**이기 때문입니다.

• 검색 트리의 규칙: 왼쪽 자식 < 부모 < 오른쪽 자식 순서로 데이터가 배치되어야 합니다.
• 만약 트리의 **구조(노드들이 어떻게 연결되어 있는지)**가 딱 결정되었다면, 8개의 데이터를 크기순으로 나열했을 때 각 자리에 들어갈 수 있는 숫자는 오직 하나로 정해집니다.

 

 

레드블랙 삽입할때 

더블 레드 위로 계속 번질수도있음(확인 필요) 

 

 

• 노드 (Node): 트리를 구성하는 **'개별적인 요소(상자)'**입니다. 자식 노드를 가리키는 포인터(연결선)를 가지고 있으며, 트리 구조의 한 '층'을 차지하는 단위입니다.
• 키 (Key): 노드 안에 저장되는 **'실제 데이터 값'**입니다. 우리가 탐색할 때 비교하는 숫자(예: 50, 70 등)가 바로 키입니다.

 

 2-3-4 트리 (Multi-way Search Tree)

• 특징: 노드 1개 안에 키가 1개, 2개, 또는 3개까지 들어갈 수 있습니다.
• 2-노드: [ 50 ] (키 1개, 자식 2개)
• 3-노드: [ 30 | 50 ] (키 2개, 자식 3개)
• 4-노드: [ 20 | 40 | 60 ] (키 3개, 자식 4개)
• 여기서는 **"노드는 1개인데, 키는 3개"**인 상황이 발생합니다.

 

 

삽입 연산 시 루트에서 리프 노드로 이동하는 것이 필요하다. (옳음)

• 설명: 모든 이진 탐색 트리와 마찬가지로, 새로운 데이터를 삽입하기 위해서는 먼저 그 데이터가 들어갈 적절한 위치(리프 노드)를 찾아야 합니다. 이를 위해 루트부터 시작하여 키 값을 비교하며 아래로 내려가는 과정이 필요합니다.

 

위치를 찾는 과정'**과 **'노드를 쪼개는(분할) 과정'**을 나누어 생각해야 하기 때문입니다.

결론부터 말씀드리면, **"어디에 넣을지 찾아가는 길은 위에서 아래(Root → Leaf)"**이고, **"노드가 꽉 차서 쪼개지는 영향은 위로 전달될 수 있다"

 

 

 

 

레드블랙트리

점선, 실선중 뭐가 블랙, 레드인지 

 

점선의 의미: 위 노드인가, 아래 노드인가?

점선은 그 선의 아래에 있는 노드(자식 노드)의 색상을 나타냅니다.