Sunday, November 29, 2020

Java Maze Solver

 

Wednesday, November 18, 2020

AVL TREE LEFT RIGHT DOUBLE ROTATIONS, DEPTH FIRST SEARCHs, BREADTH FIRST SEARCH, RECURSIVE and ITERATIVE TRAVERSALS, HEIGHT, DEPTH, SIZE, LEAF, NODE FINDERS, ROOT to LEAF NODE PATHS




SINGLE ROTATION
DOUBLE ROTATION



Suppose the node to be rebalanced is X. 
There are 4 cases that we might have to fix (two are the mirror images of the other two):

  • An insertion in the left subtree of the left child of X,
  • An insertion in the right subtree of the left child of X,
  • An insertion in the left subtree of the right child of X, or
  • An insertion in the right subtree of the right child of X.

Balance is restored by tree rotations.

Case 1 and case 4 are symmetric and requires the same operation for balance. 
Cases 1,4 are handled by single rotation.

Case 2 and case 3 are symmetric and requires the same operation for balance.
Cases 2,3 are handled by double rotation