tailieunhanh - Cây cân bằng

Cấu trúc dữ liệu Cây cân bằng tương đối: Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1 (theo định nghĩa của Adelson-Velskii và Landis). Cây cân bằng tương đối còn gọi là cây AVL (AVL Tree). | ịị3. Cây cân bằng Balanced Tree . Định nghĩa - Cấu trúc dữ liệu Cây cân bằng tương đối Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1 theo định nghĩa của Adelson-Velskii và Landis . Cây cân bằng tương đối còn gọi là cây AVL AVL Tree . Cây cân bằng hoàn toàn Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì số nút của cây con trái và số nút của cây con phải của nút đó hơn kém nhau không quá 1. Cây nhị phân cân bằng hoàn toàn là cây nhị phân cân bằng tương đối. 1 í dụ 4 2 . Định nghĩa - Cấu trúc dữ liệu tt Để ghi nhận mức độ cân bằng tại mỗi nút gốc cây con dùng thêm thành phần Bal trong cấu trúc dữ liệu của mỗi nút. typedef struct BALNode T Key int Bal BALNode BALLeft BALNode BALRight BALOneNode typedef BALOneNode BALType Để quản lý cây cân bằng chỉ cần quản lý địa chỉ nút gốc của cây BALType BALTree