当前课程知识点:计算几何 > 08. Windowing Query > H. Priority Search Tree > 08-H-03. Sibling Partitioning
你可能已经注意到了
我们刚才这种构造堆的方法
其实是非常自由自在的
难道不是吗
对于无论是全集
还是任何一个需要构造
一个子堆的一个子集
我们都可以或者说
必须找到其中最高的那个点
把它作为或者
指定为堆顶就够了
而至于接下来
它的后代的组织是非常自由的
这种后代的组织
在同一层与下一层之间
表现为就是它的左和右孩子
或者叫左后代和右后代的划分
我们刚才没有做任何的限定
其实我们刚才也说过
你可以任意地来划分
无论左右数量是多少
无论他们的高低相差有多少
无论如何你都是自由的
同时 我们又从另一个方面注意到
我们的输入也就是那个点集中
所有的点的某些信息
我们至今又没有利用到
哪些信息呢
对 就是它的y坐标
或者说在这里来讲
就是它横向的那个信息
我们没有利用到
压根就没有利用到
好 注意到这样一个需求
也注意到这样一个条件
我们不妨将这两个东西合起来
我们不妨就利用y坐标
来作为在处处划分左右孩子
左右后代的这样的一个依据
确切的讲我们需要使得
在任何一个位置处
比如说它这个位置处
使得它的所有的左后代
从y坐标也就是
我们这里的左右关系来看
都要严格的小于它的右后代
或者简而言之
对于任何一个结点而言
它的左后代和右后代
都必须是能够
经过一条竖直的线切分之后
左和右经位分明的
能够严格的分出来左和右
也就是一般的习惯左后代都靠左
右后代都靠右 好
这就是我们划分的第一个依据
当然你也可以想象到
我们将来跟所有的东西一样
要去做搜索而搜索里头
最最重要的一个指标就是深度
在数据规模固定的情况下
你应该已经有这个常识
我们每一次划分
越是均匀越好
因为这样的话
可以使得在同样的条件下
整个这个结构的高度
或者叫搜索的深度
会达到最小 最平衡
好 所有这东西想通了以后
那就很自然的可以理解
为什么我们在这里会采用中位数
也就是说对于任何的一个节点
我们这里都需要对它的后代
去切分成严格的左边的一部分
和右边的一部分各自一半
而采用median
是很直接也是最有效的方法
好了 经过了
这样的一个补充的说明
我们已经不难理解
我们不仅可以
将任何一个平面上的点集
表示编码为一个堆
而且这个编码的形式
从刚才的那个意义上讲
会导致唯一的确定的一个结果
这样一个由平面点集
直接导出的唯一的结构
从数据结构的意义上讲
就是我们这里所谓的
priority search tree
概括一下
所谓的PST就是利用x坐标
也就是我们这里所说的高度
来维护这个堆的order property
同时用正交的那个y坐标
通过所有的y median
来进行左和右后代的均匀划分
在这样一棵PST中
既然所有的左后代
都严格的位于右后代的左侧
所以相应地来说
所有左后代的y坐标
也自然不会超过
任何右后代的y坐标
所以在y坐标上
它们必然是这样左右顺序的
有一点需要强调的是
刚才的这样
对于x坐标和y坐标的
使用方法和约定是不能颠倒的
比如 刚才我们虽然讲过
祖先的x坐标必然会小于后代
但是在y坐标上看
却未必如此
比如我们来看一下
就这个例子
这是一个故意要画成
这样的一个例子
我们注意到这里的根
或者说祖先是零
可是它的孩子呢
无论是1还是2
从y坐标也就是左右来看
都位于它的左侧
确认一下 都位于它的左侧
我们看到
既然两个孩子都为同侧
那么在y方向上
就不能出现一左一右
也就是我们刚才
说的顺序的那种情况
所以强调要你记住的一条
就是我们的y坐标那个顺序性
实际上是对于左右后代而言的
在代际之间
只能通过x进行比较
而不能用y
这两件事是本身不矛盾的
但是你不要贸然的把它们弄混了
-Before we start
--html
-Evaluation
--html
-Online Judge
--html
-Lecture notes
--html
-Discussion
--html
-A. History of This Course
--00-A. History of This Course
-B. What's Computational Geometry
--00-B. What's Computational Geometry
-B. What's Computational Geometry--作业
-C. How to Learn CG Better
--00-C. How to Learn CG Better
-C. How to Learn CG Better--作业
-D. Why English
-A. Convexity
-A. Convexity--作业
-B. Extreme Points
-B. Extreme Points--作业
-C. Extreme Edges
-C. Extreme Edges--作业
-D. Incremental Construction
--01-D-01. Decrease and Conquer
--01-D-02. In-Convex-Polygon Test
--01-D-03. Why Not Binary Search
-D. Incremental Construction--作业
-E. Jarvis March
--01-E-06. Lowest-Then-Leftmost
-E. Jarvis March--作业
-F. Lower Bound
--01-F-02. CAO Chong's Methodology
-F. Lower Bound--作业
-G. Graham Scan: Algorithm
-G. Graham Scan: Algorithm--作业
-H. Graham Scan: Example
-H. Graham Scan: Example--作业
-I. Graham Scan: Correctness
-I. Graham Scan: Correctness--作业
-J. Graham Scan: Analysis
-J. Graham Scan: Analysis--作业
-K. Divide-And-Conquer (1)
-K. Divide-And-Conquer (1)--作业
-L. Divide-And-Conquer (2)
--01-L-03. Topmost + Bottommost ?
--01-L-07. More Considerations
-L. Divide-And-Conquer (2)--作业
-M. Wrap-Up
-0. Introduction
-0. Introduction--作业
-A. Preliminary
-A. Preliminary--作业
-B. Interval Intersection Detection
-B. Interval Intersection Detection--作业
-C. Segment Intersection Reporting
-C. Segment Intersection Reporting--作业
-D. BO Algorithm: Strategy
--02-D-01. Proximity & Separability
--02-D-02. Comparability & Ordering
-D. BO Algorithm: Strategy--作业
-E. BO Algorithm: Implementation
--02-E-03. Events & Operations
-E. BO Algorithm: Implementation--作业
-F. BO Algorithm: Analysis
--02-F-04. Complexity of Event Queue
--02-F-05. Complexity of Status Structure
-F. BO Algorithm: Analysis--作业
-G. Convex Polygon Intersection Detection
--02-G-01. Problem Specification
--02-G-02. Monotone Partitioning
--02-G-04. Decrease-And-Conquer
-G. Convex Polygon Intersection Detection--作业
-H. Edge Chasing
--02-H-01. Eliminating Sickles
-H. Edge Chasing--作业
-I. Plane Sweeping
-I. Plane Sweeping--作业
-J. Halfplane Intersection Construction
-J. Halfplane Intersection Construction--作业
-0. Methodology
-0. Methodology--作业
-A. Art Gallery Problem
--03-A-02. Lower & Upper Bounds
--03-A-04. Approximation & Classification
-A. Art Gallery Problem--作业
-B. Art Gallery Theorem
--03-B-01. Necessity of floor(n/3)
--03-B-02. Sufficiency by Fan Decomposition
-B. Art Gallery Theorem--作业
-C. Fisk's Proof
--03-C-04. Pigeon-Hole Principle
-C. Fisk's Proof--作业
-D. Orthogonal Polygons
--03-D-01. Necessity of floor(n/4)
--03-D-02. Sufficiency by Convex Quadrilateralization
-D. Orthogonal Polygons--作业
-E. Triangulation
-E. Triangulation--作业
-F. Triangulating Monotone Polygons
--03-F-02. Monotonicity Testing
--03-F-04. Stack-Chain Consistency
-F. Triangulating Monotone Polygons--作业
-G. Monotone Decomposition
-G. Monotone Decomposition--作业
-I. Tetrahedralization
--03-I-01. Polyhedron Decomposition
--03-I-02. Schonhardt's Polyhedron
-I. Tetrahedralization--作业
-A. Introduction
--04-A-02. Dining Halls on Campus
--04-A-03. More Analogies & Applications
-A. Introduction--作业
-B. Terminologies
--04-B-02. Intersecting Halfspaces
--04-B-04. Planar Voronoi Diagram
-B. Terminologies--作业
-C. Properties
--04-C-03. Nearest = Concyclic
--04-C-04. Number of Nearest Sites = Degree
-C. Properties--作业
-D. Complexity
-D. Complexity--作业
-E. Representation
-E. Representation--作业
-F. DCEL
-F. DCEL--作业
-G. Hardness
--04-G-03. Voronoi Diagram In General Position
-G. Hardness--作业
-H. Sorted Sets
--04-H-01. Convex Hull Made Easier
--04-H-02. Convex Hull As A Combinatorial Structure
--04-H-03. Voronoi Diagram As A Geometric Structure
-H. Sorted Sets--作业
-I. VD_sorted
--04-I-06. Sorting Not Made Easier
-I. VD_sorted--作业
-J. Naive Construction
-J. Naive Construction--作业
-K. Incremental Construction
-K. Incremental Construction--作业
-L. Divide-And-Conquer
--04-L-09. Intersecting with Cells
-L. Divide-And-Conquer--作业
-M. Plane-Sweep
--04-M-09. Circle Event: What, When & Where
-M. Plane-Sweep--作业
-A. Point Set Triangulation
-A. Point Set Triangulation--作业
-B. Delaunay Triangulation
-B. Delaunay Triangulation--作业
-C. Properties
-C. Properties--作业
-D. Proximity Graph
--05-D-02. Relative Neighborhood Graph
-D. Proximity Graph--作业
-E. Euclidean Minimum Spanning Tree
-E. Euclidean Minimum Spanning Tree--作业
-F. Euclidean Traveling Salesman Problem
-G. Minimum Weighted Triangulation
-G. Minimum Weighted Triangulation--作业
-H. Construction
--05-H-03. Maximizing The Minimum Angle
--05-H-04. Evolution By Edge Flipping
-H. Construction--作业
-I. RIC With Example
-I. RIC With Example--作业
-J. Randomized Incremental Construction
--05-J-01. Recursive Implementation
--05-J-02. Iterative Implementation
-J. Randomized Incremental Construction--作业
-K. RIC Analysis
--05-K-04. Types Of Edge Change
--05-K-05. Number Of Edge Changes
--05-K-07. Number Of Rebucketings
--05-K-08. Probability For Rebucketing
--05-K-10. Further Consideration
-0. Online/Offline Algorithms
--06-0. Online/Offline Algorithms
-0. Online/Offline Algorithms--作业
-A. Introduction
--06-A-03. Assumptions For Clarity
--06-A-05. Performance Measurements
-A. Introduction--作业
-B. Slab Method
--06-B-02. Ordering Trapezoids
-B. Slab Method--作业
-C. Persistence
--06-C-01. Ephemeral Structure
--06-C-02. Persistent Structure
-C. Persistence--作业
-D. Path Copying
--06-D-03. Storage Optimization
-D. Path Copying--作业
-E. Node Copying
-E. Node Copying--作业
-F. Limited Node Copying
-G. Kirkpatrick Structure
--06-G-01. Optimal And Simpler
--06-G-06. The More The Better
--06-G-07. The Fewer The Better
--06-G-09. Existence Of Independent Subset
--06-G-10. Construction Of Independent Subset
-G. Kirkpatrick Structure--作业
-H. Trapezoidal Map
--06-H-03. Properties & Complexity
--06-H-04. Search Structure: Example
--06-H-05. Search Structure: Nodes
--06-H-06. Search Structure: Performance
-H. Trapezoidal Map--作业
-I. Constructing Trapezoidal Map
--06-I-04. Case 1: Two Endpoints
--06-I-05. Case 2: One Endpoint
--06-I-06. Case 3: No Endpoints
-J. Performance Of Trapezoidal Map
--06-J-03. Number Of Ray Trimmed
--06-J-04. Number Of Trapezoidals Created (1)
--06-J-05. Number Of Trapezoidals Created (2)
--06-J-06. Time For Point Location
--06-J-07. Size Of Search Structure
--06-J-08. Fixed Query Point + Randomly Created Maps
--06-J-10. Probability Of Enclosing Trapezoid Changed
-A. Range Query
--07-A-01. 1-Dimensional Range Query
-A. Range Query--作业
-B. BBST
--07-B-02. Lowest Common Ancestor
-B. BBST--作业
-C. kd-Tree: Structure
-C. kd-Tree: Structure--作业
-D. kd-Tree: Algorithm
-D. kd-Tree: Algorithm--作业
-E. kd-Tree: Performance
--07-E-01. Preprocessing Time + Storage
-E. kd-Tree: Performance--作业
-F. Range Tree: Structure
--07-F-03. x-Query * y-Queries
-F. Range Tree: Structure--作业
-G. Range Tree: Query
-G. Range Tree: Query--作业
-H. Range Tree: Performance
-H. Range Tree: Performance--作业
-I. Range Tree: Optimization
--07-I-04. Fractional Cascading
-A. Orthogonal Windowing Query
-A. Orthogonal Windowing Query--作业
-B. Stabbing Query
-C. Interval Tree: Construction
-C. Interval Tree: Construction--作业
-D. Interval Tree: Query
-D. Interval Tree: Query--作业
-E. Stabbing With A Segment
--08-E-03. Query Algorithm (1)
--08-E-04. Query Algorithm (2)
-F. Grounded Range Query
--08-F-03. 1D-GRQ Using Range Tree
--08-F-04. 1D-GRQ By Linear Scan
-G. 1D-GRQ Using Heap
-G. 1D-GRQ Using Heap--作业
-H. Priority Search Tree
--08-H-03. Sibling Partitioning
-H. Priority Search Tree--作业
-I. 2D-GRQ Using PST
-I. 2D-GRQ Using PST--作业
-J. Segment Tree
--08-J-01. General Windowing Query
--08-J-02. Elementary Interval
--08-J-06. Solving Stabbing Query
--08-J-11. Constructing A Segment Tree
--08-J-12. Inserting A Segment (1)
--08-J-13. Inserting A Segment (2)
--08-J-14. Inserting A Segment (3)
-K. Vertical Segment Stabbing Query