Cây nhị phân tìm kiếm week6 bst

1

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

BÀI THỰC HÀNH TUẦN 6

CÂY NHỊ PHÂN TÌM KIẾM

Cây nhị phân tìm kiếm là cây có tính chất: Các node có giá trị khóa nhỏ hơn khóa

ở node gốc sẽ nằm ở cây con trái, các node có giá trị khóa lớn hơn giá trị khóa

node gốc thì nằm ở cây con bên phải.

Hình minh hoạ 1: Cây nhị phân tìm kiếm

1. Số lượng node cực đại ở cấp ! là 2#

2. Số lượng node cực đại của một cây BST có độ sâu $ là

% = 2' + 2) + 2* + ⋯ + 2,-) + 2, = 2# = 2,/) − 1

,

'

3. Một cây BST được gọi là đầy đủ(full BST) khi mỗi node trên nó có đúng 2

cây con hoặc không có cây con nào.

4. Một cây BST được gọi là hoàn hảo (pefect BST) khi tất cả node lá trong

cây có cùng độ cao.

5. Một cây BST được gọi là Completed khi tất cả các node ở các cấp nhỏ hơn

cấp cuối cùng đều có đủ 2 con và tại cấp cuối cùng các node lá được dồn

về phía bên trái.