Tham khảo tài liệu 'toán rời rạc ứng dụng trong tin học part 7', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 246 TOĂN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC Chứng mình Chứng minh bằng quy nạp theo i. - Với i 0 Đỉnh thuộc mức 0 là gốc mà mỗi cây chỉ có một gốc nên bổ để đúng. - Giả sử bổ đề đúng với i k lức là ở mức k cây có 2k đỉnh. - Xét mức k 1 và chỉ ra số đỉnh ở mức này là 2k l. Thật vây mỗi đỉnh ở mức k có đúng 2 con nên 2k đỉnh ở mức k có 2 X 2k 2k 1 con hay số đỉnh ở mức k 1 là 2k 1. Bổ đề 2 Số lượng các đỉnh trong và đỉnh ngoài của cây nhị phân đầy đủ có độ cao h là 2h 1 - 1. Chứng minh Suy ra từ bổ đề ỉ SỐ các đỉnh trong và đỉnh ngoài ở mức h số các đỉnh ở mức 0 số các đỉnh ở mức 1 4-. . . số các đỉnh ở mức h 2 4- 21 4-. 4- 2h 2h l - 1. Định lý 5 Cho cây nhị phân đầy đủ với L số các đính ngoài. Khi đó sô các đỉnh trong của cây là L - 1. Chứng minh Gọi chiều cao của cây là h. Theo bổ đề 1 thì số các đỉnh ngoài L 2h. Còn số các đỉnh trong và ngoài theo bổ đề 2 là 2h l - 1 . Nếu đặt K số đỉnh trong thì K 4- L 2h 1 - 1. Vậy K - 2 X 2h - l -2h 2L- 1 -L L- 1. Định lý 6. Cây nhị phân đầy dủ có n đỉnh thì chiều cao h của nó được tính theo công thức h log2 n 1 - 1. Chứng minh Theo bổ đề 2 thì n 2h 1 - 1 n 1 2h 1 Loga cơ số 2 hai vế đẳng thức trên ta được log2 n 4- 1 h 4- 1 hay h log2 n 1 - 1. 3. ỨNG DỤNG CỦA CÂY Xét ba bài toán bằng mô hình cây Bài toán 1 Các phần tử trong một danh sách được lưu trữ như thế nào để có thể dễ dàng định vị được chúng Bài toán 2 Hãy xác định dãy các quyết định để tìm đối tượng có tính chất X trong tập hợp các đối tượng nào đó. Phán Ui. ĐỐ THỊ VÀ ỨNG DỤNG 247 Bài toán 3 Cần phải mã hoá tập các chữ cái bằng các dãy nhị phân như thế nào để có hiệu quả sử dụng tốt nhạt . Cây tìm kiếm nhị phân đối vởi bài toán 1 Tim kiếm một phần tử trong một danh sậch là công việc thường gặp trong Tin học. Để giải quyết nó cần một thuật toán tìm kiếm có hiệu quả. Đó là cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân là một cây nhị phân trong đó mỗi con của một đỉnh hoặc là con bên phải hoặc là con bên trái mỗi đỉnh được gán một khoá sao cho với mỗi khoá chỉ xác định dược
