Về Chương 4
Lò Bộ Nhớ
LÒ BỘ NHỚ —
LƯU TRỮ CÂY NHỊ PHÂN
SONG SONG
MẢNG
LIÊN KẾT
▣
Lưu Trữ Bằng Mảng
[0]
50
[1]
30
[2]
70
[3]
20
[4]
40
[5]
60
[6]
80
[7]
—
[8]
—
[9]
—
[10]
—
[11]
—
[12]
—
[13]
—
[14]
—
⟡
Lưu Trữ Liên Kết
LEFT
30
KEY
50
RIGHT
70
LEFT
20
KEY
30
RIGHT
40
LEFT
null
KEY
20
RIGHT
null
LEFT
null
KEY
40
RIGHT
null
LEFT
60
KEY
70
RIGHT
80
LEFT
null
KEY
60
RIGHT
null
LEFT
null
KEY
80
RIGHT
null
Cấu trúc mỗi nút: [ LEFT | KEY / INFO | RIGHT ]
So Sánh Hai Phương Pháp
Tiêu chí
Mảng
Liên kết
Truy cập node
O(1) — theo chỉ số
O(n) — duyệt từ gốc
Bộ nhớ
Lãng phí (cây không đầy)
Tiết kiệm
Thêm/xóa node
Cần dịch chuyển
Chỉ thay đổi con trỏ
Tìm cha
⌊(i-1)/2⌋
Cần lưu thêm con trỏ
Tìm con
2i+1, 2i+2
Truy cập Left/Right