PacktPublishing / Learning-JavaScript-Data-Structures-and-Algorithms-Third-Edition

Learning JavaScript Data Structures and Algorithms (Third Edition), published by Packt
MIT License
1.06k stars 429 forks source link

fix: fix avl-tree removeNode func problem #16

Closed huiliangShen closed 2 years ago

huiliangShen commented 2 years ago

Fixes #14 AVL-tree removeNode function

     // Left right case 
     if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) { 
       return this.rotationLR(node.left); 
     } 

I think this code is not correct; eg:

                      10
                 ↙          ↘  
            6                     。。。
        ↙       ↘         
      3             8       
         ↘       
             4
  1. remove node key = 8;
  2. node key=6 is not balanced;
  3. condition accord with balanceFactor === BalanceFactor.UNBALANCED_RIGHT;
  4. run return this.rotationLR(node.left);, it's will be throw error;
in fact, this condition need return this.rotationLR(node);

also, Right-left-case has same error

 // Right left case
  if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
       // need change code
        return this.rotationRL(node.right);
        ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
        return this.rotationRL(node);
   }