Bài giảng "Cấu trúc dữ liệu và giải thuật: Cây cân bằng Red Black và AA" cung cấp cho người đọc các định nghĩa về cây cân bằng Red Black, cấu trúc lưu trữ, các tính chất cây cân bằng Red Black, các thao tác cơ bản. . | Bài giảng Cấu trúc dữ liệu và giải thuật: Cây cân bằng Red Black và AA - Nguyễn Tri Tuấn Cây cân bằng Red Black và AA Review Giới thiệu Cây Đỏ – Đen (Red Black Tree) AA – Tree Winter 2011 Data Structures & Algorithms - Red Black + AA tree - Nguyen Tri Tuan, 5 Red Black Tree Định nghĩa Cấu trúc lưu trữ Các tính chất Các thao tác cơ bản Đánh giá Winter 2011 Data Structures & Algorithms - Red Black + AA tree - Nguyen Tri Tuan, 6 Red Black Tree (tt) Định nghĩa: Red-Black tree là một cây nhị phân tìm kiếm (BST) tuân thủ các quy tắc sau: [1] Mọi node phải là đỏ hoặc đen [2] Node gốc là đen [3] Các node ngoài (external node; NULL node) mặc định là những node đen [4] Nếu một node là đỏ, những node con của nó phải là đen [5] Mọi đường dẫn từ gốc đến node ngoài phải có cùng số lượng node đen Winter 2011 Data Structures & Algorithms - Red Black + AA tree - Nguyen Tri Tuan, 7 Red Black Tree (tt) H=4 H=3 Hb = 2 Hb = 2 H=3 Hb = 2 H=2 H=1 H=2 Hb = 1 Hb = 1 Hb = 1 H=1 Hb = 1 Minh họa Red-Black tree Winter 2011 Data Structures & Algorithms - Red Black + AA tree - Nguyen Tri Tuan, 8 Red Black Tree (tt) Chiều cao đen (black height – hb(x)): là số node đen trên đường đi từ node x đến node ngoài (không bao gồm x) Từ quy tắc [4] không thể tồn tại node cha và node con cùng đỏ. Khi cây đỏ đen vi phạm qui tắc này gọi là hiện tượng xung đột đỏ-đỏ Winter 2011 Data Structures & Algorithms - Red Black + AA tree - Nguyen Tri Tuan, 9 Red Black Tree (tt) Cấu trúc lưu trữ: Thông tin lưu trữ tại Node .
