tailieunhanh - Cấu trúc dữ liệu và giải thuật I - Bài 13

CÂY CÂN BẰNG Mục tiêu Trình bày khái niệm cây cân bằng và các ưu điểm của cây cân bằng. Tìm hiểu một số kiểu cây cân bằng Nội dung I. Cây nhị phân cân bằng hoàn toàn nghĩa giá | BÀI 13 CÂY CÂN BẰNG Mục tiêu Trình bày khái niệm cây cân bằng và các ưu điểm của cây cân bằng. Tìm hiểu một số kiểu cây cân bằng Nội dung Cx Cây nhị phân cân bằng hoàn toàn nghĩa giá nhị phân cân bằng AVL tree -j .Pinh nghĩa -Ũ2. Lich sử giá chiều cao của cây AVL trúc dữ liệu giá NHỊ PHÂN CÂN BẰNG HOÀN TOÀN 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. Đá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 xác suất rất lớn chi phí cân bằng lại cây lớn vì phải thao tác trên toàn bộ cây. Tuy nhiên nếu cây cân đối thì việc tìm kiếm sẽ nhanh. Đố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. Như vậy cần tìm cách tổ chức một cây đạt trạng thái cân bằng yếu hơn và việc cân bằng lại chỉ xảy ra ở phạm vi cục bộ nhưng vẫn phải bảo đảm chi phí cho thao tác tìm kiếm đạt ở mức O log2n . II. CÂY NHỊ PHÂN CÂN BẰNG AVL Đị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 cân bằng lưu ý cây này không phải là cây cân bằng hoàn toàn Dễ dàng thấy CCBHT là cây cân bằng. Điều ngược lại không đúng. 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 .