tailieunhanh - Tối ưu hóa cây nhị phân một chiều với thông tin chứa ở các đỉnh trong trên tập khóa hữu hạn

Tối ưu hóa cây nhị phân một chiều với thông tin chứa ở các đỉnh trong trên tập khóa hữu hạn Sơ đồ phân bố ứng suất kiến tạo khu vực thềm lục địa đông nam Việt Nam tỷ lệ 1/500000; + Sơ đồ các vùng nguồn tiềm năng động đất, núi lửa và động đất kích thích khu vực thềm lục địa đông nam Việt Nam tỷ lệ 1/500000; + Hệ thống các giải pháp phòng tránh tai biến địa chất và giảm thiểu thiệt hại; + Báo cáo. | Tạp chí Tin học và Điều khiển học T. 16 s. 3 2000 47-55 TỐI ƯU HÓA CÂY NHỊ PHÂN MỘT CHIÊU VỚI THÔNG TIN CHỨA Ở CÁC ĐÌNH TRONG TRÊN TẬP KHÓA HỮU HẠN Đỗ ĐỨC GIÁO ĐẶNG THỊ NGA VÀ vũ LÊ TÚ Abstract. The notion of search tree plays an impotant role in computer science especially in the theory of data structures. The efforts to optimize one dimensional binary search tree as introduced in this paper quite useful for practical applications especially for the representation of range queries where the information about secondary keys defined on range are organized as a binary tree. In this paper we intend to further develop the conception of the binary search tree in 3 5 and prove a theorem which shows that each binary search tree can be uniquely transformed into optimal binary search tree in the finite set of keys. 1. ĐẶT VẤN ĐÊ Trong 5 Thiele đã đưa ra định nghĩa cây nhị phân một chiều các thông itn chứa các đỉnh trong của cây trên tập khóa vô hạn N gồm các phần tứ thỏa mẫn quan hệ so sánh đồng thòi đưa ra một thuật toán để khẳng định hai cây bất kỳ có tưomg đương với nhau hay không trên tập khóa N. Dựa vào thuật toán đó cda Thiele trong 5 các tác giả trong 3 phát triển thêm thuật toán tìm cây tối ưu của một cây bất kỳ cho trước trên tập khóa vô hạn N. Trong bài báo này chúng tôi trình bày việc xây dựng thuật toán tương đưomg và thuật toán tối ưu trên lóp cây nhị phân một chiều vói các thông tin chứa ở các đỉnh trong trên tập khóa hữu han bất kỳ K c N. Thực chất nội dung của bài này là cơ sỏ xây dưng thuât toán phân rã để tối ưu hóa cây nhị phân với các thông tin chứa ỏf các đỉnh trong. Chúng tôi sẽ đe cập đến thuật toán phân rã trong một bài báo khác. 2. Sự TƯƠNG DUONG CỦA CÂY NHỊ PHÂN TRÊN TẬP KHÓA HỦU HẠN K . Định nghĩa cây nhị phân Giả sứ I là tập hữu hạn không rỗng các phần tử nào đó. I được gọi là tập các thông tin .N là tập không rỗng các phần tứ trên nó thỏa mãn quan hệ so sánh. Gọi N là tập khóa mỗi phần tứ k e N gọi là một khóa key . Đặt I I u r ờ đây T là ký