Thắc mắc về cân bằng lại trên cây AVL

[tara95]

Chào mọi người, mình có bài tập mong được mọi người giúp đỡ.
Thêm 1 nút trong cây AVL đòi hỏi phải cân bằng lại, mình đã làm thử bằng tay nhưng kết quả lại không ra cây AVL. Cây AVL có 4 nút: 3 6 8 9, thêm 1 nút là: 4, sau đó ta cân bằng lại. Mong mọi người góp ý, nếu ai có hướng dẫn cụ thể bằng hình (hoặc lời) thì tốt quá.
hình0252.jpg
P/s: Post bài nhầm box, mong MOD, AD move bài giùm. Em xin cảm ơn.

[11520246]

Như bạn bên dưới:

8
| \
6  9
|
3
|
4

=>
6
| \
3  8
|  |
4  9 

[13520747]

theo mình thì cân bằng lại như sau (sr do lười post hình )
node gốc là 6; mức 1 có 3 và 8 (con của 6)
mức 2 có 4 (con của 3) và 9 (con của 8)

cái này chỉ là cân bằng left-left thôi mà bạn, cứ ghép code vào là quay được thôi

[13520797]

xem thử cái này thử:

http://www.cs.scranton.edu/~mccloske/courses/cmps240/avl_trees_report.pdf

[tara95]

theo mình thì cân bằng lại như sau (sr do lười post hình )
node gốc là 6; mức 1 có 3 và 8 (con của 6)
mức 2 có 4 (con của 3) và 9 (con của 8)
cái này chỉ là cân bằng left-left thôi mà bạn, cứ ghép code vào là quay được thôi

-- Tớ làm cái này để hiểu code nên từ đầu đến giờ tớ vẫn luôn làm theo đoạn code, lúc đầu tớ cũng làm như cậu, nhưng giờ thấy có vẻ sai.
-- Theo cái cậu nói thì 8 lúc đầu là cha của 6, sau này thì 6 là cha của 8, cái này tớ nghĩ là sai, nút 8 có con trỏ Left đến 6, nhưng 6 không có con trỏ Right trỏ đến 8, cậu dùng dấu mũi tên sẽ thấy.
-- Tại nút 6 tớ thấy nó quay kiểu Left-Right chứ không phải Left-Left, vì lúc đầu nút 3 là EH, sau này nó cập nhật lại là RH.
Cậu xem thử tớ nói có đúng không, mong cậu góp ý.

[13520747]

-- Tớ làm cái này để hiểu code nên từ đầu đến giờ tớ vẫn luôn làm theo đoạn code, lúc đầu tớ cũng làm như cậu, nhưng giờ thấy có vẻ sai.
-- Theo cái cậu nói thì 8 lúc đầu là cha của 6, sau này thì 6 là cha của 8, cái này tớ nghĩ là sai, nút 8 có con trỏ Left đến 6, nhưng 6 không có con trỏ Right trỏ đến 8, cậu dùng dấu mũi tên sẽ thấy.
-- Tại nút 6 tớ thấy nó quay kiểu Left-Right chứ không phải Left-Left, vì lúc đầu nút 3 là EH, sau này nó cập nhật lại là RH.
Cậu xem thử tớ nói có đúng không, mong cậu góp ý.

Thứ nhất: trường hợp này là mất cân bằng left-left
bạn để ý sẽ thấy, tại node gốc, cây mất cân bằng trái; tại cây con bên trái, cây cũng mất cân bằng trái
với lại tái cân bằng cây AVL thì mình chỉ xét ở gốc thôi, vì bản thân cây trước khi thêm node vào thì nó đã cân bằng

Thứ hai: Node 6 vẫn có con trỏ right, chỉ là bằng NULL thôi, tức là ta có thể gán Node 6->right = Node 8 được
và trong đoạn code có 1 dòng là

T->left = T1->right

với T là Node gốc, T1 = T->left, cụ thể thì T là 8, còn T1 là 6
dòng này nếu áp dụng vào bài của bạn thì có nghĩa là cắt liên kết left của Node 8 (gán = NULL)

[tara95]

Sau khi thêm xong, nếu chiều cao của cây thay đổi, từ vị trí thêm vào, ta phải lần ngược lên gốc để kiểm tra xem có nút nào bị mất cân bằng hay không. Cái cậu đang kiểm tra là ở nút gốc. Ở đây thêm vào nút 4, sau khi thêm xong, mình phải lần ngược từ dưới lên, nút 4 và 3 không mất cân bằng, và mất cân bằng tại nút 6, ta phải cân bằng lại ở nút 6 (đóng vai trò là nút gốc trong khi cân bằng lại). Cái cậu cân bằng là ở ngay tại nút gốc luôn rồi, sau khi kiểm tra 6 xong mới xem có cần thiết phải cân bằng lại nút gốc hay không?
P/s: Không biết hiểu ý cậu hay không?

[12520234]

6
| \
4 8
| |
3 9

[13520747]

#tara95: Cảm ơn bạn. Mình vừa xem lại lý thuyết và đúng là mình đã nhầm lẫn ở chỗ này.
Vậy có nghĩa là bạn đã cân bằng được Mình ghi ra xem có đúng không nhé ^^

         8
      /    \
    4       9
   / \
 3    6

[tara95]

#tara95: Cảm ơn bạn. Mình vừa xem lại lý thuyết và đúng là mình đã nhầm lẫn ở chỗ này.
Vậy có nghĩa là bạn đã cân bằng được Mình ghi ra xem có đúng không nhé ^^

         8
      /    \
    4       9
   / \
 3    6

Tớ vẫn chưa nhìn ra được.
Tớ nói, cậu thấy sai thì bảo tớ với: Cân bằng tại nút 6, nút con bao gồm 3 (lúc đầu là EH, hiện tại là RH), nút 4 (EH), lệch về bên trái nên cân bằng lại theo bên trái. Tiếp theo vào hàm cân bằng, 6 là T, 3 là T1, T1 là RH nên xoay Left-Right. Vào hàm xoay Left-Right thì 6 là T, 3 là T1 và 4 là T2. Làm 1 tí thì ra hình zíc zắc.
:cry:

[13520747]

bạn xác định T, T1 và T2 đúng rồi
cơ mà mình không hiểu lắm câu này của bạn

lệch về bên trái nên cân bằng lại theo bên trái

bạn đã xác định được chỗ node 6 này lệch theo trường hợp left-right nên cứ áp dụng code vào thôi

gửi bạn hàm cân bằng cho trường hợp left-right của thầy Ngô Quốc Hưng

void rotateLR(AVLTree &T)
{ 
            AVLNode * T1 = T-> pLeft ; 
            AVLNode * T2 = T1-> pRight ; 
            T-> pLeft      = T2-> pRight ; 
            T2-> pRight = T; 
            T1-> pRight = T2-> pLeft ; 
            T2-> pLeft     = T1; 
            switch (T2-> balFactor ) 
            { 
                         case LH: T-> balFactor = RH; 
                                      T1-> balFactor = EH; 
                                      break ; 
                         case EH: T-> balFactor = EH; 
                                      T1-> balFactor = EH; 
                                      break ; 
                         case RH: T-> balFactor = EH; 
                                      T1-> balFactor = LH; 
                                      break ; 
            } 
 
            T2-> balFactor = EH; 
            T = T2; 
}

[tara95]

bạn xác định T, T1 và T2 đúng rồi
cơ mà mình không hiểu lắm câu này của bạn

bạn đã xác định được chỗ node 6 này lệch theo trường hợp left-right nên cứ áp dụng code vào thôi

gửi bạn hàm cân bằng cho trường hợp left-right của thầy Ngô Quốc Hưng

Cảm ơn cậu rất nhiều, mình đoảng quá.
Ngay từ đầu tớ làm không sai, code cũng không sai, chỉ quên chạy mất dòng cuối đoạn code cậu nêu

[tara95]

         8
      /    \
    4       9
   / \
 3    6

Đáp án cuối cùng là đây.