Nhảy đến vị trí phần tử bất kỳ trong cây

[tienlbhoc]

Thấy cái này khó quá, nghĩ mãi không ra, mình muốn hỏi ở cây (nhị phân , tam phân , avl , đỏ đen...) cây gì cũng được , đại thể là có khoảng 1000 phần tử đi, muốn di cư đến phần tử thứ 347 (lẻ cho khó tính), làm thế nào đây .
đừng nói là duyệt tuần tự từ phần tử thứ nhất nhé , làm thế thì còn nói làm gì. Giải pháp thêm cái đánh dấu thứ tự để tra cũng không ổn, vì khi add một phần tử lại phải chỉnh lại toàn bộ thứ tự của các phần tử đứng sau nó .

[bete]

giải pháp thêm cái đánh dấu thứ tự để tra cũng không ổn, vì khi add một phần tử lại phải chỉnh lại toàn bộ thứ tự của các phần tử đứng sau nó

=> phải sửa lại số thứ tự cho O(n) phần tử

Nếu ở mỗi nút mình lưu tổng số con thì khi thêm 1 phần tử phải sửa lại tổng số con cho các nút "cha" => phải sửa lại số thứ tự cho O(h) phần tử (h là độ cao của cây)

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[vukex2079]

Mỗi một cấu trúc dữ liệu nó có mục đích riêng và có cách xử lý khác nhau, vì thế nhiều yêu cầu có thể thực hiện dễ dàng trên cấu trúc này lại rất khó hay không thể thực hiện trên cấu trúc khác. Tùy vào mục đích bạn sử dụng mà lựa chọn cấu trúc cho phù hợp chứ không phải ta chỉ có một kiểu cấu trúc như thế. Như trường hợp của cây, là một kiểu cấu trúc xây dựng để giúp tìm kiếm nhanh, nhưng truy cập trực tiếp chậm và không xác định vị trí, vậy ta ko thể áp dụng tốt thao tác xác định vị trí phần tử đc. Ngược lại, mảng một chiều tìm kiếm không nhanh bằng, chúng ta phải sắp xếp lại và thêm phần tử cũng khó hơn, nhưng nó truy cập rất nhanh, có thể tịnh tiến và có xác định vị trí. Tóm lại là không nên áp dụng thao tác không phù hợp trên cấu trúc dữ liệu vì nó đi trái với mục đích thiết kế.

[tienlbhoc]

Ừ nói đúng 1 vế, thêm xoá chậm hơn , còn tìm kiếm nhị phân mà chậm hơn cây nhị phân thì phải xem lại đó . Hình như 2 cái ngang nhau mà