Chào ace, bài này chúng ta sẽ tìm hiểu về Các tính chất của Binary Tree trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Trong bài học trước, chúng ta đã được giới thiệu qua về Binary Tree. Trong bài học tiếp theo này, chúng ta sẽ cùng tìm hiểu về các tính chất của Binary Tree.
1) Số lượng nodes tối đa ở level l – cấp l của Binary Tree là 2^l
Ở đây, thuật ngữ level – cấp, có nghĩa là số lượng nodes gặp được trên đường đi từ node root cho đến một node cụ thể nào đó (bao gồm cả node root và node cụ thể đó). node root có level là 0.
Điều này có thể được chứng minh bằng quy nạp:
– Đối với node root, có i = 0, số lượng nodes của Binary Tree lúc này là 2^0 = 1
– Giả sử rằng số lượng nodes tối đa của Binary Tree ở level l là 2^l
Bởi vì trong Binary Tree, mọi node đều chỉ có nhiều nhất 2 node con, vì vậy, level tiếp theo sẽ có số node gấp đôi level trước, tức là số nodes ở level tiếp theo sẽ la: 2 * 2^l
2) Số nodes tối đa trong Binary Tree có chiều cao ‘h’ là 2^h – 1
Ở đây, chiều cao của một Tree là số nodes tối đa trên đường đi từ node root đến node leaf (node lá – là node mà không có node con nào). Chiều cao của một Tree mà chứa duy nhất một node, được coi là 1. Một Tree sẽ có số lượng nodes là tối đa nếu tất cả các levels của nó đều có số lượng nodes tối đa. Vì vậy, số lượng nodes tối đa bên trong một Binary Tree có chiều cao h là 1 + 2 + 4 + … + 2^(h-1). Đây là một cấp số nhân đơn giản với h số hạng và tổng của chuỗi này là 2^h – 1.
Tuy nhiên, trong một số sách, chiều cao của node root lại được coi là bằng 0. Nếu theo quy ước này thì công thức trên sẽ trở thành 2^(h+1) – 1
3) Trong một Binary Tree có N nodes, chiều cao tối thiểu có thể có, hoặc là số cấp tối thiểu của cây sẽ là Log2(N+1)
Tuy nhiên, nếu chúng ta xét quy ước mà trong đó, chiều cao của một node lá (leaf node) được coi là 0, thì công thức trên dành cho chiều cao tối thiểu có thể có của Binary Tree sẽ trở thành Log2(N+1) – 1
4) Một Binary Tree có L lá, sẽ có ít nhất Log2(L) + 1 cấp độ (levels)
Một Binary Tree có số lượng node lá tối đa (và có số levels tối thiểu) khi tất cả các levels của Binary Tree đều được lấp đầy (bởi các nodes). Cho tất cả các nodes lá đều ở level l, công thức dưới đây sẽ đúng với số lượng nodes lá là L:
L <= 2^(l-1) [Từ điểm 1)]
l = Log2(L) + 1
Trong đó l là số lượng levels tối thiểu của Binary Tree.
5) Trong một Binary Tree mà mọi node đều có 0 hoặc 2 nodes con, thì số lượng các node lá (leaf nodes) sẽ luôn nhiều hơn một đơn vị so với số lượng các nodes có hai nodes con.
L = T + 1
Trong đó:
– L là số lượng các node lá (leaf nodes)
– T là số lượng các nodes bên trong Binary Tree mà có hai nodes con.
Trong bài học tiếp theo của series về Tree, chúng ta sẽ tìm hiểu về các loại Binary Trees và các tính chất của chúng.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ){kind=link}