왜 바이너리 트리가 중요합니까?

Question

우리는 왜 바이너리 트리를 특별히 연구합니까? 일반적인 m-way 검색 트리 에서처럼 DataStructure 교과서에서 이진 트리만큼 중요한 것은 아닙니다.

이진 트리의 사용이 m- 웨이 트리를 초과합니까?

Answer 1

이진 트리는 가장 단순한 형태의 다중 방향 트리이므로 이러한 의미에서 공부하기가 더 쉽습니다.

멀티 웨이 나무의 라인을 따라 N 키와 N+1 포인터로 구성 노드를 가지고 :

   | 
    +-----+-----+-----+-----+ 
    | k00 | k01 | k02 | k03 | 
    +-----+-----+-----+-----+ 
/ |  |  |  \ 
p00  p01 p02 p03  p04 

가 검색에 따르도록하는 포인터를 확인하려면, 당신은 당신이 찾고있는 키를 비교 노드의 키에 대해 위의 예는 order-2 multi-way tree입니다 (나는 키와 2n+1 포인터를 갖는 것으로서 n을 정의하고 있습니다). 이 구조는 가장 작은 노드 수 "타락한"이시기

, 당신은 하나의 키와 두 개의 포인터, 당신의 고전 이진 트리와 끝까지 : 나는 대학에 갔다

 | 
    +-----+ 
    | k00 | 
    +-----+ 
/  \ 
p00  p01 

(나는거야 자유롭게 인정했다.), 우리는 알고리즘이 우아하기 때문에 이진 트리 을 처음으로으로 연구했다. 검색은 간단한 비교 노드였으며 두 개의 하위 트리 중 하나를 선택했습니다. 삽입 및 삭제도 비교적 쉽습니다.

이진 트리에서 검색은 정확히 같았지 만 삽입과 삭제가 더 복잡하고 서브 트리 루트를 통해 필요한 경우 하위 트리를 '회전'시키는 작업이 계속되었습니다. 균형이 잡힌.

그런 다음 올바른 노드를 찾으면 균형 잡힌 멀티 웨이 트리가 검색된 다음 노드 내에서 검색 개념을 얻습니다. 마지막으로 이진 트리와 기본적으로 동일한 균형 잡힌 멀티 웨이 트리가 나타납니다 순차 검색의 복잡성이 추가되고 노드 내 삽입 또는 삭제, 노드 자체의 결합 및 침입이 추가됩니다.

각 단계에서 알고리즘에 약간의 복잡성을 추가하기 만하면됩니다. 나는 그 진행에 문제가있는 사람들이 너무 많다는 것을 기억하지 않으므로 아마도 여러분이 언급 한 모든 교과서는 초보 수준에있을 것입니다.

아주 특별한 상황을 제외하고는 다중 경로 트리가 이진 트리보다 유용하다고 생각한 적이 없습니다. 그 때 디스크와 같은 느린 매체에서 나무의 노드를 읽고 섹터/클러스터/블록 크기에 맞게 최적화했습니다.

노드가 기본 디스크 블록과 동일한 지 확인하여 OS/2 (여기에 내 나이를 표시)에서 다중 경로 트리 구현을 개발했습니다. 이것은 약간의 낭비 된 공간을 초래할 수 있지만, 속도 향상은 그만한 가치가있었습니다.

메모리 내 내용의 경우, 이진 트리는 노드의 순차 검색과 하위 트리 선택을 결합해야하는 추가 복잡성이없는 다중 방식의 모든 장점을 가지고 있습니다.

이진 나무는 "우리가 왼쪽이나 오른쪽으로 움직여야할까요?"라는 말로 요약됩니다. 다중 경로는 "이 노드에서 키가 어디에있어 하위 트리를 선택할 수 있습니까?"입니다.

Answer 2

이진 트리는 이해하기 쉽고, 구현하기 쉽고, 빠르고 잘 작동합니다.이 교습 및/또는 사용에 충분하다고 생각합니다.

Answer 3

예를 들어 이진 트리는 힙 정렬 (이진 힙)에 사용됩니다. 가장 큰 (또는 가장 낮은) 항목이 항상 앞에 오도록 데이터를 매우 빠르게 정렬하는 방법입니다. 이것은 AI (A * 알고리즘)에서 예를 들어 사용됩니다.

Answer 4

'n-ary'나무에 대한 이진 나무의 이점은 흔히 binary space partitioning에서와 같이 간단한 예/아니오 결정 문제로 이어지는 것입니다.

Answer 5

저는 바이너리 트리가 DataStructure에서 많은 중요성을 부여하는 이유는 여기에 너무 많습니다. 이진 트리는 T/F, 예/아니요 등을 기반으로하는 트리를 의미합니다. Duo의 조합을 말합니다. 실제적으로 우리는 예 또는 아니오를 결정할 필요가있는 상황에 직면합니다. 참 또는 거짓. 이진 트리는 그러한 상황을 나타냅니다. 우리가 작업하는 소프트웨어는 실생활 시나리오를 해결하기 위해 내부적으로 사용되는 데이터 구조를 사용하는 솔루션입니다. 그래서 이진 트리가 그림으로 등장하고 일반적으로 사용되고 심지어 중요합니다. 나무의 나머지 부분은 일반적인 상황과 일치시키기위한 세부 사항 또는 추가 된 복잡성입니다. 시작을 위해 이진 트리가 항상 중요합니다.

Answer 6

트리 데이터 구조는 순서가 지정된 요소를 구성하는 데 자주 사용되기 때문에 (예 : a> b> c). 나무에 삽입 된 항목이 정렬 된 경우 왼쪽 노드의 하위 트리로 더 큰 요소와 오른쪽 하위 트리로 더 작은 요소를 나누기 위해 각 노드에 두 개의 분기가 필요합니다.

이 때문에 이진 트리가 m-ary 트리보다 훨씬 널리 퍼진 이유입니다. 예/아니오 결정 대 m-ary 결정의 용이성과는 아무런 관련이 없습니다!

Answer 7

위의 모든 대답에 덧붙여 임의의 트리는 이진 트리로 나타낼 수 있습니다 (왼쪽 링크는 노드의 첫 번째 자식 노드로 이동하고 오른쪽 링크는 다음 "형제"로 연결됩니다).