C/C++에서 2-3개의 트리(검색 및 삽입)?

2-3 트리는 트리 데이터 구조로 정의됩니다. 여기서 자식이 있는 모든 노드(내부 노드)에는 두 개의 자식(2-노드)과 하나의 데이터 요소 또는 세 개의 자식(3-노드)과 두 개의 데이터가 있습니다. 요소.

정의

내부 노드에 하나의 데이터 요소와 두 개의 자식이 있는 경우 이를 2노드라고 합니다.

내부 노드에 2개의 데이터 요소와 3개의 자식이 있는 경우 이를 3노드라고 합니다.

다음 문장 중 하나가 −

• T는 비어 있거나 비어 있습니다. 즉, T에는 노드가 없습니다.

• T는 데이터 요소 a가 장착된 2-노드입니다. T에 왼쪽 자식 L과 오른쪽 자식 R이 있으면 결론을 내립니다.

• L 및 R은 동일한 높이의 비어 있지 않은 2-3개의 트리로 처리됩니다.

• L의 각 요소보다 높습니다. 그리고

• R의 각 데이터 요소보다 작거나 같습니다.

• T는 데이터 요소와 b가 있는 3-노드이며 여기서 b는 b보다 작습니다. T에 왼쪽 자식 L, 가운데 자식 M, 오른쪽 자식 R이 있으면 결론을 내립니다.

• L, M, R은 같은 높이의 비어 있지 않은 2-3개의 트리로 처리됩니다.

• L의 각 데이터 요소보다 높고 M의 각 데이터 요소보다 작거나 같고; 그리고

• b는 M의 각 데이터 요소보다 높고 R의 각 데이터 요소보다 작거나 같습니다.

속성

• 모든 내부 노드는 2노드 또는 3노드로 취급됩니다.

• 모든 잎이 같은 수준에 있습니다.

• 모든 데이터는 정렬된 순서로 유지 또는 유지됩니다.

작업

검색 중

2-3 트리에서 항목을 검색하는 것은 이진 검색 트리에서 항목을 검색하는 것과 같습니다. 각 노드의 데이터 요소는 순서대로 처리되므로 검색 기능은 올바른 하위 트리로 이동하고 결국 항목으로 구성된 올바른 노드로 이동합니다.

• T를 2-3 트리로 처리하고 d를 우리가 찾고자 하는 데이터 요소로 처리합니다. T가 비어 있으면 d는 T에 없고 수행됩니다.

• r을 T의 근으로 취급합니다.

• r을 잎이라고 하자. d가 r에 없으면 결과적으로 d는 T에 없습니다. 그렇지 않으면 d는 T에 있습니다. 특히 d는 리프 노드에서 찾을 수 있습니다. 더 이상의 단계가 필요하지 않으며 수행됩니다.

• r이 왼쪽 자식 L과 오른쪽 자식 R이 있는 2-노드로 처리된다고 가정합니다. e를 r의 데이터 요소로 취급합니다.

세 가지 경우가 있습니다 -

• d가 e와 같으면 T에서 d를 찾고 수행합니다.

• d가 e보다 작으면 정의에 따라 2-3 트리인 T를 L로 설정하고 2단계로 돌아갑니다.

• d가 e보다 크면 T를 R로 설정하고 2단계로 돌아갑니다.

• r이 왼쪽 자식 L, 가운데 자식 M, 오른쪽 자식 R이 있는 3-노드라고 가정합니다. a와 b를 r의 두 데이터 요소로 취급한다고 가정합니다. 여기서 a

  • d가 또는 b와 같으면 d는 T에 있고 수행됩니다.

  • d가 a보다 작으면 T를 L로 설정하고 2단계로 돌아갑니다.

  • a가 d보다 작고 d가 b보다 작으면 T를 M으로 설정하고 2단계로 돌아갑니다.

  • d가 b보다 크면 T를 R로 설정하고 2단계로 돌아가십시오.

삽입

삽입은 키의 적절한 위치를 검색하고 거기에 키를 추가하거나 추가하는 방식으로 수행됩니다. 노드가 4노드가 되면 노드는 2개의 2노드로 나뉘고 중간 키는 상위 노드로 이동합니다. 그러면 부모는 4노드가 될 수 있으며, 이 경우에도 분할되어 자신의 부모에게 키를 전파합니다. 이 프로세스는 2노드이고 나눌 필요가 없는 부모에 도달할 때까지 또는 루트에 도달할 때까지 반복됩니다. 이 경우 루트에 도달할 때까지 전파된 요소를 구현하여 2노드인 새 루트를 만듭니다 . 이 알고리즘의 도움으로 수행할 연산의 수는 트리의 높이에 비례하므로 트리가 완벽하게 균형을 이루기 때문에 대수적입니다. 이 프로세스는 결과가 2-3 트리로 처리되도록 합니다. 특히 모든 잎은 동일한 깊이에 유지됩니다.

아래 다이어그램은 이 프로세스의 가능한 경우를 설명하거나 보여줍니다.

3가지 가능한 경우에 대해 2-3 트리에 숫자 삽입.