Quadtree nén (Compressed Quadtrees)
Khi lưu trữ mọi nút tương ứng với ô đã phân chia, chúng ta có thể lưu trữ nhiều nút rỗng. Giảm kích thước cây thưa (sparse trees) này có thể bằng cách chỉ lưu trữ các cây con mà lá có dữ liệu thú vị (tức là "cây con quan trọng"). Chúng ta thực sự có thể giảm kích thước còn hơn nữa. Khi chỉ xét các cây con quan trọng, quá trình cắt tỉa (pruning) có thể tránh các đường dẫn dài trong cây nơi các nút trung gian có bậc hai (một liên kết cha, một liên kết con). Rốt cục, ta chỉ cần lưu nút U ở đầu đường dẫn này (và gắn siêu dữ liệu để biểu diễn các nút đã xóa) và gắn cây con gốc tại cuối nó vào U. Các cây nén này vẫn có chiều cao tuyến tính khi cho đầu vào "xấu" (bad input points).
Mặc dù chúng ta cắt bỏ nhiều phần của cây khi nén, vẫn có thể đạt thời gian chèn, xóa, tìm kiếm logarit bằng cách tận dụng đường cong Z-order (Z-order curves). Đường cong Z-order chuyển đổi mỗi ô của quadtree đầy đủ (do đó cả quadtree nén) trong thời gian O(1) thành đường 1 chiều (và chuyển ngược lại trong O(1)), tạo ra thứ tự toàn phần trên các phần tử. Bây giờ, ta có thể lưu quadtree trong cấu trúc dữ liệu cho tập hợp có thứ tự (ordered set) (trong đó lưu các nút của cây). Ta phải nêu giả định hợp lý trước khi tiếp tục: giả định cho hai số thực α, β ∈ [0,1] dưới dạng nhị phân, ta có thể tính trong O(1) chỉ số bit đầu tiên mà chúng khác nhau. Cũng giả định tính trong O(1) tổ tiên chung nhỏ nhất (lowest common ancestor) của hai điểm/ô trong quadtree và xác định thứ tự Z-order tương đối của chúng, và tính hàm floor trong O(1). Với các giả định này, định vị điểm (point location) cho điểm Q (tìm ô chứa Q), xóa và chèn đều có thể thực hiện trong O(log n) thời gian (tức thời gian tìm kiếm trong cấu trúc tập hợp có thứ tự cơ sở).
Để thực hiện định vị điểm cho Q (xác định ô của nó trong cây nén):
- Tìm ô hiện có trong cây nén đứng trước Q theo thứ tự Z-order. Gọi ô đó là V.
- Nếu Q ∈ V, trả về V.
- Ngược lại, tìm tổ tiên chung nhỏ nhất của điểm Q và ô V trong quadtree không nén. Gọi ô tổ tiên đó là U.
- Tìm ô hiện có trong cây nén đứng trước U theo thứ tự Z-order và trả về nó.
Không đi vào chi tiết cụ thể, để chèn/xóa ta trước tiên định vị điểm cho đối tượng muốn chèn/xóa, sau đó chèn/xóa. Cần cẩn thận định hình lại cây phù hợp, tạo và xóa nút khi cần.
Octree
Octree được định nghĩa là cấu trúc dữ liệu cây mà mỗi nút nội bộ có đúng tám nút con.
Octree thường được dùng để phân vùng không gian 3 chiều bằng cách chia đệ quy nó thành tám phần tám (octants).
Octree là đối ứng 3 chiều của quadtree. Tên được tạo từ "oct" + "tree", nhưng lưu ý thường viết "octree" với chỉ một "t".
Octree thường dùng trong đồ họa 3D và engine game 3D.
Để biểu diễn không gian
Mỗi nút trong octree chịu trách nhiệm phân vùng không gian nó biểu diễn thành tám octant. Trong octree vùng điểm (Point Region - PR), nút lưu một điểm 3 chiều tường minh, là "trung tâm" của phân vùng cho nút đó; điểm chỉ định một trong các góc cho mỗi trong tám nút con. Trong octree dựa trên ma trận (Matrix-based - MX), điểm phân vùng ngầm hiểu là trung tâm của không gian mà nút biểu diễn. Nút gốc của PR octree có thể biểu diễn không gian vô hạn; nút gốc của MX octree phải biểu diễn không gian hữu hạn chặn để các trung tâm ngầm định được xác định rõ.
Ứng dụng phổ biến
- Render mức chi tiết (Level of detail) trong đồ họa 3D máy tính.
- Chỉ mục không gian (Spatial indexing).
- Tìm kiếm láng giềng gần nhất (Nearest neighbour search).
- Phát hiện va chạm hiệu quả trong ba chiều.
- Phân tích phần tử hữu hạn (Finite element analysis).
- Sparse voxel octree.
- Ước lượng trạng thái (State estimation).
- Ước lượng tập hợp (Set estimation).