主题：【原创】新时代新潮流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）。

这样分析对不对？

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