4
이 간단한 트리의 이름을 찾고 있는데, 이것은 이진 검색 트리를 매우 간단하게 일반화 한 것입니다.이 트리의 이름은 무엇입니까?
설명입니다. 트리의 모든 노드는 고정 된 수의 최대 키 MI와 최소 수의 키 (단지 1)를 갖습니다. 키가 정렬됩니다. 모든 노드에는 자식에 대한 MI + 1 외부 링크가 있으며 b- 트리와 비슷합니다. 자식 노드는 b- 트리처럼 부모의 두 개의 가까운 키 간격의 키만 포함합니다.
삽입 및 삭제 작동 방식이 다릅니다.
삽입 :
루트부터 시작합니다.
확인중인 노드에 MI 키가 없기 때문에 공간이 충분하지 않으므로 키가 옳은 위치에 추가됩니다.
노드가 가득차면 체크인합니다. 이 범위의 하위 항목이 없으면 우리는 키만으로 항목을 만듭니다. 기타 등등.
DELETION : 나는 노드의 예 "ACE"를했다, 나는 "E"를 삭제해야하지만, "C"와 "E"사이의 간격에 아이가있는 경우
삭제에, , 나는 아이의 가장 큰 요소를 얻고 그것을 "E"로 대체합니다 (요소를 제거하면 차례대로 다른 요소를 부모로부터 부모로 옮길 필요가 있기 때문에 여기에서 재귀해야 할 수도 있음). 이보다 조금 더 복잡하지만 일반적으로 요소를 자식에서 삭제 된 키를 소유 한 노드로 이동해야합니다.
이것은 매우 비공식적으로 지정되었지만 이진 트리의 일반적인 일반화 된 것으로 보이는 이름을 찾을 수 없음을 알고 있습니다.
노드에 MI 키가있을 수 있지만 삽입시 "자식"이라고 말하면됩니다. 자녀가 중요한 정보로 선택되는 방법을 명확히하십시오. – marcog
@margoc : 나는 현재 노드가 꽉 찼다면 우리가 이미 가지고있는 두 개의 키로 구분 된 범위의 링크 된 자식에게갑니다. 따라서 MI가 4이고 루트 노드 "A C M Z"에 있고 "E"를 추가해야하는 경우 A-C 범위에 연결된 하위 항목으로 이동하려고 시도합니다. 아무 것도 없다면 나는 그것을 창조한다. – antirez