西西河

主题:【原创】新时代新潮流WebOS 【1】 -- 邓侃

共:💬594 🌺1902
全看分页树展 · 主题 跟帖
家园 在DOM上定位事件发生的leaf

这个例子不完整,我们到底要在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)。

这样分析对不对?

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河