tag:blogger.com,1999:blog-2564777502681463717.post1397938681668922314..comments2023-12-31T10:17:57.560-05:00Comments on Teaching, Playing, and Programming: On Balanced Trees and Car InsuranceChris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-2564777502681463717.post-76474463531576174492008-05-20T22:19:00.000-04:002008-05-20T22:19:00.000-04:00even when buffering is not feasible, (e.g. in the ...even when buffering is not feasible, (e.g. in the car insurance database example), it may be possible to use an unbalanced tree, and balance it every night (or during any expected breaks in the insertion process) by shuffling the entries. depending on the performance requirements, this might be better than suffering the overheads of a balanced tree at every insertion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-10611344128787595732008-05-20T09:29:00.000-04:002008-05-20T09:29:00.000-04:00Very good comments. Thank you http://www.6i6.deVery good comments. Thank you http://www.6i6.dehafhttps://www.blogger.com/profile/02725670092870101088noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-57639826073546162062008-05-17T19:57:00.000-04:002008-05-17T19:57:00.000-04:00Loi please.Perhaps in some cases you could buffer ...<A HREF="http://nomorelol.com/" REL="nofollow">Loi please.</A><BR/><BR/>Perhaps in some cases you could buffer it. But consider a car insurance database searchable by the policy end date. New records will be added every day, with generally strictly increasing dates. And you cannot buffer the data for long enough enough to make a difference.<BR/><BR/>In the case where you need to buffer it, it makes sense to just use a balanced binary tree and avoid hacks (that will have a performance penalty as well) to make the unbalanced trees work.Mattiashttps://www.blogger.com/profile/10240253818280933714noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-25051261127196066012008-05-16T22:05:00.000-04:002008-05-16T22:05:00.000-04:00LOL, I suppose you could buffer it.LOL, I suppose you could buffer it.Epic Fail Guyhttps://www.blogger.com/profile/11706976165013506029noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-79952838703101330362008-05-16T05:58:00.000-04:002008-05-16T05:58:00.000-04:00Epic Fail > You could shuffle all data, if you hav...Epic Fail > You could shuffle all data, if you have access to it beforehand. <BR/><BR/>If the data is slowly trickling in, you do not have the luxury of being able to shuffle it.Unknownhttps://www.blogger.com/profile/07775360304045063973noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-85120087653380108582008-05-16T03:42:00.000-04:002008-05-16T03:42:00.000-04:00At the risk of sounding stupid and naive, I'd like...At the risk of sounding stupid and naive, I'd like to ask what would happen if you simply shuffled a (possibly) sorted list in advance of interning it into a normal non-balanced binary tree? The odds are, especially for very large lists, that the tree would retain something around O(log n) performance. Right?<BR/><BR/>Oh and nice blog btw, keep writingEpic Fail Guyhttps://www.blogger.com/profile/11706976165013506029noreply@blogger.com