I have been trying to find a good tutorial for KD tree for quite sometime in UA-cam. Honestly, this was the best. If you could also do a follow up video and show the spatial representation of all the nodes and probably show a Nearest Neighbor search, that'll make this tutorial complete :) Thank you! :-)
I wish it included an example in the end where you showed how we could find point within a threshold, as in find the closest points to a target etc. great video though
Great question! In my videos on KD-Trees, I assumed we wouldn't run into any ties to keep things simple, but in the event of a tie, you would want to break the tie in a consistent manner. For example, in your example, you have a tie when comparing the x-dimension, you could break the tie by also looking at the y-dimension. if you have a tie again, you can break it using the z-dimension. If you have ties in all dimensions, you have a duplicate element, which you don't want to insert
I do wonder what the advantage would be of a kd tree versus a regular binary tree or some other data structure. It would take (roughly) the same number of operations to find an element since there are also two nodes (log base 2 of N). It doesn't look like you would necessarily achieve a better distribution of the data such that each branch would have the same number of levels. I fail to see why I would ever favour a kd tree over a binary tree.
@@UwUAroze That does indeed matter; great insight! 😄 Much like how, with a BST, you typically want to optimize the insertion order in some way to make the tree well-balanced, the same logic applies for K-D Trees. There are algorithms for building well-balanced K-D Trees from a given dataset; see here: en.wikipedia.org/wiki/K-d_tree#Construction
@@niemasd oh so it matters from a standpoint of optimising the nns search/etc, but regardless of order it would be able to do the search with the correct answer?
I have been trying to find a good tutorial for KD tree for quite sometime in UA-cam. Honestly, this was the best. If you could also do a follow up video and show the spatial representation of all the nodes and probably show a Nearest Neighbor search, that'll make this tutorial complete :) Thank you! :-)
The most helpful tutorial on K-D trees I have found so far
Nuevo seguidor, muy buen tutorial, ni los tutoriales en mi idioma los entendi tan bien como este👋
I was looking for a good tutorial for this kind of tree, i will use it in my final thesis, so, thanks from Chile!
I wish it included an example in the end where you showed how we could find point within a threshold, as in find the closest points to a target etc. great video though
Good examples
simplest tutorial on Kd trees I have come across.....
Explanation so good🤩🤩🤩🤩🤩🤩
Very clear explanation, thank you.
top-notch tutrial!
in the 3D example, what if we try to insert (10, 9, 8)? will the algorithm do nothing because of the duplicate element?
Great question! In my videos on KD-Trees, I assumed we wouldn't run into any ties to keep things simple, but in the event of a tie, you would want to break the tie in a consistent manner. For example, in your example, you have a tie when comparing the x-dimension, you could break the tie by also looking at the y-dimension. if you have a tie again, you can break it using the z-dimension. If you have ties in all dimensions, you have a duplicate element, which you don't want to insert
my college teacher made this seem like theory of relatively. but you, ..thanks vro.
hahaha same here :3
what to do if the numbers are same example: (19,34) and (19,45)
Ties can be broken arbitrarily
Thanku sir
I do wonder what the advantage would be of a kd tree versus a regular binary tree or some other data structure. It would take (roughly) the same number of operations to find an element since there are also two nodes (log base 2 of N). It doesn't look like you would necessarily achieve a better distribution of the data such that each branch would have the same number of levels. I fail to see why I would ever favour a kd tree over a binary tree.
K-D trees are more useful for representing high-dimensional data and answering questions like "what are the closest points to this query?"
if you look at your points in a different order, you'll have a different looking tree. does that matter..?
@@UwUAroze That does indeed matter; great insight! 😄 Much like how, with a BST, you typically want to optimize the insertion order in some way to make the tree well-balanced, the same logic applies for K-D Trees. There are algorithms for building well-balanced K-D Trees from a given dataset; see here: en.wikipedia.org/wiki/K-d_tree#Construction
@@niemasd oh so it matters from a standpoint of optimising the nns search/etc, but regardless of order it would be able to do the search with the correct answer?
very helpful, thank you.
What if its equal?
lol I found out that this is no longer on the cse100 requirement :(
Thanks :)
I have an exam in 13 minutes.
jai siya ram
Nós não conseguimos em portugues