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.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật assignment 01 - Tree setVietnam National University – HCMCHochiminh University of TechnologyFaculty of Computer Science and EngineeringĐại Học Quốc Gia TP.HCMTrường Đại học Bách KhoaKhoa KH&KT Máy TínhCẤU TRÚC DỮ LIỆU & GIẢI THUẬTASSIGNMENT 02 - Tree set1Giới thiệuTrong 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ậphợ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 gianthự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.2Hiện thựcPhần hiện thực trong bài tập lớn này được tổ chức trong file main.cpp và 2 lớp: AVLNode and TreeSet vàđược chia thành bốn file riêng biệt: AVLNode.h, TreeSet.h, TreeSet.cpp và main.cpp. Cụ thể như sau:2.1AVLNode.hFile 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 :3int key ;// data4AVLNode∗ l e f t ;// left child5AVLNode∗ r i g h t ;// right child6int b a l a n c e ;// balance factor78AVLNode( int key ) {9this−>key = key ;10l e f t = r i g h t = NULL;11balance = 0;12}13AVLNode( int key , int b a l a n c e ) {14this−>key = key ;15this−>b a l a n c e = b a l a n c e ;16l e f t = r i g h t = NULL;17}18 } ;2.2TreeSet.hFile 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ệnthực Java của cấu trúc dữ liệu TreeSet.123456789class 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 https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html11011 public :12TreeSet ( ) ;13~TreeSet ( ) ;14void c l e a r ( ) ;15// print out the set in ascending order16friend os tr ea m& operator