Cây cân bằng Balanced trees

*Phần 2: Các giải thuật nâng caoChương 3: Cây cân bằng Balanced trees PGS. TS. TRẦN CAO ĐỆĐại Học Cần Thơ 2013*Cây tìm kiếm nhị phânbinary search tree Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà khoá tại mỗi nút lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải.typedef KeyType;typedef struct Node{KeyType Key;Node* Left;Node* Right;};typedef Node* Tree;20101751535224237*thêm một khoá vào cây TKNPvoid InsertNode(KeyType x,Tree& Root ){/* thêm nút mới chứa khoá x */ if (Root == NULL){ Root=(Node*)malloc(sizeof(Node));Root->Key = x;Root->Left = NULL;Root->Right = NULL; } else if (x Key) InsertNode(x,Root->Left); else if (x>Root->Key)InsertNode(x,Root->Right);}1920101751535224237Xóa nút 35Xóa nút 17Xóa nút 20Xóa một nút trên cây TKNP20101752235254224201035NULL1017515*Xóa một nút trên cây TKNPKeyType DeleteMin (Tree& Root ){KeyType k;if (Root->Left == NULL){k=Root->Key; Root = Root->Right;return k;}else return DeleteMin(Root->Left);}void DeleteNode(KeyType x,Tree& Root){if (Root!=NULL)if (x Key) DeleteNode(x,Root->Left);else if (x > Root->Key) DeleteNode(x,Root->Right);else if ((Root->Left==NULL) && (Root->Right==NULL)) Root=NULL; elseif (Root->Left == NULL) Root = Root->Right;else if (Root->Right==NULL) Root = Root->Left; else Root->Key = DeleteMin(Root->Right);}*Phân tích BSTTìm kiếm một nút trên cây TKNPMất O(1) duyệt trên mỗi nútMỗi lần duyệt đi sâu xuống một mức Vậy thời gian tìm kiếm là O(h) với h là chiều cao của cây Thời gian tìm kiếm 1 nút, thêm một nút, xóa một nút trên cây TKNP là O(h), với h là chiều cao của cây TKNPChiều cao của cây TKNP có n nút: Logn ≤ h ≤ n *Cây AVLTrong trường hợp xấu nhất thời gian thực hiện các phép toán trên BST là O(n)Cân bằng AVLDo Adelson Velski và LandisAVL: Cây TKNP mà chiều cao của hai cây con của mọi nút chênh lệch nhiều nhất là 1.Trên cây AVL các phép tìm kiếm, thêm, xoa một nút là O(log n), n là số nútChứng minhGọi Nh số nút cây AVL có chiều cao h.Nh ≥ Nh-1 + Nh-2 + 1 ≥ 2Nh-2 + 1 ≥ 1 + 2(1 + 2Nh-4) = 1 + 2 + 22Nh-4 ≥ 1 + 2 + 22 + 23Nh-6 ≥ 1 + 2 + 22 + 23 + ... + 2h/2 = 2h/2+1 – 1Vậy2h/2+1 – 1 < nh/2 +1 < log2(n + 1)h < 2 log2(n + 1)Phân tích sâu sắc theo số Fibonacci, giới hạn trên là 1.44 log(n + 2). *Thêm một nút vào cây AVLĐầu tiên thêm một nút vào cây TKNP. Cây có thể mất cân bằng.Cân bằng lại Xét cây AVL: tree T=(r,Tl,Tr) trong đó Tl có chiều cao hl và Tr có chiều cao hrGiả sử nút thêm vào trên Tr.Nếu hl=hr+1: sau khi thêm vẫn cân bằngNếu hl=hr : sau khi thêm vẫn cân bằngNếu hl=hr-1 thì sau khi thêm sẽ mất cân bằngcân bằng lại.Tương tự nếu thêm nút vào Tl*Single Rotation-RRRR rotation *Single rotationLLLL *Double rotation-LRLR *Double rotation-RLRL *Các định lý4 phép quay LL, RR, LR, và RL phủ toàn bộ các trường hợp cần phải cân bằng lạiTrường hợp cây AVL trở nên mất cân bằng khi thêm một nút chỉ cần một phép quay để làm cho cây cân bằng lại.Trường hợp cây AVL trở nên mất cân bằng khi Xóa một nút có thể cần tới O(log n) phép quay để làm cho cây cân bằng lại (từ nút mất cân bằng đến gốc).*Ví dụ thêm 1 khóaThêm khóa 1Thêm khóa 32LL Xóa nút 44RR rotationLL rotation*AVL Trees Implementation in javaSee 3.6.1 chapter 3, Algorithm design, Goodrich*d-câyCây đa phân: là cây mỗi nút có từ hai con trở lên. Cây có thứ tự: các nút có ttNút v là d-nút: V có d≥2 nút conCây tìm kiếm đa phân (multi-way search tree) là cây có thứ tự với các tính chất sau:Mỗi nút trong là một d-nút có ít nhất 2 nút con.Mỗi nút lưu trữ một tập hợp các phần tử dạng (k,x), k là khóa x là giá trị kết hợp với khóaMỗi d-nút (có các nút con v1,..,vd) sẽ lưu d-1 phần tử dạng (k1,x1), , (kd-1,xd-1) và mỗi phần tử (k,x) lưu trong cây con gốc vi phải thỏa mãn: ki-1 ≤ k < ki ( k0= -∞ còn kd = +∞) Định lý: cây tìm kiếm đa phân chứa n phần tử có (n+1) nút ngoài*Ví dụ: 3-cây225 10253 46 81423 242711 1317Xem thêm các giải thuật B-Cây trong giáo trình GT của Nguyễn Văn Linh*Cây 2-3-4 hoặc cây (2,4)Cây (2,4) là 4-cây cân bằng:Mỗi nút có tối đa 4 nút conCác nút lá cùng một độ sâuĐịnh lý:Cây (2,4) chứa n phần tử có chiều cao (logn)255 15 500 36 7 917 19 20 4070*Thêm 1 phần tử vào cây (2,4)thêm 4,6,12,15,3,5,10,8 44, 64, 6, 124, 6, 12, 15split4, 612153, 4, 612153, 4, 5, 612153, 45, 12156split3, 45, 12156,103, 45, 12156, 8, 10SỐ lần split khi thêm 1 phần tử là O(logn)*Xóa một phần tử trong cây (2,4)Xóa một phần tử có khóa k Tìm kiếm nút chứa khóa kXóa phần tử. Ta luôn có thể giả sử phần tử bị xóa nằm tại nút v là lá. Nếu phần tử bị xóa là pt thứ i của nút z, tức là (ki,xi), là nút trong, ta đổi (ki,xi) với một phần tử thích hợp:Tìm nút cực phải trên cây con thứ i của z, gọi đó là nút vĐổi chổ (ki,xi) với phần tử cuối cùng của v.Việc xóa như trên: bảo toàn độ sâuKhông bảo toàn điều kiện về số phần tử chuyển phần tử từ anh em (3-nút, 4-nút) sang, hoặc Kết hợp 2 nút 125, 101546 81113 14174126 1015581113 141712111161558 1013 141713 141161558 1014171161558 10141714156 1115 1758 10*Hiệu quả của cây (2,4)Thêm, xóa, tìm một phần tử với thời gian O(logn) *Cây đỏ-đen red – black treesCây đỏ đen là cây TKNP với các nút được tô màu đỏ/đen:Gốc: đen Nút ngoài: đenCon nút đỏ là nút đenTất cả các nút ngoài (NIL) có cùng độ sâu đen (cùng số nút đen tiền bối)Định lý: Cây đỏ-đen chứa n nút sẽ có độ cao O(Logn)CM: Tr172*Tương đương giữa cây đỏ đen và cây (2,4)1013 1413 14 201014131314141320*Tương đương giữa cây đỏ đen và cây (2,4)*Các phép quayRight-Rotation(B)Left-Rotation(A)Định lý: Các phép quay trái và quay phải như trên bảo tồn trật tự các nút trên cây TKNP. *Thêm một phần tử vào cây đỏ đenThêm phần tử có khóa x vào cây đỏ đenTìm kiếm và thêm vào cây TKNPTô màu: Đen nếu là ROOT, Đỏ ngược lạiNhư vậy:Tính chất cân bằng “đen” bảo toànTính chất nút đỏ có thể bị vi phạm: Cha nút mới có thể là nút đỏ (double red). Gọi z là nút mới thêm, v là cha của z: Nếu v là nút đỏ thì cha của v là u phải là nút đen. Gọi w là sibling của v.double red: Tô màu lại Trường hợp 1: w là nút đen10zu3020vwu3010vw20zu1020vw30zu1030vw20zb2030ca10Rotationa,b,c là 3 nút theo thứ tự duyệt trung tựdouble red: Tô màu lại Trường hợp 1: w là nút đỏ10zu3020vw4010 20 30 40Recoloring10zu3020vw403010 2040zuvwzuwvuwvzTương tựzuvwzuwvuwvzRecoloring*Ví dụ: đưa các nút 4,7,12, 15, 3, 5, 14, 18, 16, 17 vào cây đỏ đen741212741512741512741535127415351474351412151874351412151874351412151816743514121618151774351412161815177435141216181517RB-INSERT(T, x){ BST-TREE-INSERT(T, x) color[x] ← RED //only RB property 3 can be violated while (x ≠ root[T] and color[p[x]] = RED) do { if p[x] = left[p[p[x]] then { y ← right[p[p[x]] // y = aunt/uncle of x if color[y] = RED then Case_1 else if x = right[p[x]] then { Case_2 // Case 2 falls into Case 3 Case_3 } } else 〈“then” clause with “left” and “right” swapped〉 }color[root[T]] ← BLACK *Case 1Là một cây đỏ đen hợp lệ (Gốc đen, các nhánh đều có cùng số nút đen)*Case 2, 3*Định lýThêm một phần tử vào cây đỏ đen chứa n nút cần O(logn) phép recoloring và O(1) phép quay để cấu trúc lại cây.*Xóa một nút trên cây đỏ đenTìm kiếm và xóa phần tử trên cây TKNPTa luôn xóa nút lá hoặc nút chỉ có 1 nút conGọi v là nút bị xóa, w là nút con ngoài của v, r là nút anh em của w, x là nút cha của v. Xóa v và w, cho r là con của x. vwrxxr*Nếu v là nút đỏ (thì r đen) hoặc r đỏ (thì v đen)thay v bởi r, tô r đen và dừngrvwxrvwxvwrxvxdouble-blackNếu v đen và r cũng đen: Sau khi xóa thì r được đặt màu “giả” double-black)Cấu trúc lại bộ 3 nút ( 3-nodes restructuring)Trường hợp 1: nút y anh em của r là đen, nút y có một con màu đỏ (z). Gọi a,b,c là ba nút x,y,z theo thứ tự duyệt trung tựy20z1030xy10z2030x40rRestructuring(z)ba10203040cr40rTrường hợp 2: nút y anh em của r là đen, nút y có hai con đen. y2030x40r10y2030x40r10RecoloringDone!X màu đỏNếu x đen, tô màu lại thì x trở thành double blacky2030xRecoloringDouble black propagatedy2030x40r40rTrường hợp 3: nút y anh em của r màu đỏAdjustment: IF (y == right(x)) THEN z=right(y) ELSE z=left(y)y2030x40r10zx3020y40r10zadjustmentBlackBlackThen, apply case 1 or case 2 without reappearing double black*Định lý Giải thuật xóa một phần tử trên cây đỏ đen chứa n phần tử có độ phức thời gian O(logn). Giải thuật cần nhiều nhất là một phép hiệu chỉnh (adjustment) và một phép cấu trúc lại bộ 3 nút (3-nodes restructuring). Như vậy nó cần nhiều nhất là 2 phép cấu trúc lại bộ 3 nút.Ví dụ14716412151835173147164121518517Xóa nút 3147164121518517Xóa nút 1214716415185171451641518717restructuring1451641518717Xóa nút 171451641518717Xóa nút 18145164157recoloring145164157145164157Xóa nút 151451647Xóa nút 1614547adjustment1454714547 recoloring*Red Black Trees Implementation in javaSee 3.6.1 chapter 3, Algorithm design, Goodrich