主题:【原创】新时代新潮流WebOS 【1】 -- 邓侃
共:💬594 🌺1902
这个例子不完整,我们到底要在DOM上找什么?
找对鼠标所在位置负责的那个character?则是树搜索,O(logN)
设想,browser现在知道鼠标的位置(X,Y),如何定位鼠标移动这个事件发生在哪个character上?
如果characters之间有重叠,那么就不能简单地从DOM树的根节点一路向叶子节点找,因为中间节点占据的区域有重叠。所以,成本不是O(logN)。
也就是说,用DOM树来表述2D图像是不方便的。对于这种情形,R-Tree或许更强有力。
但是假设我们要做的仅仅是简单页面的结构处理,还不如简单遍历,也就是链式结构。
如果我们规定有效元素只是叶子点,内部点都算overhead。那树结构也不过是把O(N)的问题复杂化为O(N+logN),还是O(N)。
如果想遍历树的叶子节点,成本是O(N),但是这里有个前提,必须事先用链表把所有树的叶子节点串联起来。如果没有叶子链表,那么要访问每个叶子节点,成本等同于遍历树,也就是O(N logN)。
这样分析对不对?
- 相关回复 上下关系8
压缩 2 层
🙂最早的HTML也是很简单的,结果..... 6 moudy 字1054 2009-04-09 11:26:45
🙂在DOM上定位事件发生的leaf
🙂DOM树来表述2D图像是不方便的,这句话需要商量的 2 木头人 字435 2009-04-10 07:13:18
🙂就是类似MVC? 1 数字崇拜 字12 2009-04-09 04:32:11
🙂从开发效率和运行效率比较,长远来看总是前者胜出 2 四处张望 字209 2009-04-08 04:02:16
🙂树性结构有其必要性:要开发速度还是效率? 8 t1000 字663 2009-04-02 09:44:24