[binary-tree] 이진 트리의 응용 프로그램은 무엇입니까?

대부분의 사람들이 이진 트리에 대해 이야기 할 때, 이진 검색 트리 에 대해 생각하지 않는 것보다 더 흔하기 때문에 먼저 다룰 것입니다.

불균형 이진 검색 트리는 실제로 학생들에게 데이터 구조에 대한 교육 이상을 제공하는 데 유용합니다. 데이터가 비교적 임의의 순서로 나오지 않는 한 단순한 이진 트리의 균형 이 맞지 않기 때문에 트리가 최악의 형태로 쉽게 변질 될 수 있기 때문 입니다.

좋은 사례 : 한 번은 조작 및 검색을 위해 데이터를 이진 트리에로드 한 일부 소프트웨어를 수정해야했습니다. 데이터를 정렬 된 형식으로 작성했습니다.

Alice
Bob
Chloe
David
Edwina
Frank

다시 읽을 때 다음 트리로 끝났습니다.

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

이것은 퇴화 형태입니다. 해당 트리에서 Frank를 찾으면 6 개의 노드를 모두 검색해야 찾을 수 있습니다.

이진 트리는 균형을 잡을 때 검색에 정말 유용합니다. 여기에는 루트 노드를 통해 하위 트리를 회전하여 두 하위 트리 사이의 높이 차이가 1 이하가되도록합니다. 한 번에 하나씩 위의 이름을 균형 트리에 추가하면 다음과 같은 시퀀스가 ​​제공됩니다.

1.   Alice
    /     \
   =       =

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

항목이 추가됨에 따라 전체 하위 트리가 왼쪽으로 회전하는 것을 볼 수 있습니다 (3 단계와 6 단계 O(log N)에서 O(N). 어느 시점에서도 가장 높은 NULL ( =)은 둘 이상의 레벨만큼 가장 낮은 것과 다릅니다. 그리고, 위의 최종 트리에, 당신은 (세 개의 노드를보고 프랭크을 찾을 수 있습니다 Chloe, Edwina마지막으로하고 Frank).

물론 이진 트레스가 아닌 균형 잡힌 멀티 웨이 트리 를 만들 때 더 유용 할 수 있습니다 . 이는 각 노드가 하나 이상의 항목을 보유 함을 의미합니다 (기술적으로 N 항목과 N + 1 포인터를 보유합니다. 이진 트리는 1 항목과 2 포인터가있는 단방향 다중 경로 트리의 특수한 경우입니다).

3 방향 트리를 사용하면 다음과 같이 끝납니다.

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

일반적으로 항목 인덱스의 키를 유지 관리하는 데 사용됩니다. 노드가 정확히 디스크 블록 크기 (예 : 512 바이트) 인 하드웨어에 최적화 된 데이터베이스 소프트웨어를 작성했으며 단일 노드에 가능한 많은 키를 넣었습니다. 포인터 이 경우 실제로 인덱스 파일에서 별도의 고정 길이 레코드 직접 액세스 파일에 기록 수 있었다 (그래서 레코드 번호는 X단지에 추구로 볼 수 있습니다 X * record_length).

예를 들어 포인터가 4 바이트이고 키 크기가 10 인 경우 512 바이트 노드의 키 수는 36입니다. 총 36 개의 키 (360 바이트)와 37 개의 포인터 (148 바이트)는 총 508 바이트입니다. 노드 당 4 바이트가 낭비됩니다.

다 방향 키를 사용하면 2 단계 검색 (노드에서 올바른 키를 찾기 위해 작은 순차적 (또는 선형 이진) 검색과 결합 된 올바른 노드를 찾기위한 다 방향 검색)의 복잡성이 발생하지만 장점은 다음과 같습니다. 이보다 더 적은 디스크 I / O를 수행합니다.

메모리 내 구조 에서이 작업을 수행 할 이유가 없습니다. 균형 이진 트리를 고수하고 코드를 간단하게 유지하는 것이 좋습니다.

또한 데이터 세트가 작을 때 O(log N)오버 의 장점이 O(N)실제로 나타나지는 않습니다. 주소록에 15 명을 저장하기 위해 다 방향 트리를 사용하는 경우 아마 과잉 일 수 있습니다. 지난 10 년 동안 수십만 고객의 모든 주문과 같은 것을 저장할 때 장점이 있습니다.

big-O 표기법의 요점은 N무한대 에 접근 할 때 발생하는 상황을 나타내는 것 입니다. 어떤 사람들은 동의하지 않을 수도 있지만 데이터 세트가 특정 크기 이하로 유지되는 것이 확실하다면 다른 방법으로 거품 정렬을 사용하는 것이 좋습니다. 🙂

이진 트리의 다른 용도와 관련하여 다음과 같은 많은 것들이 있습니다.

• 높은 키가 왼쪽 (또는 아래 또는 오른쪽 및 오른쪽)이 아닌 낮은 키보다 높 거나 같은 이진 힙 .
• 해시 테이블과 유사한 해시 트리;
• 컴퓨터 언어 컴파일을위한 추상 구문 트리;
• 데이터 압축을위한 허프만 트리;
• 네트워크 트래픽을위한 라우팅 트리.

검색 트리에 대해 생성 한 설명이 많으면 다른 것에 대해 자세하게 설명하고 싶지만 원하는 경우 조사하기에 충분해야합니다.

답변

    *
   / \
  +   2
 / \
1   3