For those of you following along at home or checking the archives in days to come, I came across a really good lecture on interval trees:
https://www.youtube.com/watch?v=q0QOYtSsTg4 It's presented by Robert Sedgewick. Yes, *that* Robert Sedgewick, the algorithms guy. Well, the algorithms guy for people like me that just don't have the background for Knuth. The lecture isn't enough to just run and implement interval trees, but it does explain really well the basic concept and illustrates exactly why it's such a powerful and tidy way to handle interval searches. Fair warning: If you don't understand binary search trees and how to build and maintain them by hand, it probably won't make sense. If you do know that already, the interval tree is a BST with some augmentation. When you insert, you walk back up and attach some extra information to the node to indicate the max value along the subtree path. (Likewise, you would have to reset this value if you deleted the max element.) This small amount of hinting costs a bit during insert/delete, but then saves you having to scan parts of branches or even whole branches when searching. It's kind of genius. So, for anyone with an interest in this subject, check it out. The ultimate benefit of this simple+powerful data structure is that insert/search/delete are guaranteed to run in log N instead of N time. That's huge. That's what you get from binary trees normally. Sedgewick says that the runtime for finding all interval intersections is R log N, which is a huge advantage over the alternative of N. It's just a massive, massive optimization. This is a fairly specific problem, granted, but if your'e doing schedule fitting, schedule/capacity analysis...or anything having to do with intervals, this algorithm is the real deal. I'm talking about datetime intervals, but intervals are any start-endpoint pair on a numberline, there are lots of things like that other than date times. P.S. For any Postgres fans, check out tsrange with a GIST index and the OVERLAP operator. Subsecond results for scheduling range conflict management with lots of rows. ********************************************************************** 4D Internet Users Group (4D iNUG) FAQ: http://lists.4d.com/faqnug.html Archive: http://lists.4d.com/archives.html Options: http://lists.4d.com/mailman/options/4d_tech Unsub: mailto:4d_tech-unsubscr...@lists.4d.com **********************************************************************
