tailieunhanh - Cấu trúc dữ liệu và giải thuật assignment 01 - Tree set

Trong bài tập lớn này sinh viên sẽ hiện thực cấu trúc dữ liệu tập hợp TreeSet1 . Cụ thể, cấu trúc dữ liệu tập hợp này sẽ được hiện thực dựa trên cây AVL đã được học trên lớp. Việc hiện thực này phải đảm bảo thời gian thực thi trong trường hợp xấu nhất (worst case) là log(n) cho các phép toán cơ bản như thêm phần từ (add), xóa phần tử (remove), và các phép toán tìm kiếm. Ở bài tập lớn này, dữ liệu kiểm tra sẽ có kích thước rất lớn, do đó, sinh viên cần lưu ý tối ưu hóa mã nguồn để đảm bảo thời gian thực thi. | Vietnam National University – HCMC Hochiminh University of Technology Faculty of Computer Science and Engineering Đại Học Quốc Gia Trường Đại học Bách Khoa Khoa KH&KT Máy Tính CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ASSIGNMENT 02 - Tree set 1 Giới thiệu Trong bài tập lớn này sinh viên sẽ hiện thực cấu trúc dữ liệu tập hợp TreeSet1 . Cụ thể, cấu trúc dữ liệu tập hợp này sẽ được hiện thực dựa trên cây AVL đã được học trên lớp. Việc hiện thực này phải đảm bảo thời gian thực thi trong trường hợp xấu nhất (worst case) là log(n) cho các phép toán cơ bản như thêm phần từ (add), xóa phần tử (remove), và các phép toán tìm kiếm. Ở bài tập lớn này, dữ liệu kiểm tra sẽ có kích thước rất lớn, do đó, sinh viên cần lưu ý tối ưu hóa mã nguồn để đảm bảo thời gian thực thi. 2 Hiện thực Phần hiện thực trong bài tập lớn này được tổ chức trong file và 2 lớp: AVLNode and TreeSet và được chia thành bốn file riêng biệt: , , và . Cụ thể như sau: File này chứa phần khai báo và định nghĩa cấu trúc dữ liệu AVLNode để hiện thực cấu trúc dữ liệu cây AVL. 1 class AVLNode { 2 public : 3 int key ; // data 4 AVLNode∗ l e f t ; // left child 5 AVLNode∗ r i g h t ; // right child 6 int b a l a n c e ; // balance factor 7 8 AVLNode( int key ) { 9 this−>key = key ; 10 l e f t = r i g h t = NULL; 11 balance = 0; 12 } 13 AVLNode( int key , int b a l a n c e ) { 14 this−>key = key ; 15 this−>b a l a n c e = b a l a n c e ; 16 l e f t = r i g h t = NULL; 17 } 18 } ; File này chứa phần khai báo các hàm (method) cho lớp TreeSet. Phần prototype của lớp này là dựa trên hiện thực Java của cấu trúc dữ liệu TreeSet. 1 2 3 4 5 6 7 8 9 class T r e e S e t { private : AVLNode ∗ r o o t ; int count ; protected : void c l e a r R e c (AVLNode∗ r o o t ) ; 1 1 10 11 public : 12 TreeSet ( ) ; 13 ~TreeSet ( ) ; 14 void c l e a r ( ) ; 15 // print out the set in .