0
BST와 2 개의 대기열이 있습니다. 삽입과 삭제가 가능한 가장 짧은 시간에 가능하도록하기 위해서 나는 매번 나무를 균형 잡을 필요가 있습니다. 이를 위해 나는 DSW 알고리즘을 사용한다.BST 균형을 유지하는 최적의시기는 언제입니까?
나는 이것을 모두 구현했으며 모두 훌륭하게 작동합니다. 내 문제는 내가 나무를 균형을 유지하는 가장 좋은시기가 언제인지 모르겠다.
나는 이것과 모든 종류의 정보에 대한 논문을 찾으려고했지만 어떤 것도 찾을 수 없다.
기본적으로 트리의 균형을 맞추는 것이 최적 일 때가 너무 많아서 너무 많은 시간이 걸리지 만 종종 내 삽입 & 삭제 시간이 길어질 정도로 충분하다는 것을 알아야합니다. 그래서 결국 전체 실행 시간은 가능한 짧습니다.
아이디어가 있으십니까?
이것은 내 머리의 제안에 불과합니다. 트리의 요소 수를 최대 깊이와 비교하면 어떨까요? n 요소의 경우 최적 깊이는 log2 (n) + 1이어야합니다. 실제 최대 깊이가 최적 깊이에서 너무 멀리 떨어져 있으면 트리가 부적절하게 균형을 잡았다는 것을 알게됩니다. – bstempi
나는이 아이디어를 좋아하지만 얼마나 멀리 떨어져 있는가? – Dee
당신이 나무를 얼마나 효율적으로 사용 하느냐에 달려 있다고 생각합니다. "너무 멀리"2 또는 3을 만들었 으면 매우 효율적인 나무를 갖게되지만 더 자주 균형을 조정하게됩니다. 더 큰 것으로 정의하면 트리 액세스 시간을 희생시키면서 트리 균형을 조정하는 데 소요되는 시간이 줄어 듭니다. 나는 당신의 나무가 무겁다는 것을 짐작하고, 수를 낮게 유지하십시오. 쓰기가 무거운 경우 계속하십시오. – bstempi