Tài liệu môn Tin Học | Đại học Ngoại Ngữ - Tin Học Thành Phố Hồ Chí Minh

gv : Huỳnh Bình Buổi 09
Cây nhị phân cân bằng - AVL Nội dung  Cài đặt cây AVL 
Áp dụng cây AVL để giải quyết tìm kiesm và tạo chỉ mục Cấu trúc của một nút : data left right bal
Bal : lưu chỉ số cân bằng Qui đ nh ch ị sốố cân bằằng ỉ bal
bal = 0 : cân bằằng chính xác (EH) h h bal = 1 : l ch ph ệ i 1 ả bal = 2 : l ch ph ệ i 2 ả  ph i cân bằằng l ả i ạ (RH) h h +1 h h +2 bal = -1 : l ch trái 1 ệ bal = -2 : l ch trái 2 ệ  ph i cân bằằng l ả i ạ (LH) h h +1 h h +2 gv : Huỳnh Bình
1. Các trường hợp phải cân bằng lại cây nhị phân: 
Trường hợp 1 : nút thêm vào ở vị trí nhánh trái của một nút trước (root) gần nhất đang bị lệch trái. 
Trường hợp 2 : nút thêm vào ở vị trí nhánh phải của một nút trước (root) gần nhất đang bị lệch phải Thêm 4 Thêm 44
2. Các trường hợp khi thêm nút vào cây (gọi r
oot là nút đang xét)
 Thêm vào bên trái root ( key < root.data) o
Xét root.bal = LH cân bằng trái (LeftBalance)  o root.bal = EH LH  không cần cân bằng  o root.bal = RH EH  không cần cân bằng 
 Thêm vào bên phải root ( key > root.data) o Xét root.bal = LH EH  không cần cân bằng  o root.bal = EH RH  không cần cân bằng  o
root.bal = RH cân bằng phải (RightBalance) 
3. Các trường hợp cân bằng trái (LeftBalance) 
Trường hợp root.left, bal = LH : trước khi xoay, gán lại balance root root.left root.left root T3 xoay phải (root) T1 h h T1 T2 T2 T3 h h h h thêm 
Không có trường hợp root.left.bal = EH 
Trường hợp root.left.bal = RH xét 
thêm nút phải root.left.right xoay kép  root root r.left.right root.left T4 r.left.right r.left root r.l.right h T4 T1 r.left h h T3 T1 T2 T3 T4 h h h h h T2 T3 T1 T2 h-1 h-1 h-1 h-1 rotateLeft(root.left) rotateRight(root) gv : Huỳnh Bình
4. Các trường hợp cân bằng phải (RightBalance) : tương tự Cài đặt class Node { public int data; //Vùng d ữ liệu public int bal; // balance : Ch ỉ s ố cân bằng public Node left; // Con tr ỏ trái public Node right; // Con tr ỏ phả i // Khai báo các thu ộ c tính public int
Data { get => data; set => data = value; } public int
Bal { get => bal; set => bal = value; }
public Node Left { get => left; set => left = value; }
public Node Right { get => right; set => right = value; } // Contructor : kh ở ạ i t o node ớ m i có data = key public Node(int key) { data = key; bal = 0; left = right = null; } } class AVLTree {
public Node root; // nút gốc public AVLTree() // Kh ở i t ạ o cây { root = null; } // Xoay ph ả i nút root public void rotateRight(ref Node root) root { p Node p = root.left; root.left = p.right; p.right = root; root = p; } // Xoay trái nút root public void rotateLeft(ref Node root) { Node p = root.right; root.right = p.left; p.left = root; root = p; } // cân b ằ ng ph ả i nút root public void balanceRight(ref Node root) { Node b = root.left; if (b.bal == -1) { root.bal = b.bal = 0; rotateRight(ref root); } else { Node c = b.right;
root.bal = c.bal < 0 ? +1 : 0; gv : Huỳnh Bình b.bal = c.bal > 0 ? -1 : 0; c.bal = 0; rotateLeft(ref root.left); rotateRight(ref root); } } // cân b ằ ng trái nút root public void balanceLeft(ref Node root) { Node b = root.right; if (b.bal == +1) { root.bal = b.bal = 0; rotateLeft(ref root); } else { Node c = b.left;
root.bal = c.bal <= 0 ? 0 : -1;
b.bal = c.bal >= 0 ? 0 : +1; c.bal = 0; rotateRight(ref root.right); rotateLeft(ref root); } }
// Thêm khóa k vào cây có g ố c là root public int re insert( f Node root, int k) { if (root == null) { root = new Node(k); //if (root == null) return 0; root.data = k; root.bal = 0; root.left = root.right = null; return 1; } if (root.data == k) return 0; if (root.data > k) {
if (insert(ref root.left, k) == 0) return 0; root.bal--; } else {
if (insert(ref root.right, k) == 0) return 0; root.bal++; } if (root.bal == 0) return 0;
if (root.bal == -1 || root.bal == +1) return 1; if (root.bal == -2) balanceRight(ref root); else balanceLeft(ref root); return 0; } ộ
// Tìm m t node có data = key ả , tr ề v node đó (gi ố ng cây BST)
public Node Search(Node root, int key) {
if (root == null) return null; // cây r ỗ ng tr ả v ề null ế
// N u root.data = key -> root là node c ầ n tìm gv : Huỳnh Bình
if (root.Data == key) return root; ế
// N u key < root.data -> tìm bên cây con trái if (root.Data > key) return Search(root.Left, key); ế
// N u key >root.data -> tìm bên cây con phả i else if (root.Data < key)
return Search(root.Right, key); else return null; } // Xu ấ t cây theo mức public void PrintTree(Node root, int muc) { int i; //Console.WriteLine(); if (root != null) {
PrintTree(root.right, muc + 1);
for (i = 0; i <= muc; i++) Console.Write(" ");
Console.Write(" |" + root.data + "|\n\n"); PrintTree(root.left, muc + 1); } } // Xóa node k, cung c ấ p thêm đ ể tham khảo public void removeX(int k) { remove(ref root, k); } public int remove(ref Node root, int k) { if (root == null) return 0; if (k < root.data) {
if (remove(ref root.left, k) == 0) return 0; root.bal++; } else if (k > root.data) {
if (remove(ref root.right, k) == 0) return 0; root.bal--; }
else if (root.left == null && root.right == null) { root = null; return 1; }
else if (root.left == null && root.right != null) { root = root.right; return 1; }
else if (root.left != null && root.right == null) { root = root.left; return 1; } else { Node p = root.left;
while (p.right != null) p = p.right; root.data = p.data ;
return remove(ref root.left, p.data); gv : Huỳnh Bình } if (root.bal == 0) return 1;
if (root.bal == -1 || root.bal == +1) return 0; if (root.bal == -2) balanceRight(ref root); else balanceLeft(ref root); return 1; } } Bài tập
Sử dụng cây AVL để tạo một bộ chỉ mục (index) cho tập tin cơ sở dữ liệu
File dữ liệu là HosoNK.txt lưu trữ thông tin của các nhân khẩu trong địa phương có dạng:
 File gồm nhiều field (cột) và ngăn cách bởi phím tab ('t/')
 Dòng đầu tiên lưu tiêu đề cột (FieldName), các dòng còn lại mỗi dòng lưu thông tin của một nhân khẩu
 Việc lưu trữ (vật lý) thông tin các nhân khẩu trên file không theo một thứ tự nhất định. Mỗi lần thêm
một thông tin NK mới được ghi tiếp ở cuối file (Append)
 Sử dụng cây AVL để tạo một chỉ mục (index) cho cột Mã NK (như trong CSDL tạo index cho Mã NK)
Mô hình cho bài toán Data Data (buffer) Xử lý Array lines  Lưu file vào array lines : 0 Mã NK H ọ lót Tên Ngày sinh
lines = …ReadAllLines(filePath); 1 111084 Ngô Nam Anh .. 
duyệt từng dòng lines[i] : 2 110788 Nguyễ n Thế Định
Tách các phần trong dòng Lines[i] : HosoNK.txt … …
string[] a = lines[i].Split('t/'); 
lưu vào bộ index (cây AVL) : cây AVL MaNK và số dòng left int data;(mank) right int stt;(s ố dòng)
Mỗi lần truy xuất trên cây theo LNR
 có thứ tự theo data (Mã NK)  stt: số dòng
 nội dung dòng dữ liệu lines[stt] gv : Huỳnh Bình
Thiết kế các đối tượng Node AVLTree HSNK int data;//Mã N khẩu Node root; AVLTree idAVL ; //lư u int stt;//s ố thứ tự ộ b ch ỉ m ụ c (index) dòng trong hố sơ string[] lines;/lư u int bal; Node left ạ t m file đ ể xử lý Node right
1. Node : như Node trong BSTTree và thêm thành phần stt (số thứ tự dòng trong hồ sơ) class Node { public int data; //Vùng d ữ li ệ u Mã nhân khẩu public int stt; ố // s ứ th ự t dòng trong hồ sơ
public int bal; // balance : Ch ỉ s ố cân bằng public Node left; // Con tr ỏ trái public Node right; // Con tr ỏ phả i // Khai báo các thu ộ c tính . . . // Contructor : kh ở ạ i t o node m ớ i có data = key public Node(int key, int so) { data = key; stt = so; bal = 0; left = right = null; } } 2. AVLTree
Là class AVTree. Trong phương thức public int insert(ref Node root, int int k, so) có thêm số
ứ ự th t so và khi gán : root.data = k; ph ả
i kèm theo gán stt : root.stt = so;
3. HSNK : hò sơ nhân khẩu class HSNK { AVLTree idAVL ; ư // l u ộ b ch ỉ m ụ c (index) string[] lines; ư // lạ u t m file đ ể xử lý // Propeties public HSNK() { } ở ạ ồ ơ // Kh i t ẩ o h sạ nhân kh ộ
u và tớo b index v i idAVL, filePath : chu ỗ i đ ượ c t ạ o từ Program public HSNK(string filePath) { idAVL = new AVLTree();// Kh ở i t ạ o cây AVL if (File.Exists(filePath)) ể // ki m tra s ự ồ tạ n t i c ủ a file {
lines = File.ReadAllLines(filePath);
for (int i = 1; i < lines.Length; i++) { // Tách các thành ph ầ n trong dòng i
string[] a = lines[i].Split('\t'); // Thêm vào cây node m ớ i có n ộ i dung MaxNK và s ố thứ tự
idAVL.insert(ref idAVL.root,int.Parse(a[0]), i); } } gv : Huỳnh Bình else {
Console.WriteLine(" Không tìm th ấ y File h ồ s ơ nhân khẩ u"); } }
ấ // Xuộ t toàn b danh sách theo index Mã NK (duyệ t LNR)
public void LNRindex(Node node) { ệDuy t idAVL, m ỗ i m
ộ t node  stt  lines[stt]  tách các thành ph ầ n và in } ấ // Xu t thông tin ộ m t nhân kh ẩ u t ạ i dòng row public void OutOne(int row) {
Thông tin có trong lines[row] tách các th  ành ph ầ n và in } // Tìm nhân kh ẩ u theo mã NK và xu ấ t lên màn hình public void FindNK(int mank) { } // Xu ấ t DS theo quận
public void LNRQuan(Node node,string quan) { } // Xu ấ t DS theo phái
public void LNRPhai(Node node, string phai) { } // Xu ấ t DS theo tuoi
public void LNRTuoi(Node node, int tuoi) { } // Thêm nhân kh ẩ u (thêm t ạ m vào lines)
public void AddnewNK(string ma, string ho, string ten, string ns, string ph, string dc, string q) {
Thêm vào lines[] và thêm node ớ ồ m i g m Mã NK và s ố tt trong lines } ậ // c p nh ậ t vào file
public void UpdateFile(string filePath) { if (File.Exists(filePath)) {
File.WriteAllLines(filePath, lines); } else {
Console.WriteLine(" Không tìm th ấ y File h ồ s ơ nhân khẩ u"); } } } } 4. Program :
Tạo môi trường làm việc cho chương trình
ấ // Xu t text theo Unicode (có d ấ u ti ế ng Việ t)
Console.OutputEncoding = Encoding.Unicode; ậ
// Nh p text theo Unicode (có d ấ u ti ế ng Việ t)
Console.InputEncoding = Encoding.Unicode; ạ // T
ườ o đẫ ng d n file dùng làm tham số
string filePath = @"../../../TextFile/HosoNK.txt"; // Kh ở i t ạ o hồ sơ HSNK hs = new HSNK(filePath); gv : Huỳnh Bình
Thiết kế giao diện với các chức năng sau đây: Giao diện chính
Chọn 1 : tìm nhân khẩu  nhập Mã NK hiển thị thông tin nhân khẩu đó 
Chọn 2 : Theo dõi nhân khẩu  có 3 chức năng : theo quận, theo phái, theo tuổi
Ví dụ chọn 3 (theo tuổi) nhập tuổi  xuất danh sách theo tuổi  gv : Huỳnh Bình
Chon 3 : xuất tất cả danh sách theo index Mã NK mẫu tương tự như trên
Chọn 4 : Thêm nhân khẩu mới nhập các thông tin yêu cầu 
ghi thông tin nhân khẩu mới vào lines 
Chon 5 : tiến hành ghi dữ liệu từ lines file HosoNK.txt 