Sự liên kết giữa các nút sau khi xoay cây AVL

[thy_tam (Thy)]

Xin chào cả nhà,
Em đang đọc đoạn code vừa chèn vừa đảm bảo cây AVL (https://www.geeksforgeeks.org/avl-tree-set-1-insertion/)
Code em paste vào đây: https://pastebin.com/fns604nb
VD: chèn vào các node 5, 6, 4, 3, 2
Ở hàm insert, sau khi chèn node 2 thì kiểm tra thấy cây đang lệch trái tại 4, vào case left left (dòng 117). Sau khi thực hiện xoay cây tại hàm rightRotate (dòng 46), hàm trả về new root (node 3).

Em không hiểu vì sao sau khi xoay, node 5 lại nối đến node 3. Em lại thấy node 5 vẫn đang nối trái đến node 4 (em biết đây là suy nghĩ sai nhưng em không lý giải được). Cho em hỏi bằng cách nào node 5 đã nối đến node 3 không ạ?
Em đã search gg cả ngày nhưng vẫn chưa hiểu, nên em mạnh dạn lên nhờ sự giúp đỡ của cả nhà, cám ơn cả nhà đã đọc topic của em.

[Sherly1001]

 98.    if (key < node->key)
 99.        node->left  = insert(node->left, key);
100.    else if (key > node->key)
101.        node->right = insert(node->right, key);

Ở dòng 99 và 101 đó bạn.

(node 5)->left sẽ trỏ đến gốc của cây con sau khi chèn (vì như chú thích thì hàm insert sẽ trả về gốc mới của cây sau khi chèn).

Ở đây, sau khi chèn (node 2) vào cây gốc (node 4) sẽ trả về một cây gốc (node 3).

[thy_tam (Thy)]

Oh, mình hiểu rồi, cám ơn bạn nhiều. Mình chợt thấy rằng mình đang bị dở ở phần đệ quy, mình sẽ luyện tập thêm để khắc phục. Một lần nữa cảm ơn bạn ^^~