Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo tài liệu 'multibooks - tổng hợp it - pc part 12', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 5. Hình 2.18 chỉ ra cách làm không đúng khi chèn chữ nhật R11. Tiếp cận này không khả thi vì nút biểu diễn nhóm chứa chữ nhật R11 có thể là chỉ chứa duy Error nhất một chữ nhật. 2.5.2 Xoá trong cây R-Trees Việc xóa các đối tượng từ cây R-Trees có thể gây ra một nút trong cây R-Tree trở nên thiếu hụt underflow . Nhắc lại rằng một R-Tree bậc k phải bao gồm ít nhất K 2 hình chữ nhật trong nó. Khi chúng ta xoá một hình chữ nhật từ một R-Tree chúng ta phải đảm bảo rằng nút đó không bị thiếu hụt. Ví dụ xem xét R-Trees như hình 2.15 trình bày trên. Giả thiết chúng ta muốn xoá chữ nhật R9. Nút chứa R9 chỉ còn lại một nút trong nó nếu thực hiện xoá R9 kết quả là nút này sẽ phản ánh một điều kiện hụt. Trong trường hợp này chúng ta phải tạo ra nhóm logic mới. Một khả năng là sắp xếp lại các nhóm như sau Group Rectangles G1 R1 R2 R3 G2 R4 R6 R7 G3 R5 R8 Cây R mới là kết quả của việc xóa nút R9 nó được thể hiện trên hình 2.19. Error 2.6 So sánh các cấu trúc dữ liệu Trong chương này ta đã khảo sát 4 loại cấu trúc dữ liệu cây k-d cây tứ phân điểm cây tứ phân MX và cây R. Mỗi chúng đều có ưu điểm và nhược điểm nhất định. Cây tứ phân điểm rất dễ cài đặt. Tuy nhiên cây tứ phân điểm có k nút thì có thể có độ cao là k như vậy làm tăng độ phức tạp cho chèn và tìm kiếm nó có thể là O k . Hơn nữa mỗi so sánh đòi hỏi so sánh hai tọa độ.Việc xóa nút trong cây loại này là khá khó khăn. vì việc tìm kiếm nút ứng viên thay thế cho nút đang xóa thông thường là không đơn giản. Cuối cùng truy vấn khoảng trong cây này cần O 2Ön n là tổng số bản ghi trong cây. Cây k-d rất dễ cài đặt. Tuy nhiên cây k-d chứa k nút có thể có độ cao k do vậy chèn và tìm kiếm có thể phức tạp. Trong thực tế đường dẫn từ gốc tới lá của cây loại này dài hơn trong cây tứ phân điểm bởi vì cây này là cây nhị phân. Độ phức tạp tồi nhất của tìm kiếm dải trong cây k-d là Error . Khi k 2 thì độ phức tạp còn Error như cây tứ phân điểm. Cây tứ phân MX đảm bảo có độ cao nhất là O n trong đó vùng được biểu diễn có 2nx2n tế bào. Nói .
