有几种构建四叉树的方法。如果你采取一个像素矩阵,或任何单位,并做出一个四叉树,那么它的高度将是log(n)。
但是,如果你使用它存储一个接一个地添加的点(类似于BST),那么如果所有的点都根据一个组件进行排序,那么你将会遇到最坏的情况。在这种情况下,树的高度为n。
这种情况的一个例子如下:
- 从空的四叉树开始
- 插入(0,0)
- 插入(1,1)
- 插入(2,2)
- 插入(3,3)
- ...
- 插入(n-1,n-1)
每次插入节点时,进入先前插入的节点的右上角,因此每个节点只有一个孩子。你最后得到的只是长度为n的奇怪的链表。
所以,这一切都取决于你如何构建四叉树,而没有一个独特的方案要做到这一点。这就是为什么操作的最糟糕的复杂性,如 insert 或搜索 O(n)。
As I read from sources,I learnt that worst case complexity of Quad tree is O(N) when the 2D matrix has only one dimension.I am not able to understand the reason for this. For eg. When matrix is just 1xm,we'll keep dividing it into two halves and will reach unit cell in log(m) stops.So complexity should be log(m) THANKS
解决方案There are several ways of building a quad tree. If you take a matrix of pixels, or whatever units and make a quadtree out of it, then indeed it's height will be log(n).
However, if you use it to store points (kind of like a BST) that you add one after the other, then you'll hit the worst-case scenario if all of your points are sorted according to one components. In this case, height of the tree will be n.
An example of such a case is the following:
- Start with an empty quad tree
- Insert (0,0)
- Insert (1,1)
- Insert (2,2)
- Insert (3,3)
- ...
- Insert (n-1,n-1)
Each time you insert a node, it goes into the upper right corner of the previously inserted node, so each node has exactly one child. What you get at the end is just a weird linked list of length n.
So, it all depends of how you build your quadtree, and there is not a unique scheme to do that. That's why the worst-case complexity for operations like insert or search O(n).
更多推荐
四叉树O(N)的最坏情况如何复杂?
发布评论