이진 검색 트리의 정의를 찾으려고 노력하고 있으며 어디에서나 다른 정의를 계속 찾습니다.
어떤 하위 트리에서는 왼쪽 하위 키가 루트보다 작거나 같다고 말합니다.
어떤 하위 트리에서는 올바른 하위 키가 루트보다 크거나 같다고 말합니다.
저의 오래된 대학 데이터 구조 책은 “모든 요소에는 키가 있고 두 요소에는 동일한 키가 없습니다”라고 말합니다.
bst에 대한 보편적 인 정의가 있습니까? 특히 동일한 키의 여러 인스턴스가있는 트리로 수행 할 작업과 관련하여.
편집 : 어쩌면 내가 명확하지 않은, 내가보고있는 정의는
1) 왼쪽 <= 루트 <오른쪽
2) 왼쪽 <루트 <= 오른쪽
3) 왼쪽 <root <오른쪽으로 중복 키가 존재하지 않습니다.
답변
많은 알고리즘에서 중복이 제외되도록 지정합니다. 예를 들어, MIT 알고리즘 책의 예제 알고리즘은 일반적으로 중복없이 예제를 제공합니다. 중복을 구현하는 것은 (사소한 목록이나 특정 방향으로) 매우 사소한 일입니다.
(내가 본) 대부분은 왼쪽 자식을 <=로 지정하고 오른쪽 자식을>로 지정합니다. 실제로, 오른쪽 또는 왼쪽 자식 중 하나가 루트 노드와 같도록 허용하는 BST는 중복 노드가 허용되는 검색을 완료하기 위해 추가 계산 단계가 필요합니다.
노드의 한쪽에 ‘=’값을 삽입하려면 노드를 자식으로 배치하기 위해 해당 측면에 트리를 다시 쓰거나 노드가 그랜드로 배치되므로 중복을 저장하기 위해 노드에서 목록을 사용하는 것이 가장 좋습니다. -child, 아래 지점에서 검색 효율성을 일부 제거합니다.
대부분의 강의실 예제는 개념을 묘사하고 전달하기 위해 단순화되었습니다. 많은 실제 상황에서 쪼그리고 앉을 가치가 없습니다. 그러나 “모든 요소에는 키가 있고 두 요소에는 동일한 키가 없습니다”라는 문구는 요소 노드에서 목록을 사용하여 위반되지 않습니다.
따라서 데이터 구조 책이 말한 것과 함께하십시오!
편집하다:
이진 검색 트리의 범용 정의는 두 방향 중 하나에서 데이터 구조를 순회하는 것에 기초하여 키를 저장하고 검색하는 것을 포함합니다. 실용적인 의미에서, 값이 <> 인 경우 두 ‘방향’중 하나로 데이터 구조를 탐색합니다. 따라서 이러한 의미에서 중복 값은 전혀 의미가 없습니다.
이것은 BSP 또는 이진 검색 파티션과 다르지만 그다지 다릅니다. 검색 알고리즘에는 ‘여행’에 대한 두 가지 방향 중 하나가 있거나 수행됩니다 (성공 여부는 상관 없습니다). 따라서 중복이 실제로는 고유하기 때문에 원래의 답변이 ‘유니버설 정의’의 개념을 다루지 않았다고 사과합니다. 주제 (이진 검색의 일부가 아닌 성공적인 검색 후 처리하는 항목)
답변
이진 검색 트리가 빨간색 검은 색 트리이거나 모든 종류의 “트리 회전”작업을하려는 경우 중복 노드가 문제를 일으킬 수 있습니다. 트리 규칙이 다음과 같다고 상상해보십시오.
왼쪽 <루트 <= 오른쪽
이제 루트가 5이고 왼쪽 자식이 0이고 오른쪽 자식이 5 인 간단한 나무를 상상해보십시오. 루트에서 왼쪽 회전을하면 왼쪽 자식에서 5, 오른쪽 자식으로 루트에서 5가됩니다. 없어요. 이제 왼쪽 트리의 어떤 것이 루트와 같지만 위의 규칙은 left <root라고 가정합니다.
빨간색 / 검은 색 나무가 때때로 순서를 벗어나는 이유를 알아 내려고 몇 시간을 보냈습니다. 문제는 위에서 설명한 것입니다. 바라건대 누군가가 이것을 읽고 미래에 디버깅 시간을 절약 할 수 있기를 바랍니다!
답변
세 가지 정의는 모두 수용 가능하고 정확합니다. 그들은 BST의 다른 변형을 정의합니다.
대학 데이터 구조의 책은 그 정의가 유일한 것이 아니라는 것을 명확히하지 못했습니다.
확실히, 복제를 허용하면 복잡성이 추가됩니다. “left <= root <right”정의를 사용하고 다음과 같은 트리가있는 경우 :
3
/ \
2 4
이 트리에 “3”복제 키를 추가하면 다음과 같은 결과가 발생합니다.
3
/ \
2 4
\
3
중복은 연속적인 수준이 아닙니다.
이는 위와 같이 BST 표현에서 복제를 허용 할 때 큰 문제입니다. 복제는 여러 레벨로 분리 될 수 있으므로 복제의 존재를 확인하는 것은 노드의 직계 자식을 확인하는 것만 큼 간단하지 않습니다.
이 문제를 피할 수있는 옵션은 중복을 구조적으로 (별도의 노드로) 나타내지 않고 대신 키 발생 횟수를 계산하는 카운터를 사용하는 것입니다. 이전 예제는 다음과 같은 트리를 갖습니다.
3(1)
/ \
2(1) 4(1)
중복 “3”키를 삽입하면 다음과 같이됩니다.
3(2)
/ \
2(1) 4(1)
이는 일부 추가 바이트 및 카운터 작업을 희생하면서 조회, 제거 및 삽입 작업을 단순화합니다.
답변
BST에서, 노드의 왼쪽에서 내림차순의 모든 값은 노드 자체보다 작거나 같습니다 (나중에 참조). 유사하게, 노드의 오른쪽에서 내림차순의 모든 값은 노드 값보다 크거나 같습니다 (a) .
일부 BST는 중복 값을 허용하도록 선택할 수 있으므로 위의 “또는 같음”한정자입니다.
다음 예는 명확 할 수 있습니다.
|
+--- 14 ---+
| |
+--- 13 +--- 22 ---+
| | |
1 16 +--- 29 ---+
| |
28 29
여기에는 중복을 허용하는 BST가 표시됩니다. 값을 찾으려면 루트 노드에서 시작하여 검색 값이 노드 값보다 작거나 큰지 여부에 따라 왼쪽 또는 오른쪽 하위 트리로 내려갑니다.
다음과 같은 방법으로 재귀 적으로 수행 할 수 있습니다.
def hasVal (node, srchval):
if node == NULL:
return false
if node.val == srchval:
return true
if node.val > srchval:
return hasVal (node.left, srchval)
return hasVal (node.right, srchval)
그리고 그것을 호출 :
foundIt = hasVal (rootNode, valToLookFor)
중복은 동일한 값을 가진 다른 노드에 대한 값을 찾은 후에 계속 검색해야 할 수 있으므로 약간 복잡합니다.
(a)는 당신이 할 수 소원을 제공, 그래서 당신은 당신이 특정 키를 검색하는 방법을 실제로 일종의 그 반대 방향을 조정해야합니다. BST는 오름차순이든 내림차순이든 상관없이 정렬 된 순서 만 유지하면됩니다.
답변
Cormen, Leiserson, Rivest 및 Stein의 세 번째 버전 인 “Introduction to algorithms”책에서 BST (Binary Search Tree)는 중복 을 허용하는 것으로 명시 적으로 정의됩니다 . 그림 12.1과 다음 (287 페이지)에서 볼 수 있습니다.
“이진 검색 트리의 키는 항상 이진 검색 트리 속성을 만족하는 등의 방식으로 저장됩니다하자가
x. 이진 검색 트리의 노드 수를하는 경우는y왼쪽 하위 트리에서 노드x후y:key <= x:key. 경우y입니다 오른쪽 하위 트리의 노드x다음,y:key >= x:key. “
또한, 레드 – 블랙 트리는 다음 페이지 (308)에 다음과 같이 정의된다
“적색 검정 트리는 노드 당 하나의 추가 비트 저장소가있는 이진 검색 트리입니다.”
따라서이 책에 정의 된 적갈색 트리는 중복을 지원합니다.
답변
모든 정의가 유효합니다. 구현에서 일관성이 유지되는 한 (항상 동일한 노드를 오른쪽에 두거나 항상 왼쪽에 두거나 절대 허용하지 마십시오) 괜찮습니다. 나는 그것을 허용하지 않는 것이 가장 일반적이라고 생각하지만, 그들이 허용되고 왼쪽이나 오른쪽에 배치하면 여전히 BST입니다.
답변
빨강-검정 트리 구현 작업 빨강-검정 삽입 회전으로 제약 조건을 풀어야한다는 것을 깨달을 때까지 여러 키로 나무를 유효성 검사하는 데 문제가 발생했습니다.
left <= root <= right
내가보고있는 문서 중 중복 키를 허용하지 않고 회전 방법을 다시 작성하고 싶지 않기 때문에 노드 내에서 여러 값을 허용하도록 노드를 수정하기로 결정했으며 중복 키는 입력하지 않았습니다. 나무.
