C U TRÚC D LI U VÀ Ấ Ữ Ệ
GI I THU TẢ Ậ
Ch ng 10: Cây nh phânươ ị
Ch ng 10: Cây nh phânươ ị
2
Đ nh nghĩaị
Cây nh phânị
Cây r ngỗ
Ho c có m t node g i là g c (root) và 2 cây con g i là cây ặ ộ ọ ố ọ
con trái và cây con ph iả
Ví d :ụ
Cây r ng:ỗ
Cây có 1 node: là node g cố
Cây có 2 node:
Ch ng 10: Cây nh phânươ ị
3
Các đ nh nghĩa khácị
M c:ứ
Node g c m c 0.ố ở ứ
Node g c c a các cây con c a m t node m c ố ủ ủ ộ ở ứ m là m+1.
Chi u cao:ề
Cây r ng là 0.ỗ
Chi u cao l n nh t c a 2 cây con c ng 1ề ớ ấ ủ ộ
(Ho c: m c l n nh t c a các node c ng 1)ặ ứ ớ ấ ủ ộ
Đ ng đi (path)ườ
Tên các node c a quá trình đi t node g c theo các cây con ủ ừ ố
đ n m t node nào đó.ế ộ
Ch ng 10: Cây nh phânươ ị
4
Các đ nh nghĩa khác (tt.)ị
Node tr c, sau, cha, con:ướ
Node x là tr c node y (node y là sau node x), n u trên ướ ế
đ ng đi đ n y có x.ườ ế
Node x là cha node y (node y là con node x), n u trên ế
đ ng đi đ n y node x n m ngay tr c node y.ườ ế ằ ướ
Node lá, trung gian:
Node lá là node không có cây con nào.
Node trung gian không là node g c hay node lá.ố
Ch ng 10: Cây nh phânươ ị
5
Các tính ch t khácấ
Cây nh phân đ y đ , g n đ y đ :ị ầ ủ ầ ầ ủ
Đ y đ : các node lá luôn n m m c cao nh t và các nút ầ ủ ằ ở ứ ấ
không là nút lá có đ y đ 2 nhánh con.ầ ủ
G n đ y đ : Gi ng nh trên nh ng các node lá n m m c ầ ầ ủ ố ư ư ằ ở ứ
cao nh t (ho c tr c đó m t m c) và l p đ y t bên trái ấ ặ ướ ộ ứ ấ ầ ừ
sang bên ph i m c cao nh t.ả ở ứ ấ
Chi u cao c a cây có ề ủ n node:
Trung bình h = [lg n] + 1
Đ y đ ầ ủ h = lg (n + 1)
Suy bi n ếh = n
S ph n t t i m c ố ầ ử ạ ứ i nhi u nh t là 2ề ấ i