tailieunhanh - Thuật toán phân rã lớp thông tin có cấu trúc dạng cây tam nguyên N-chiều với thông tin chứa ở lá trên tập khóa vô hạn

Trong bài báo này đưa ra cấu trúc cây tam nguyên n-chiều với thông tin chứa ở lá cùng với hàm kết quả, các quy tắc dẫn xuất, hệ tiên đề, các hiệu quả, các định lý và đặc biệt là thuật toán phân rã lớp các thông tin có cấu trúc dạng cây tam nguyên n-chiều trên cơ sở hai thuật toán: thuật toán chuyền cây tam nguyên n-chiều về cây chuẩn tắc tương đương và thuật toán chuyền về cây tam nguyên n-chiều tối ưu nhằm mục đích giảm thời gian xây dựng cây tam nguyên n-chiều tối ưu khi tập khóa rất lớn. Điều đặc biệt là khi áp dụng hệ thống lý thuyết này với trường hợp n=1 ta thu được kết quả cho cây tam nguyên một chiều. | THUẬT TOÁN PHÂN RÃ LỚP THÔNG TIN CÓ CẤU TRÚC DẠNG CÂY TAM NGUYÊN N-CHIÈU VỚỊ THÔNG TIN CHỨA Ỏ LÁ TRÊN TẬP KHÓA VÔ HẠN Đỗ Đức Giáo Phạm Ngọc Hùng Trịnh Đình Vinh Khoa Công nghệ - Đợi học Quốc gia Hà Nội ỉn the save information process under the binary search trees form it is put forward which standard to appreciate and set up again information under the optimal binary search trees form and construction code table to saved information in that trees optimums. One of the methods is always used to set up information again and it is saved under the binary search trees form . It s axiom method by H. Thiele in I . In this paper we will prove the theorem which says that every n-dimentional ternary search tree can be uniquely transformed into a optimal n-dỉmentìonaỉ ternary search tree by using descomposition algorithms for the infinite set of n-dimentional keys. 1. ĐẬT VÁN ĐÈ Trong quá trình lưu trữ các thông tin dưới dạng cây nhị phân người ta thương đưa ra một tiêu chuẩn nào đó để đánh giá vả tổ chức lại các thông tin dưới dạng cây tìm kiếm tối ưu và xây dựng bảng mã cho các thông tin được lưu trữ trong cây tối ưu đó. Một trong những phương pháp hay dùng đê tô chức lại các thông tin và lưu trữ nó dưới dạng cây nhị phân là phương pháp tiên đề do nêu ra trong 1 . Từ kết quả đó của người ta đã xây dựng các thuật toán tương đương và thuật toán tìm cây tối ưu dựa trên việc xét duyệt các khóa của cây đã cho. Trong bài báo này chúng tôi đưa ra cấu trúc cây tam nguyên n-chiều với thông tin chứa ở lá cùng với hàm kết quả các quy tẳc dẫn xuất hệ tiên đề các hệ quả các định lý và đặc biệt là thuật toán phân rã lớp các thông tin có cấu trúc dạng cây tam nguyên n-chiều trên cơ sở hai thuật toán thuật toán chuyển cây tam nguyên n-chiều về cây chuẩn tắc tương đương và thuật toán chuyền về cây tam nguyên n-chiều tối ưu nhàm mục đích giảm thời gian xây dựng cây tam nguyên n-chiều tối ưu khi tập khóa rất lớn. Điểu đặc biệt là khi áp dụng hệ thống lý thuyết này với trường