01/10/2018, 09:38
Data structures - Tree
Mọi người cho mình hỏi là trong thực tế, Cây cài bằng mảng có được dùng không?
Tại sao con trỏ hay như vậy là còn cài Tree bằng mảng làm gì, cài bằng con trỏ là được rồi mà?
Giúp mình so sánh 2 loại cài đặt này với ạ. Thanks!
Bài liên quan
Hi Nguyen Trong Dung.
Bạn cần xem ưu nhược của các laoị dữ liệu. Theo mình :
1 Với con trỏ thì có khả năng mở rộng tốt nhưn truy xuất khó.
2 Mảng thì bạn khó mở rộng nhưng truy xuất là ngẫu nhiện.
-> Khi bạn cần duyệt qua tất cả các phần tử của cây thì có lẽ là dùng mảng đơn giản hơn khi chỉ cần for mà không cần các kĩ thuật duyêth cây. Tuy nhiên khả năng mở rộng cây khó hơn vì kích thước mảng là cố định.
Dùng con trỏ sẽ tốn mem nhưng data blob càng lớn thì càng nên dùng cây vì thêm 2 con trỏ không có bao nhiêu trong khi mảng thì quá tù.
Thực tế người ta kết hợp cả con trỏ và mảng (như B-Tree/B+Tree trên đĩa cứng) chứ không dùng mảng không vì sửa mảng rất cực.
Thanks 2 bạn