search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

Zig-Zag Rotations in Balanced BST Lecture #102

Closed chloeslam closed 3 years ago

chloeslam commented 3 years ago

Balanced BST Lecture

I tried drawing out the rotations for the left and right zig-zag conditions, but I can't understand how we can only perform rotations to get the zig-zag conditions to be balanced. Attached to this issue is a picture of my problem. Can someone please explain how the connectivity does not need to be rearranged?

IMG_5B905BC6CBE6-1

jdchoi77 commented 3 years ago

@chloeslam after left-rotate on (1), the tree becomes left-linear as the top-left figure. then perform right-rotate on (3) would give the figure in the center.

chloeslam commented 3 years ago

So after the left-rotate on (1), (3) will no longer be connected to (1)? Because the figure in the center has (3) connected to (2) and no longer connected to (1), but I thought these only require rotations and no breaking of connectivity.

chloeslam commented 3 years ago

Oh nevermind, I understand it now. Thank you!