Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 5: Cấu trúc cây - Nguyễn Hà Giang

Nguyễn Hà Giang - 2009 1 Tree Structure ThS. Nguyễn Hà Giang Hutech - FIT Nguyễn Hà Giang - 2009 2 Nội dung  Cấu trúc cây  Cây nhị phân  Cây nhị phân tìm kiếm  Cây nhị phân tìm kiếm cân bằng AVL  Phần mở rộng (cây n-phân)  Cây Top-Down  B-Tree Nguyễn Hà Giang - 2009 3 Cấu trúc dữ liệu Nguyễn Hà Giang - 2009 4 Cấu trúc cây  Tập hợp các nút và cạnh nối các nút đó  Có một nút gọi là gốc  Quan hệ one-to-many giữa các nút  Có duy nhất một đường đi từ gốc đến một nút  Các loại cây:  Nhị phân: mỗi nút có {0,1, 2} nút con  Tam phân: mỗi nút có {0,1,2,3} nút con  n-phân: mỗi nút có {0,1,..,n} nút con Nguyễn Hà Giang - 2009 5 Cấu trúc cây Sao trong máy tính, cây lại thể hiện ngược? Nguyễn Hà Giang - 2009 6 Khái niệm J Z A DRB LFAKQ Lá nút gốc Cạnh Nguyễn Hà Giang - 2009 7 Khái niệm  Thuật ngữ  Nút gốc: không có nút cha  Nút lá: không có nút con  Nút trong: tất cả các nút không phải nút lá  Chiều cao: khoảng cách từ gốc đến lá Chiều cao Nút gốc Nút trong Nút lá Nguyễn Hà Giang - 2009 8 Khái niệm Root Node A Node H Node B Node GNode FNode ENode DNode C Node KNode J Node L Node I Cây con Nút anh em Nguyễn Hà Giang - 2009 9 Nội dung  Cấu trúc cây  Cây nhị phân  Cây nhị phân tìm kiếm  Cây nhị phân tìm kiếm cân bằng AVL Nguyễn Hà Giang - 2009 10 Binary Tree  Cấu trúc cây đơn giản nhất  Tại mỗi nút gồm các 3 thành phần  Phần data: chứa giá trị, thông tin  Liên kết đến nút con trái (nếu có)  Liên kết đến nút con phải (nếu có)  Cây nhị phân có thể rỗng (ko có nút nào)  Cây NP khác rỗng có 1 nút gốc  Có duy nhất 1 đường đi từ gốc đến 1 nút  Nút không có nút con bên trái và con bên phải là nút lá Nguyễn Hà Giang - 2009 11 Binary Tree A B C D E F IH G Độ sâu/chiều cao = 3 Kích thước = 9 (số nút) Cây con trái Cây con phải Mức 1 Mức 2 Mức 3 Mức 0 Nguyễn Hà Giang - 2009 12 Binary Tree  Cây nhị phân đúng:  Nút gốc và nút trung gian có đúng 2 con  Cây nhị phân đúng có n nút lá thì số nút trên cây 2n-1 A B C D E F G H I J K Nguyễn Hà Giang - 2009 13 Binary Tree  Cây nhị phân đầy đủ với chiều sâu d  Phải là cây nhị phân đúng  Tất cả nút lá có chiều sâu d A B C D E F G Số nút = (2d+1 -1) Số nút trung gian = ? Biết số nút tính d của cây NP đầy đủ Nguyễn Hà Giang - 2009 14 Binary Tree  Duyệt cây:  Do cây là cấu trúc ko tuyến tính  3 cách duyệt cây NP  Duyệt theo thứ tự trước PreOrder: NLR  Duyệt theo thứ tự giữa InOrder: LNR  Duyệt theo thứ tự sau PostOrder: LRN Nguyễn Hà Giang - 2009 15 Binary Tree A B C D E F G H I J K PreOrder: InOrder: PostOrder: Nguyễn Hà Giang - 2009 16 Binary Tree  Cài đặt cây NP dùng liên kết typedef struct node { DataType info; struct node * left; struct node * right; } NODE; typedef NODE * NodePtr; NodePtr pTree; Trỏ nút gốc của cây NP Cấu trúc của một nút Chứa thông tin của nút Trỏ đến nút con trái Trỏ đến nút con phải Nguyễn Hà Giang - 2009 17 Binary Tree 8 5 10 1 3 4 79 20 pTree Con trỏ pTree trỏ đến nút gốc của cây Nguyễn Hà Giang - 2009 18 Binary Tree  Các thao tác:  NewNode, CreateNode, FreeNode, Init, IsEmpty  InsertLeft, InsertRight  DeleteLeft, DeleteRight  PreOrder, InOrder, PostOrder  Search  ClearTree Phần minh hoạ dùng DataType là kiểu int Nguyễn Hà Giang - 2009 19 Binary Tree  CreateNode: tạo một nút mới có giá trị là x NodePtr CreateNode(int x) { NodePtr node; node = NewNode(); node->info = x; node->left = NULL; node->right = NULL; return node; } X node new Nguyễn Hà Giang - 2009 20 Binary Tree  InsertLeft: thêm nút con bên trái nút p int InsertLeft(NodePtr p, int x) { if (p == NULL) return FALSE; if (p->left != NULL) return FALSE; p->left = CreateNode(x); return TRUE; } Nguyễn Hà Giang - 2009 21 Binary Tree  InsertRight: thêm một nút con bên phải p int InsertRight(NodePtr p, int x) { if (p == NULL) return FALSE; if (p->right != NULL) return FALSE; p->right = CreateNode(x); return TRUE; } Nguyễn Hà Giang - 2009 22 Binary Tree  DeleteLeft: xoá nút con bên trái của p, nút này phải là nút lá int DeleteLeft(NodePtr p) { NodePtr q; int value; if (p == NULL) return -1; q = p->left; if (q == NULL) return -1; if (q->left != NULL || q->right !=NULL) return -1; value = q->info; p->left = NULL; FreeNode(q); return value; } Nguyễn Hà Giang - 2009 23 Binary Tree  PreOrder: xuất theo thứ tự trước void PreOrder(NodePtr pTree) { if (pTree != NULL) { printf(“%d ”, pTree->info); PreOrder(pTree->left); PreOrder(pTree->right); } } Nguyễn Hà Giang - 2009 24 Binary Tree  InOrder void InOrder(NodePtr pTree) { if (pTree != NULL) { InOrder(pTree->left); printf(“%d ”, pTree->info); InOrder(pTree->right); } } Nguyễn Hà Giang - 2009 25 Binary Tree  PostOder void PostOrder(NodePtr pTree) { if (pTree != NULL) { PostOrder(pTree->left); PostOrder(pTree->right); printf(“%d ”, pTree->info); } } Nguyễn Hà Giang - 2009 26 Binary Tree  Search: tìm nút có khoá x NodePtr Search(NodePtr pTree, int x) { NodePtr p; if (pTree == NULL) return NULL; if (pTree->info == x) return pTree; p = Search(pTree->left, x); if (p == NULL) p = Search(pTree->right, x); return p; } Nguyễn Hà Giang - 2009 27 Binary Tree  ClearTree: xóa lần lượt nút bên trái, bên phải và nút cha. void ClearTree(NodePtr pTree) { if (pTree != NULL) { ClearTree(pTree->left); ClearTree(pTree->right); FreeNode(pTree); } } Nguyễn Hà Giang - 2009 28 Binary Tree  Các thao tác mở rộng khác: 1. Đếm số nút lá: CountLeaf 2. Đếm số nút trên cây: CountNode 3. Đếm số nút trong: CountInnerNode 4. Xác định độ sâu/chiều cao của cây 5. Tìm giá trị nhỏ nhất/lớn nhất trên cây 6. Tính tổng các giá trị trên cây 7. Đếm số nút có giá trị bằng x Nguyễn Hà Giang - 2009 29 Nội dung  Cấu trúc cây  Cây nhị phân  Cây nhị phân tìm kiếm  Cây nhị phân tìm kiếm cân bằng AVL Nguyễn Hà Giang - 2009 30 Binary Search Tree  BST là cây nhị phân mà mỗi nút thoả  Giá trị của tất cả nút con trái < nút gốc  Giá trị của tất cả nút con phải > nút gốc 5 3 1 4 10 8 20 5 Nguyễn Hà Giang - 2009 31 Binary Search Tree  Ví dụ Binary search trees Non-binary search tree 5 10 30 2 25 45 5 10 45 2 25 30 5 10 30 2 25 45 Nguyễn Hà Giang - 2009 32 Binary Search Tree 5 10 30 2 25 458 3 6 9 14 33 66 x = 9 10>9, left 5<9, right 8<9, right 9=9, Tìm thấy 5<9 8<9 9=9 Nguyễn Hà Giang - 2009 33 Binary Search Tree  Tìm (2) 5 10 30 2 25 45 5 10 30 2 25 45 10 > 2, left 5 > 2, left 2 = 2, found 5 > 2, left 2 = 2, found Nguyễn Hà Giang - 2009 34 Binary Search Tree  Tìm (25) 5 10 30 2 25 45 5 10 30 2 25 45 10 < 25, right 30 > 25, left 25 = 25, found 5 < 25, right 45 > 25, left 30 > 25, left 10 < 25, right 25 = 25, found Nguyễn Hà Giang - 2009 35 Binary Search Tree  Thời gian tìm kiếm  Dựa trên chiều cao của cây  Cây cân bằng  O(log(n))  Cây ko cân bằng  O(n)  Tương tự tìm kiếm trên danh sách, mảng ko sắp Nguyễn Hà Giang - 2009 36 Binary Search Tree  Search  Xuất phát từ gốc  Nếu nút = NULL  ko tìm thấy  Nếu khoá x = khóa nút gốc  tìm thấy  Ngược lại nếu khoá x < khoá nút gốc  Tìm trên cây bên trái  Ngược lại  tìm trên cây bên phải Nguyễn Hà Giang - 2009 37 Binary Search Tree  Search NodePtr Search(NodePtr node, int x) { NodePtr p = node; if (p != NULL) if (node->info > x) p = Search(node->left, x); else if (node->info < x) p = Search(node->right, x); return p; } Nguyễn Hà Giang - 2009 38 Binary Search Tree  Xây dựng cây BST  Chèn  Xóa  Luôn duy trì tính chất  Giá trị nhỏ hơn ở bên cây con trái  Giá trị lớn hơn ở bên cây con phải Nguyễn Hà Giang - 2009 39 Binary Search Tree  Insert  Thực hiện tìm kiếm giá trị x  Tìm đến cuối nút Y (nếu x ko tồn tại trong cây)  Nếu x < y, thêm nút lá x bên trái của Y  Nếu x > y, thêm nút lá x bên phải của Y 5 10 30 2 25 45 20 Y X mới Nguyễn Hà Giang - 2009 40 Binary Search Tree void Insert(NodePtr pTree, int x) { NodePtr node; if ( pTree == NULL) return; if (pTree->info == x) return; if (pTree->info > x) { // nhánh trái if (pTree->left == NULL) { node = CreateNode(x); pTree->left = node; } else Insert(pTree->left, x); } // nhánh phải else if (pTree->right == NULL) { // hết đường đi node = CreateNode(x); pTree->right = node; } else Insert(pTree->right, x); } Nguyễn Hà Giang - 2009 41 Binary Search Tree  Delete: xóa nhưng phải đảm bảo vẫn là cây BST  Thực hiện tìm nút có giá trị x  Nếu nút là nút lá, delete nút  Ngược lại  Thay thế nút bằng một trong hai nút sau  Y là nút lớn nhất của cây con bên trái  Z là nút nhỏ nhất của cây con bên phải  Chọn nút Y hoặc Z để thế chỗ  Giải phóng nút Nguyễn Hà Giang - 2009 42 Binary Search Tree  Trường hợp 1: nút p là nút lá, xoá bình thường 5 10 30 2 25 45 5 10 30 2 45 Xóa 25 Nguyễn Hà Giang - 2009 43 Binary Tree Search  Trường hợp 2: p chỉ có 1 cây con, cho nút cha của p trỏ tới nút con duy nhất của nó, rồi hủy p 5 10 30 2 25 45 Xóa 5 10 30 2 25 45 Nguyễn Hà Giang - 2009 44 Binary Search Tree  Trường hợp 3: nút p có 2 cây con, chọn nút thay thế theo 1 trong 2 cách như sau  Nút lớn nhất trong cây con bên trái  Nút nhỏ nhất trong cây con bên phải Nút lớn bên trái Nút nhỏ bên phải Nguyễn Hà Giang - 2009 45 Binary Search Tree  Delete: nút 10 cách 1 5 10 30 2 25 45 50 55 5 30 2 25 45 50 55 Xóa 10 Chọn nút có khoá lớn nhất bên trái Nguyễn Hà Giang - 2009 46 Binary Search Tree  Delete: nút 10 cách 2 5 10 30 2 25 45 50 55 Xóa 10 5 25 30 2 45 50 55 Chọn nút nhỏ nhất bên phải Nguyễn Hà Giang - 2009 47 Binary Search Tree  Minh họa xóa (25) 52 25 66 15 39 9 19 27 42 31 60 99 58 62 P Nguyễn Hà Giang - 2009 48 Binary Search Tree  Minh họa xóa (25) 52 25 66 15 39 9 19 27 42 31 60 99 58 62 P rp f Nguyễn Hà Giang - 2009 49 Binary Search Tree  Minh họa xóa (25) 52 27 66 15 39 9 19 27 42 31 60 99 58 62 P rp f mới Nguyễn Hà Giang - 2009 50 Binary Search Tree  Minh họa xóa (25) 52 27 66 15 39 9 19 25 42 31 60 99 58 62 P f mới Nguyễn Hà Giang - 2009 51 Binary Search Tree  Minh họa xóa (25) 52 27 66 15 39 9 19 31 42 60 99 58 62 P f mới Nguyễn Hà Giang - 2009 52 Binary Search Tree 25 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá 52 Nguyễn Hà Giang - 2009 53 Binary Search Tree 39 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Đưa giá trị của nút rp lên nút p 52 Nguyễn Hà Giang - 2009 54 Binary Search Tree 39 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Chuyển liên kết phải của p đến liên kết phải của rp 52 Nguyễn Hà Giang - 2009 55 Binary Search Tree 39 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Xoá nút rp 52 Nguyễn Hà Giang - 2009 56 Binary Search Tree 39 15 9 19 42 P f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Sau khi xoá 52 Nguyễn Hà Giang - 2009 57 Binary Search Tree  Remove (NodePtr &T, int x)  Nếu T = NULL  thoát  Nếu T->info > x  Remove(T->left, x)  Nếu T->info right, x)  Nếu T->info = x  P = T  Nếu T có 1 nút con thì T trỏ đến nút con đó  Ngược lại có 2 con  Gọi f = p và rp = p->right;  Tìm nút rp sao cho rp->left = null và nút f là nút cha nút rp  Thay đổi giá trị nội dung của T và rp  Nếu f = p (trường hợp đặc biệt) thì: f->right = rp->right;  Ngược lại: f->left = rp->right;  P = rp; // p trỏ tới rp để xoá  Xoá P Nguyễn Hà Giang - 2009 58 Binary Search Tree int Remove(NodePtr &T, int x) { if ( T == NULL) return FALSE; // không tìm thấy nút cần xoá if (T->info >x) // tìm bên trái return Remove(T->left, x); if (T->info <x) // tìm bên phải return Remove(T->right, x); NodePtr p, f, rp; p = T; // p biến tạm trỏ đến T if ( T->left == NULL) // có 1 cây con T = T->right; else if (T->right == NULL) // có 1 cây con T = T->left; Nguyễn Hà Giang - 2009 59 Binary Search Tree else { // trường hợp có 2 con chọn nút nhỏ nhất bên con phải f = p; // f để lưu cha của rp rp = p->right; // rp bắt đầu từ p->right while ( rp->left != NULL) { f = rp; // lưu cha của rp rp = rp->left; // rp qua bên trái } // kết thúc khi rp là nút có nút con trái là null p->info = rp->info; // đổi giá trị của p và rp if ( f == p) // nếu cha của rp là p f->right = rp->right; else // f != p f->left = rp->right; p = rp; // p trỏ đến phần tử thế mạng rp } FreeNode(p); // xoá nút p return TRUE; Nguyễn Hà Giang - 2009 60 Binary Search Tree  Bài tập  Cài đặt cấu trúc dữ liệu liên kết cho cây nhị phân tìm kiếm  Cài đặt các thao tác xây dựng cây: NewNode, Init, IsEmpty, CreateNode  Cài đặt thao tác cập nhật: Insert, Remove, ClearTree  Xuất danh sách tăng dần và giảm dần  Kiểm tra xem cây có phải là cây nhị phân đúng  Kiểm tra xem cây có phải là cây nhị phân đầy đủ  Xác định nút cha của nút chứa khoá x  Đếm số nút lá, nút giữa, kích thước của cây  Xác định độ sâu/chiều cao của cây  Tìm giá trị nhỏ nhất/lớn nhất trên cây  Tính tổng các giá trị trên cây Nguyễn Hà Giang - 2009 61 Mở rộng BST  Quá trình cập nhật cây nhị phân tìm kiếm thường làm cây mất cân bằng  Thao tác:  Xoay trái RotateLeft  Xoay phải RotateRight Nguyễn Hà Giang - 2009 62 Mở rộng BST  RotateLeft r a p b c Xoay trái nút r Cây con a Cây con b Cây con c Nút p sẽ trở thành nút gốc sau khi xoay Nguyễn Hà Giang - 2009 63 Mở rộng BST  RotateLeft r a p b c p c r a b Sau khi xoay Nguyễn Hà Giang - 2009 64 Mở rộng BST  Minh họa xoay trái 22 4 45 32 25 76 50 99 60 Nguyễn Hà Giang - 2009 65 Mở rộng BST  Minh họa xoay trái 22 4 45 32 25 76 50 99 60 pRoot p Nguyễn Hà Giang - 2009 66 Mở rộng BST  Minh họa xoay trái 22 4 45 32 25 76 50 99 60 pRoot p Nguyễn Hà Giang - 2009 67 Mở rộng BST  Minh họa xoay trái 22 4 45 32 25 76 50 99 60 pRoot p Nguyễn Hà Giang - 2009 68 Mở rộng BST  Minh họa xoay trái 22 4 45 32 25 76 50 99 60 pRoot p Gốc mới Nguyễn Hà Giang - 2009 69 Mở rộng BST  Thủ tục RotateLeft xoay nút root qua trái và trả về địa chỉ của nút gốc mới (thay cho root).  NodePtr RotateLeft(NodePtr root) Nếu pRoot khác rỗng & có cây con phải p = root->right root->right = p->left p->left = root return p return NULL Nguyễn Hà Giang - 2009 70 Mở rộng BST  Sử dụng thủ tục RotateLeft  Xoay trái toàn cây nhị phân: trả về con trỏ là nút gốc mới của cây  pTree = RotateLeft(pTree)  Xoay trái nhánh cây con bên trái của p: trả về con trỏ đến nút gốc mới của nhánh này  p->left = RotateLeft(p->left)  Xoay trái nhánh cây con bên phải của p:  P->right = RotateLeft(p->right)  Lưu ý: phải cập nhật link từ nút cha đến nút gốc mới  Ví dụ xoay nút p, trong đó p trỏ đến nút con trái của f  p = RotateLeft(p) // xoay trái nút p  f->left = p // cập nhật lại link từ nút cha đến nút gốc mới Nguyễn Hà Giang - 2009 71 Mở rộng BST  RotateRight r c p a b p a r b c Sau khi xoay phải Nguyễn Hà Giang - 2009 72 Mở rộng BST  Minh họa xoay phải 22 4 45 32 25 76 50 99 60 22 4 45 32 25 76 50 99 60 Nguyễn Hà Giang - 2009 73 Mở rộng BST  Thủ tục RotateRight xoay nút root qua phải và trả về địa chỉ của nút gốc mới (thay cho root).  NodePtr RotateRight(NodePtr root) Nếu pRoot khác rỗng & có cây con trái p = root->left root->left = p->right p->right = root return p return NULL Nguyễn Hà Giang - 2009 74 Mở rộng BST  Sử dụng thủ tục RotateRight  Xoay phải toàn cây nhị phân: trả về con trỏ là nút gốc mới của cây  pTree = RotateRight(pTree)  Xoay phải nhánh cây con bên trái của p: trả về con trỏ đến nút gốc mới của nhánh này  p->left = RotateRight(p->left)  Xoay phải nhánh cây con bên phải của p:  P->right = RotateRight(p->right)  Lưu ý: phải cập nhật liên kết từ nút cha đến nút gốc mới Nguyễn Hà Giang - 2009 75 Nội dung  Cấu trúc cây  Cây nhị phân  Cây nhị phân tìm kiếm  Cây nhị phân tìm kiếm cân bằng AVL Nguyễn Hà Giang - 2009 76 Đánh giá tìm kiếm  Đánh giá việc tìm kiếm 6 3 40 36 20 24 32 Tìm giá trị 32 (T1) 24 6 36 3 20 32 40 (T2) Nguyễn Hà Giang - 2009 77 Đánh giá tìm kiếm  Độ phức tạp của thao tác trên BST: chiều dài đường dẫn từ gốc đến nút thao tác  Trong cây cân bằng tốt, chiều dài của đường đi dài nhất là logn  1 triệu entry  đường dẫn dài nhất là log2 1.048.576 = 20  Trong trường hợp cây “cao”, ko cân bằng, độ phức tạp là O(n)  Mỗi phần tử thêm vào theo thứ tự đã sắp  Sự cân bằng cây là rất quan trọng Nguyễn Hà Giang - 2009 78 Cây NP hoàn toàn cân bằng  Cây NP hoàn toàn cân bằng  Là cây nhị phân  Tại mỗi nút: số nút trên nhánh trái và nhánh phải chênh lệch ko quá 1 nút! P Cây con bên trái Cây con bên phải nL(p): số nút cây con trái nút p nR(p): số nút cây con phải nút p Nguyễn Hà Giang - 2009 79 Cây NP hoàn toàn cân bằng  Trong cây NP hoàn toàn cân bằng  Có 3 trường hợp có thể có của một nút (p)  nL(p) = nR(p)  nL(p) = nR(p)+1  nR(p) = nL(p) +1  Chiều dài đường đi lớn nhất trong cây NP hoàn toàn cân bằng với n nút là log(n)  Quá trình thêm hay xóa một nút dễ làm mất trạng thái cân bằng Nguyễn Hà Giang - 2009 80 Cây NP hoàn toàn cân bằng  Minh họa 4 2 1 1 (T1) 5 2 2 1 1 (T2) 6 2 3 11 1 (T3) 7 3 3 1 11 1 (T4) 8 3 4 1 21 1 1 (T5) Nhãn của nút p cho biết số lượng nút của cây có gốc là p Nguyễn Hà Giang - 2009 81 Cây NP hoàn toàn cân bằng  Cây nhị phân tìm kiếm hoàn toàn cân bằng  Tối ưu nhất cho thao tác trên cây  Tốc độ tìm kiếm tỉ lệ với O(logn) với n là số nút  Thường bị mất cân bằng  Do thêm hay xoá  Chi phí để cân bằng rất lớn do thao tác trên toàn bộ cây  Thực tế ít sử dụng cây NPTK hoàn toàn cân bằng!  Xây dựng cây NPTK đạt trạng thái cân bằng yếu hơn (giảm chi phí) Nguyễn Hà Giang - 2009 82 Cây AVL  Cây AVL: ra đời 1962  Do tác giả Adelson-Velskii và Landis khám phá  Cây nhị phân cân bằng đầu tiên  Tính chất  Là cây nhị phân tìm kiếm  Độ cao của cây con trái và cây con phải chênh lệch ko quá 1  Các cây con cũng là AVL Nguyễn Hà Giang - 2009 83 Cây AVL  Mô tả  hl(p) là chiều cao của cây con trái nút p  hr(p) là chiều cao của cây con phải của p  Các trường hợp có thể xảy ra trên cây AVL  Nút p cân bằng hl(p) = hr(p)  Lệch về trái: hl(p) > hr(p) (lệch 1 đơn vị)  Lệch về phải: hl(p) < hr(p) (lệch 1 đơn vị)  Thao tác thêm hay xoá có thể làm AVL mất cân bằng  Thao tác cân bằng lại trên AVL xảy ra ở cục bộ Nguyễn Hà Giang - 2009 84 Cây AVL  Nút p cân bằng P TL TR hl(P) = hr(P) 30 25 15 27 35 54 30 25 15 32 35 54 30 25 15 32 35 54 27 (T1) (T2) (T3) Nguyễn Hà Giang - 2009 85 Cây AVL  Nút p lệch trái P TL TR hl(P) = hr(P) + 1 hl(P) hr(P) 30 25 15 27 35 (T1) 30 25 15 32 35 5427 (T3) 20 30 25 15 32 35 5427 (T3) 2010 Nguyễn Hà Giang - 2009 86 Cây AVL  Nút p lệch phải P TR TL hr(P) = hl(P) + 1 hl(P) hr(P) 30 25 32 35 54 (T1) 30 25 15 32 35 5427 (T2) 4030 25 15 32 35 54 (T3) 40 5531 Nguyễn Hà Giang - 2009 87 Cây AVL  Chỉ số cân bằng bf (Balance Factor)  Hiệu số chiều cao cây con trái với cây con phải  Xét một nút p bất kỳ trong cây AVL thì bf  bf(p) = 0: hl(p) = hr(p)  bf(p)