TAILIEUCHUNG - Cấu trúc dữ liệu : CÂY CÂN BẰNG part 1

CÂY CÂN BẰNG NHỊ PHÂN CÂN BẰNG HOÀN TOÀN . Đị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. . Đá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 CÂN BẰNG PHÂN CÂN BẰNG HOÀN TOÀN . Đị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. . Đá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 . Đị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. . 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 . 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ó N 0 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 1 N h-1 N .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• tài liệu Cấu trúc dữ liệu
• đề cương Cấu trúc dữ liệu
• giáo trình Cấu trúc dữ liệu
• bài giảng Cấu trúc dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• bài tập cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp