Bài giảng Cấu trúc dữ liệu

Các cấu trúc đã học chỉ lưu trữ dữ liệu vô hướng Ta có tập hợp các điểm trong mặt phẳng, không gian 3 chiều Ta cần tìm một điểm -> Xét toàn bộ tập hợp Lúc khác ta lại tìm một điểm khác -> Xét toàn bộCần có một cấu trúc để lưu trữ dữ liệu có hướng như trênGiỚI THIỆUQuá mất thời gian Jon Bentley phát minh vào những năm 1970 KD-TREE viết tắc từ:K-dimenssion tree	KD-TREE Dimenssion: chiều Cây có chiều: k Là cây nhị phân tìm kiếm Dữ liệu lưu trữ: nhiều chiều Mỗi node đi từ gốc đến lá phải có trục là một giá trị (0 n-1). P nằm bên phải của Q(có trục là i) → dữ liệu thứ i của P ≥dữ liệu thứ i của Q12,14,2212,8,165,10,816,0,224,22,104,16,00120QPQuy tắcQUI TẮC:Giống qui tắc insert các cây BST khác.Tại mỗi nút của cây.	So sánh:	 Không so sánh toàn bộ dữ liệu của node.	 Tọa độ thứ i của node với tọa độ thứ i	 của dữ liệu sẽ được thêm vào cây.	  Với i: là axis của node đang xét.INSERT NODE 0 2 4 6 8 101086420(5,4)(4,7)(9,6)(8,1)(2,3)(3,6)(1,1)(7,2)(9,5)INSERT NODE(7,2)(5,4)(4,7)(9,6)(8,1)(2,3)(3,6)(1,1)(9,5)xyxyInsert (9,5), (1,8)(1,8)xINSERT NODETạo Cây(12,14,22)(22,8,16)(5,10,8)(16,0,22)(4,22,10)xyz(4,16,0)0120Danh sách các điểmThêm điểm TH2: Nhánh phải khác rỗng - Tìm min (giả sử là p) - Delete p TH1: Nút cần xóa là nút lá Remove chính nó TH3: Nếu nhánh phải rỗng Thông thường: Tìm max nhánh phải để thay thế -> Có thể phạm qui tắc 2Tìm min (giả sử là p) p và toàn bộ con của p trở thành cây con phải của node đang được delete Delete pQuy tắc: Tìm min nhánh phải để thay thế Tìm Min?DELETE NODE0 2 4 6 8 101086420Trường hợp 1:Delete Nút láDELETE NODE(7,2)(5,4)(4,7)(9,6)(8,1)(2,3)(3,6)(1,1)(9,5)(1,8)xyxyxTrường hợp 1:Delete Nút láBạn có thể xóa ngay không cần kiểm traDELETE NODETìm node có dữ liệu thứ i là bé nhấtGiả sử node đang xét là P Trục của P bằng iMin thuộc left của P.Nếu left rỗng: P là min Trục của P khác i: min có thể làPCon của P (trái hoặc phải)Tìm Min i(3,19,6)(8,17,10)01201(10,17,7)(10,6,1)(9,20,2)(15,7,9)(14,3,9)(14,22,4)(17,6,20)Axis = iAxis  iAxis  iAxis = iMin=1010Bestdist  bỏ qua không duyệt cây con PỨng dụngPhoto Map( bản đồ lượng từ ).Robot.Đồ họa không gian n chiều.Ứng dụng trong lĩnh vực thiên văn học.Ưu điểm: Thuật toán đơn giản dễ tạo.Hạn chế:Không cân bằng.Mất nhiều thời gian xử lý(Nếu có số chiều lớn hơn 10 thì không hiệu quả).