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ên
Quá 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

 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 Q
Q
P
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.

0 2 4 6 8 10
10
8
6
4
2
0
(5,4)
(4,7)
(9,6)
(8,1)
(2,3)
(3,6)
(1,1)
(7,2)
(9,5)
(7,2)
(5,4)
(4,7)
(9,6)
(8,1)
(2,3)
(3,6)
(1,1)
(9,5)
Insert (9,5), (1,8)
(1,8)
(12,14,22)
(22,8,16)
(5,10,8)
(16,0,22)
(4,22,10)
(4,16,0)
0
1
2
0
Danh sách các điểm
Thê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 2
Tì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 p
Quy tắc: Tìm min nhánh phải để thay thế
Tìm Min
?
0 2 4 6 8 10
10
8
6
4
2
0
(7,2)
(5,4)
(4,7)
(9,6)
(8,1)
(2,3)
(3,6)
(1,1)
(9,5)
(1,8)
x
y
x
y
x
Bạn có thể xóa ngay không cần kiểm tra
Tìm node có dữ liệu thứ i là bé nhất
Giả sử node đang xét là P
Trục của P bằng i
Min 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à
P
Con của P (trái hoặc phải)
(3,19,6)
Axis = i
Axis  i
Axis  i
Axis = i
Min=10
10<14
Min=3
3<8<10
Min=(3,9,6)
Ví dụ: Findmin(0)
i=0
Axis  i
Axis = i
3<9
3<10
0 2 4 6 8 10
10
8
6
4
2
0
(7,2)
(5,4)
(4,7)
(9,6)
(8,1)
(2,3)
(3,6)
(1,1)
(9,5)
(1,8)
x
y
x
y
x
(1,8)
B1:tìm min trên nhánh con phải đẻ thay thế.
B2: thay thế giá trị vừa tim được vào nút cần xóa
B3: xóa nút
0 2 4 6 8 10
10
8
6
4
2
0
(7,2)
(5,4)
(9,6)
(8,1)
(2,3)
(1,1)
(9,5)
x
y
x
y
x
(3,2)
(1,2)
(1,1)
(1,1)
(1,2)
(1,2)
Left.Findmin(1)
(7,2)
(5,4)
(4,7)
(9,6)
(8,1)
(2,3)
(3,6)
(1,1)
(9,5)
(1,8)
x
y
x
y
x
(1,8)
(7,2)
(9,6)
(8,1)
(2,3)
(3,6)
(1,1)
(9,5)
x
y
x
y
(1,1)
0 2 4 6 8 10
10
8
6
4
2
0
Input: điểm Q
Output: Tập các điễm gần Q nhất
Duyệt toàn bộ cây: tại mỗi node tính khoảng cách giữa P&Q chọn ra các điểm có khoảng cách gần nhất
Nếu số chiều & số node lớn thì sẽ rất chậm
Cải tiến:
Nếu: d>Bestdist  bỏ qua không duyệt cây con P

Ứng dụng
Photo 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ả).