Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen trình bày định nghĩa cây đỏ đen, cấu trúc dữ liệu cho nút cây đỏ đen, các phép biến đổi cây đỏ đen cân bằng, các tình huống xảy ra khi duyệt ngược,. . | Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên CẤU TRÚC DỮ LIỆU CÂY ĐỎ ĐEN Bùi Tiến Lên 01/01/2017 CuuDuongThanCong.com https://fb.com/tailieudientucntt Cây đỏ đen Định nghĩa 1 Cây đỏ đen (red black tree) được Rudolf Bayer phát minh và là một cây nhị phân tìm kiếm có các đặc điểm sau 1. Mọi nút phải là nút đỏ hoặc nút đen 2. Nút gốc là nút đen 3. Nếu một nút là nút đỏ, thì con của nó phải nút đen 4. Tất cả các đường đi từ nút gốc đến nút-0 (không có con) hoặc nút-1 (có 1 con) phải có cùng số lượng nút đen (điều kiện cân bằng) Nhận xét Cây đỏ đen là cây tổng quát của cây AVL Spring 2017 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/tailieudientucntt 2 Cây đỏ đen (cont.) 13 8 17 1 11 15 25 6 22 27 Hình 1: Cây đỏ đen Spring 2017 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/tailieudientucntt 3 Cấu trúc dữ liệu cho nút cây đỏ đen Cấu trúc dữ liệu để lưu trữ cho nút cây đỏ đen 1 template 2 struct RBNode 3 { 4 T data; 5 int key; 6 NodeColor color; 7 RBNode *pLeft; 8 RBNode * pRight ; 9 RBNode * pParent ; 10 }; Spring 2017 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/tailieudientucntt 4 Tìm kiếm và duyệt I Vì cây đỏ đen là một cây nhị phân tìm kiếm, do đó tìm kiếm và duyệt cây trên cây đỏ đen tương tự như trên cây nhị phân tìm kiếm Spring 2017 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/tailieudientucntt 5 Các phép biến đổi cây đỏ đen cân bằng Có ba phép biển đổi dùng để điều chỉnh cho cây đỏ đen cân bằng I Thay đổi màu (change color ) I Thực hiện xoay trái (left rotation) I Thực hiện xoay phải (right rotation) Spring 2017 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/tailieudientucntt 6 Các phép biến đổi cây đỏ đen cân bằng (cont.) Thực hiện xoay trái giữa hai nút P và N ; trong đó, N là nút con .
