Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng "Cơ sở dữ liệu đa phương tiện - Chương 3: Các cấu trúc dữ liệu đa chiều" cung cấp cho người học các kiến thức: k-D trees, cây tứ phân dạng điểm, MX-Quadtrees, R-trees,. nội dung chi tiết. | Bài giảng Cơ sở dữ liệu đa phương tiện: Chương 3 - Nguyễn Thị Oanh Chương 3: Các cấu trúc dữ liệu đa chiều Nguyễn Thị Oanh Bộ môn HTTT – Viện CNTT & TT oanhnt@soict.hut.edu.vn 1 Plan Lưu DL dạng điểm – k-D trees – Point Quadtrees – MX-Quadtrees Lưu DL dạng vùng (chữ nhật): – R-trees 2 1. k-D trees 3 k-D trees Dành lưu trữ dữ liệu điểm đa chiều (k-dimension) – 2-tree: lưu DL điểm 2 chiều – 3-tree: lưu DL điểm 3 chiều – – Mỗi điểm là vector có k phần tử Không lưu DL vùng 4 k-D trees Là mở rộng của cây nhị phân Ở mỗi mức, các bản ghi sẽ được chia theo giá trị của 1 chiều nhất định. – Mức 0: giá trị chiều 0 – Mức 1: giá chị chiều 1, – Mức k-1: giá trị chiều k-1 5 – Mức k: giá trị chiều 0, VD: 2-D trees 6 VD: 3-D trees x y z x Cây được xây dựng phụ thuộc vào thứ tự các điểm được đưa vào 7 2-D trees Cấu trúc 1 nút: INFO XVAL YVAL LLINK RLINK Định nghĩa: 2-d tree là cây nhị phân thỏa mãn: – Nếu nút N ở mức chẵn : M N .LLINK : M . XVAL N . XVAL & P N .RLINK : P. XVAL N . XVAL – Nếu nút N ở mức lẻ: M N .LLINK : M .YVAL N .YVAL & 8 P N .RLINK : P.YVAL N .YVAL 2-D trees Ví dụ: Thứ tự insert: INFO XVAL YVAL Banja Luka 19 45 Derventa 40 50 Toslic 38 38 Tuzla 54 40 Sinji 4 4 9 Insertion/ Search in 2-D trees Nút cần thêm: P(info, x, y) Lặp: – Nút đang duyệt: N – Nếu N.XVAL = x và N.YVAL = y thì ghi đè N và kết thúc – Nếu N ở mức chẵn (0, 2, 4, ): Nếu x < N.XVAL thì duyệt cây bên trái, nếu không duyệt cây con bên phải – Nếu N ở mức lẻ (1, 3, 5, ): Nếu y < N.YVAL thì duyệt cây bên trái, nếu không duyệt cây con bên phải 10 Deletion in 2-D trees T: 2-D tree Nút cần xóa (XVAL, YVAL) = (x, y) Thuật toán: – Tìm N: N.XVAL = x & N.YVAL = y – Nếu N là nút lá: đặt LLINK or RLINK của cha N về NULL và giải phóng N. Kết thúc – Nếu N là nút trong: Tìm nút thay
