나는 시간의 중간 값을 찾을 수있는 Morris InOrder 탐색을 사용하여 http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8에 주어진 솔루션을 발견했습니다.O (logn) 시간 복잡도에서 BST의 중앙값
그러나 O(logn) 시간을 사용하여 동일한 결과를 얻을 수 있습니까? 여기에 같은 질문을했습니다. - http://www.careercup.com/question?id=192816
노드의 왼쪽 및 오른쪽 자손 수를 유지하는 경우 중앙값 위치를 검색하여 O (logN) 시간에 수행 할 수 있습니다. 사실, O (logn) 시간에서 k 번째로 큰 요소를 찾을 수 있습니다.
물론 이것은 트리가 균형을 이룬 것으로 가정합니다. 카운트를 유지하더라도 삽입/삭제의 복잡성은 변하지 않습니다.
트리가 균형을 잡지 않으면, 오메가 (n) 최악의 경우의 복잡성이 있습니다.
참조 : Order Statistic Tree.
btw, BigO 및 Smallo는 매우 다릅니다 (귀하의 제목은 Smallo라고 말함).
균형 잡힌 나무를 보장하지 않으면 불가능합니다.
left 포인터가 모두 NULL 인 경우 (예 : 모든 노드) 모든 노드가 올바른 자식 만 가질 수 있도록 모든 축약 형 트리를 고려하십시오. 즉 모든 실제적인 목적에서 "트리"는 실제로 단독 연결 목록입니다).
중간 노드 (모두)에 액세스하는 것은 선형 시간을 사용합니다. 노드 N이 중앙값임을 알았더라도 그 노드에 도달하려면 N 단계가 필요합니다.
rabbit 및 turtle 포인터를 사용하여 중간 값을 찾을 수 있습니다. 토끼는 BST의 순회 트래버스에서 거북이의 두 배 빠르게 움직입니다. 이 방법은 토끼가 BST의 중앙에있는 거북이의 끝까지 도달 할 때 발생합니다.
full explanation을 참조하십시오.
링크가 작동하지 않습니다 – kameny
링크 된 도메인은 판매용입니다. – SynerCoder
총계가 Θ (n) 인 후계 함수를 호출하므로 Θ (n)이 Θ (log n)이 아닌 시간이 걸립니다. – templatetypedef
Order Statisitc Tree에 대한 링크를 제공해 주셔서 감사합니다. 그것은 내 질문에 대답하는 heleped. – Harish