CODEWITHSUNDEEP
treeinsertbinary-treebinary-search-treequadtree
ezpzzzz
ezpzzzz

Reputation: 23

How can I represent a Quad Tree as a Binary Tree?

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!

Upvotes: 2

Views: 334

Answers (1)

trincot
trincot

Reputation: 349946

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.

Example

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)

Upvotes: 1

Related Questions