Self-balancing binary search tree
A binary search tree that remains balanced to some extent when insertion and deletion is carried out is called a self-balancing binary search tree. To create a balanced version of an unbalanced tree, we use a peculiar operation called rotation. We will discuss rotation in the following section:
Rotation of a binary search tree
This figure shows the rotation operation on nodes A and B. Left rotation on A creates the right image, and right rotation on B creates the left image. To visualize a rotation, first think about pulling out the subtree D. This subtree is somewhere in the middle. Now the nodes are rotated in either ...
Get Java 9 Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
