Đang chuẩn bị liên kết để tải về tài liệu:
Cấu trúc dữ liệu nâng cao P5

Cây cân bằng | CÂY CÂN BẰNG 1.CÂYNHỊ PHÂN CÂN BẰNG HOÀN TOÀN 1.1. Định nghĩa Cây cân bằng hoàn toàn là cây nhị phân tìm kiếm mà tại mỗi nút của nó số nút của cây con trái chênh lệch không quá một so với số nút của cây con phải. 1.2. Đánh giá Một cây rất khó đạt được trạng thái cân bằng hoàn toàn và cũng rất dễ mất cân bằng vì khi thêm hay hủy các nút trên cây có thể làm cây mất cân bằng chi phí cân bằng lại cây cao vì phải thao tác trên toàn bộ cây. Đối với cây cân bằng hoàn toàn trong trường hợp xấu nhất ta chỉ phải tìm qua log2N phần tử N là số nút trên cây . Sau đây là ví dụ một cây cân bằng hoàn toàn CCBHT CCBHT có N nút có chiều cao h log2N. Đây chính là lý do cho phép bảo đảm khả năng tìm kiếm nhanh trên CTDL này. Do CCBHT là một cấu trúc kém ổn định nên trong thực tế không thể sử dụng. Nhưng ưu điểm của nó lại rất quan trọng. Vì vậy cần đưa ra một CTDL khác có đặc tính giống CCBHT nhưng ổn định hơn. 1 2. CÂY NHỊ PHÂN CÂN BẰNG AVL Tree 2.1. Định nghĩa Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một. Dưới đây là ví dụ cây nhị phân cân bằng Dễ dàng thấy CCBHT là cây cân bằng. Điều ngược lại có thể không đúng không đúng. 2.2. Lịch sử cây cân bằng AVL Tree AVL là tên viết tắt của các tác giả người Nga đã đưa ra định nghĩa của cây cân bằng Adelson-Velskii và Landis 1962 . Vì lý do này người ta gọi cây nhị phân cân băng là cây AVL. Từ cây AVL người ta đã phát triển thêm nhiều loại CTDL hữu dụng khác như cây đỏ-đen Red-Black Tree B-Tree 2.3. Chiều cao của cây AVL 2 Một vấn đề quan trọng như đã đề cập đến ở phần trước là ta phải khẳng định cây AVL có N nút phải có chiều cao khoảng log2 n . Để đánh giá chính xác về chiều cao của cây AVL ta xét bài toán cây AVL có chiều cao h sẽ phải có tối thiểu bao nhiêu nút Gọi N h là số nút tối thiểu của cây AVL có chiều cao h. Ta có Neo 0 N 1 1 và N 2 2. Cây AVL có chiều cao h sẽ có 1 cây con AVL chiều cao h-1 và 1 cây con AVL chiều cao h-2. Như vậy N h l N h-l N .