Phân tích cây nhị phân và các trường hợp thay thế môn Cấu trúc dữ liệu và giải thuật | Đại học Đồng Tháp
Phân tích cây nhị phân và các trường hợp thay thế môn Cấu trúc dữ liệu và giải thuật. Tài liệu được sưu tầm gồm 4 trang, giúp các bạn ôn luyện và phục vụ cho việc học tập, đạt kết quả tốt. Mời các bạn đón xem!
Môn: Cấu trúc dữ liệu và giải thuật (IN4002) 6 tài liệu
Trường: Đại học Đồng Tháp 357 tài liệu
Tác giả:
Preview text:
a. Duyệt cây nhị phân theo thứ tự trung tự: 5 13 15 16 35 40 45 47 48 49 56 b. Trường hợp 1: + Thay 40 thành 35
+ Lấy nút lớn nhất trên cây con trái là 35 Trường hợp 2: + Thay 40 thành 45
+ Lấy nút nhỏ nhất trên cây con phải là 45 a. b. - Xét nút gốc 34: Chiều cao con trái: h=1 Chiều cao con phải: h=2
Độ lệch nút gốc |1 – 2| = 1 <=1 Nút 34 cân bằng - Xét nút 17: Chiều cao con trái: h = -1 Chiều cao con phải: h = 0
Độ lệch gốc |-1 – 0| = 1 Nút 17 cân bằng - Xét nút 66: Chiều cao con trái: h = 0 Chiều cao con phải: h = 1
Độ lệch gốc |0 - 1| = 1 Nút 66 cân bằng - Xét nút 71: Chiều cao con trái: h = 0 Chiều cao con phải: h = 0
Độ lệch gốc |0 - 0| = 0 Nút 71 cân bằng Vậy cây nhị phân cân bằng.
Giải thuật Merge Sort