var a = i + this.left.length; do{ var c = this.up[a]; if(c){ // root // rotated pair var d = this.up[c]; // swap descendants var b = this.left[d]; if(c == b){ b = this.right[d]; this.right[d] = a; } else { this.left[d] = a; } this[a == this.left[c] ? "left" : "right"][c] = b; this.up[a] = d; this.up[b] = c; a = d; }else{ a = c; } }while(a); // root