Chứng minh số node của Heap chiều cao h
0 likes1,075 views
Chứng minh số node của Heap với chiều cao là h
More Related Content
More from David Nguyen (12)
Chứng minh số node của Heap chiều cao h
- 1. Nguyễn Ngọc Dũng - HCMUS Chứng minh số nút của Heap với chiều cao là h Theo định nghĩa thì Heap có chiều cao là h thì số node 0 => h – 2 sẽ có đầy đủ node. * Tính tổng node từ tầng 0 => h - 2 + Tầng k = 0 => 20 nút + Tầng k = 1 => 21 nút + Tầng k = 2 => 22 nút … + Tầng k = h - 2 => 2h-2 nút Snút = 20 + 21 + 22 + … + 2h-2 2*Snút = 2*(20 + 21 + 22 + … + 2h-2) 2* Snút = 21 + 22 + 23 + … 2h - 1 Ta có: u1 = 21, q = 2(Công bội) + Áp dụng công thức cấp số nhân, ta được: 2* Snut = u1. = 21. = 21.(2h-1 – 1) Snut = 2h-1 – 1 Vậy tổng số node từ tầng 0 -> h-2 là: S(0->h-2) = 2h-1 – 1 (1) Ta có: Số node của tầng h – 1: + Tối thiểu (Min) sẽ có: 1 node (2) + Tối đa (Max) sẽ có: 2h-1 (3) Từ (1)(2)(3): Số node tối đa và tối thiểu của Heap có chiều cao là h: Tối thiểu: (2h-1 – 1) + 1 Tối đa: (2h-1 – 1) + 2h-1 11-01-2013 http://ilaptrinh.wordpress.com/