As stated in the title, how can I represent a quad-tree as a binary tree? I know that it is possible to represent general trees as binary trees but I wasn't able to wrap my head around binary tree representation of quad-tree. I'm actually looking for more of an explanation or a visual than a code snippet.
e.g, I want to insert these elements: (30,30), (20,15), (50,40).
Thanks in advance!
The binary tree equivalent would be a k-d tree with k=2
A node in a (point) quad-tree divides the plane into four quadrants, by splitting the plane by the horizontal and vertical lines that run through the point represented by the node.
In a corresponding k-d tree you would divide the plane only in two halves, based on the horizontal or vertical line. Which one to use is defined by the depth of the node: at even depths, the horizontal line is used, at odd depths, the vertical line is used. So when a node gets two children by a horizontal split, and those children also get two children each, by a vertical split, we get the same split as in the quad-tree, but needing 2 levels in the tree instead of just one.
You provided as example the input (30,30), (20,15), (50,40), but let's add a few more points, to be inserted in this order:
(30,30), (20,15), (50,40), (25,45), (60,10), (55,25)
In a point quad-tree you would get this -- labels are directions (North West, ...etc):
____________(30,30)_________
/ / \ \
SW/ SE/ NW\ NE\
/ / \ \
(20,15) ___(60,10)____ (25,45) (50,40)
/ | | \
SW/ SE| |NW \NE
/ | | \
null null (55,25) null
In a k-d tree it could be like this:
__(30,30)___
/ \
S/ N\
/ \
(20,15) (50,40)
/ \ / \
E/ W\ E/ W\
/ \ / \
null (60,10) (25,45) null
/ \
S/ N\
/ \
null (55,25)