나무, 빨강과 검정 나무

"안녕, 아미고!"

"안녕, 리시!"

"거기서 내 오래된 노트를 찾아서 흥미로운 자료를 준비했습니다. 당신이 그것을 듣고 싶어 할 것 같아요."

"들어봅시다. 당신은 항상 흥미로운 것을 발견하고 나중에 매우 유용하다는 것을 증명합니다."

"좋아요. 오늘은 나무 에 대해 이야기하고 싶기 때문에 그래프 부터 시작하겠습니다 ."

" 그래프는 점과 이를 연결하는 선의 체계입니다. 점을 그래프의 정점이라고 하고 선을 그래프의 가장자리라고 합니다. 예를 들면 다음과 같습니다."

"그래프는 다양한 실제 프로세스와 작업에 대한 수학적 모델로 사용하기에 매우 편리합니다. 그래프를 위해 다양한 작업과 알고리즘이 발명되었기 때문에 꽤 자주 사용됩니다."

"예를 들어 정점이 도시이고 가장자리가 도로라고 가정합니다. 그런 다음 도시 간 최단 도로 검색은 « 그래프가 주어지면 두 정점 사이의 최단 경로 찾기»가 됩니다. "

"하지만 A에서 B로 가는 경로는 B에서 A로 가는 경로와 항상 같은 것은 아닙니다. 따라서 때로는 두 개의 다른 선을 갖는 것이 좋습니다. 이를 위해 선(그래프의 가장자리)을 화살표로 대체합니다. 즉, 그래프에는 두 개의 화살표가 있을 수 있습니다. 하나는 A에서 B로, 다른 하나는 B에서 A로."

"그래프가 화살표를 사용하면 유향 그래프 라고 하고 , 선만 있으면 무방향 그래프 라고 합니다 ."

"각 꼭짓점은 고유한 수의 가장자리를 가질 수 있습니다. 꼭짓점에는 가장자리가 전혀 없을 수도 있습니다. 반대로, 꼭짓점은 가장자리로 다른 모든 꼭짓점에 연결될 수 있습니다. 그래프의 각 꼭지점 쌍이 가장자리로 연결  되면 완전한 그래프라고 합니다. "

"에지를 사용하여 그래프의 모든 정점에 도달할 수 있다면 연결된 그래프 라고 합니다. 3개의 개별 정점이 있고 에지가 없는 그래프는 여전히 그래프이지만 연결 되지 않은 그래프라고 합니다."

"N개의 꼭지점에서 연결된 그래프를 형성하려면 최소한 N-1개의 가장자리가 필요합니다. 이러한 유형의 그래프를 트리라고 합니다."

"또한 일반적으로 하나의 정점이 트리의 루트 로 선택되고 나머지는 가지로 선언됩니다. 자체 가지가 없는 나뭇가지를 잎 이라고 합니다 . 예를 들면 다음과 같습니다."

"트리의 각 요소에 두 개의 자식이 있는 경우 이진 트리라고 합니다 . 즉, 0 또는 2개의 분기가 있을 수 있습니다. 오른쪽 상단에서 이진 트리를 볼 수 있습니다 ."

" 트리는 각 가지에 2개의 자식이 있고 모든 잎(자식이 없는 정점)이 같은 행에 있을 때 완전한 이진 트리라고 합니다."

"예를 들어:"

"왜 이 나무들이 필요한가요?"

"오, 트리는 많은 곳에서 사용됩니다. 일반적으로 이진 트리는 정렬된 구조화된 데이터입니다."

"그게 뭐야?"

"예, 매우 간단합니다. 각 정점에 특정 값을 저장합니다. 그리고 각 요소는 규칙을 따릅니다. 오른쪽 자식에 저장된 값은 꼭짓점에 저장된 값보다 커야 하며 왼쪽 자식에 저장된 값은 정점에 저장된 값보다 작아야 합니다.  이 순서를 통해 필요한 트리의 요소를 빠르게 찾을 수 있습니다."

"그게 무슨 뜻인지 명확히 할 수 있습니까?"

"트리 요소는 일반적으로 추가하여 정렬됩니다. 13, 5, 4, 16, 8, 11, 10의 7개 요소가 있다고 가정합니다."

"트리에 요소를 추가하는 방법은 다음과 같습니다."

"이 트리에서 숫자 7을 찾는 경우 검색 방법은 다음과 같습니다."

"0) 루트에서 시작합니다."

"1a) 7은 13과 같습니까? 아니오"

"1b) 7이 13보다 큽니까? 아니요, 왼쪽 하위 트리로 이동합니다."

"2a) 7은 5와 같습니까? 아닙니다."

"2b) 7이 5보다 큽니까? 예, 오른쪽 하위 트리로 이동합니다."

"3a) 7은 8과 같습니까? 아니오"

"3b) 7이 8보다 큽니까? 아니요, 왼쪽 하위 트리로 이동합니다."

"4a) 왼쪽 하위 트리가 없습니다. 즉, 트리에 숫자 7이 없습니다."

"아. 즉, 루트에서 원하는 숫자의 위치까지의 경로에 있는 정점만 확인하면 됩니다. 네, 정말 빠릅니다."

"게다가 트리가 균형을 이루고 있으면 백만 개의 요소를 검색하기 위해 약 20개의 정점만 통과하면 됩니다."

"동의합니다. 그다지 많지 않습니다."

"균형 트리가 무엇을 의미합니까?"

"왜곡되지 않은 트리, 즉 긴 가지가 없는 트리. 예를 들어 트리를 만들 때 요소가 이미 정렬되어 있었다면 하나의 가지로 구성된 매우 긴 트리를 만들었을 것입니다. "

"흠. 네 말이 맞아. 그럼 우린 어떡하지?"

"이미 짐작하셨겠지만 가장 효율적인 트리는 거의 같은 길이의 가지를 가집니다. 그런 다음 각 비교는 나머지 하위 트리의 가장 큰 부분을 버립니다."

"그래서, 우리는 나무를 재건해야 합니까?"

"예. 완전한 이진 트리에 최대한 가깝게 만들기 위해서는 «균형을 잡아»야 합니다."

"이 문제를 해결하기 위해 자체 균형 트리가 발명되었습니다.  요소를 추가한 후 트리가 왜곡되면 모든 것이 정상이 되도록 요소를 약간 재정렬합니다.  다음은 균형 조정의 예입니다."

"이 나무들 중 일부는 레드 -블랙 트리 로 알려져 있습니다 ."

"왜 그들은 레드-블랙이라고 불리는가?"

"그들의 발명가는 두 가지 색상을 사용하여 모든 정점을 그렸습니다. 한 색상은 빨간색이고 다른 하나는 검은색이었습니다. 다른 정점은 다른 규칙을 따릅니다. 이것이 균형 조정 절차의 전체 기반을 형성합니다."

"예를 들어:"

"그래서 이 규칙은 무엇입니까?"

"1) 빨간색 정점은 빨간색 정점의 자식이 될 수 없습니다."

"2) 모든 리프의 블랙 깊이는 동일합니다(블랙 깊이는 루트에서 경로에 있는 블랙 정점의 수를 나타냄)."

"3) 나무의 뿌리는 검다."

"어떻게 작동하는지 설명하지 않겠습니다. 이미 머리가 터질 것입니다."

"예. 프로세서에서 약간의 연기가 나고 있습니다."

"여기 링크가 있습니다. 원하는 경우 여기에서 자세한 내용을 읽을 수 있습니다."

추가 자료 링크

"그럼 이제 가서 쉬세요."