Note to self: In Fractional cascading we first find the canonical nodes based on x coordinate (in the main tree). Then we only traverse and report the nodes in the auxillary arrays for which the main node is a canonical node i.e., for all the canonical nodes we traverse the auxillary array upto a certain point where y coordinate falls in the range.
Great lecture! I have a question, it's not quite clear what goes in the nodes of the 2D range tree, does it save the associated tree of points in Y coordinates orders ? if so, then what is stored in the nodes of the associated tree? I'm leaving a timestamp for reference [ 16:28 - 18:44 ]
Summary of reply: At the inner nodes of the associated trees, we store (dummy) keys to guide the search on the y-coordinates, just as we have previously seen in the 1d case. For a visualization see here: zhoujoseph.github.io/Orthogonal-range-tree-visualization/ Longer answer: First lets have a look at the 1D search trees again (see 4:58). We use a balanced binary search tree with the points stored at the leaves. The inner nodes only store information to guide the search. Now in 2d we use the same type of binary search tree on the x-coordinates as primary data structure. Thus, again the inner nodes store information to guide the search on the x-coordinate. Additionally, we store at each node a 1d-range tree of all points that fall into the corresponding x-range, but now this range tree is on the y-coordinates, see 16:45. And now to answer your question: Since these are 1D range trees on the y-coordinates, the inner nodes store information to guide the search in y. Thus for the example in 16:45, we could store a 4 at the root, which tells me that if the y-coordinate I am search for is
The slide starting at 06:11 gives an overview of white/grey/black. Grey is visited but does need to lead to output (but can). We color the nodes on the search paths grey, including the leaves on the search path (as in the example at 05:31). I assume you are asking about the leaf with the 62. This node is not in a right subtree of the left search path (for this the node above it would need to be at least 61). Thus, it is not a black node. Rather, it is on the search path and therefore colored grey. Grey leaves may or may not be part of the output; in this case it is. Does this clarify the coloring?
Note to self: In Fractional cascading we first find the canonical nodes based on x coordinate (in the main tree). Then we only traverse and report the nodes in the auxillary arrays for which the main node is a canonical node i.e., for all the canonical nodes we traverse the auxillary array upto a certain point where y coordinate falls in the range.
Great lecture! I have a question, it's not quite clear what goes in the nodes of the 2D range tree, does it save the associated tree of points in Y coordinates orders ? if so, then what is stored in the nodes of the associated tree?
I'm leaving a timestamp for reference [ 16:28 - 18:44 ]
Summary of reply: At the inner nodes of the associated trees, we store (dummy) keys to guide the search on the y-coordinates, just as we have previously seen in the 1d case. For a visualization see here:
zhoujoseph.github.io/Orthogonal-range-tree-visualization/
Longer answer:
First lets have a look at the 1D search trees again (see 4:58). We use a balanced binary search tree with the points stored at the leaves. The inner nodes only store information to guide the search.
Now in 2d we use the same type of binary search tree on the x-coordinates as primary data structure. Thus, again the inner nodes store information to guide the search on the x-coordinate. Additionally, we store at each node a 1d-range tree of all points that fall into the corresponding x-range, but now this range tree is on the y-coordinates, see 16:45.
And now to answer your question: Since these are 1D range trees on the y-coordinates, the inner nodes store information to guide the search in y. Thus for the example in 16:45, we could store a 4 at the root, which tells me that if the y-coordinate I am search for is
each node stores the subtree with the root as that node and they are ordered using the y-coordinate
Thank you for the wonderful lecture. Well thoughtout & summarised
Do you think the node 62 @ timestamp 14:52 should be black ?
The slide starting at 06:11 gives an overview of white/grey/black. Grey is visited but does need to lead to output (but can). We color the nodes on the search paths grey, including the leaves on the search path (as in the example at 05:31).
I assume you are asking about the leaf with the 62. This node is not in a right subtree of the left search path (for this the node above it would need to be at least 61). Thus, it is not a black node. Rather, it is on the search path and therefore colored grey. Grey leaves may or may not be part of the output; in this case it is.
Does this clarify the coloring?