search

moonbitlang / core

MoonBit's Core library
https://moonbitlang.com/
Apache License 2.0
643 stars 80 forks source link

@immut/sorted_set should balance when the height diff larger or equal than 2 #1123

Closed LittleJianCH closed 1 month ago

LittleJianCH commented 1 month ago

As title, AVL tree should do balance when height diff larger than 1. But the code in immut/sorted_set/immutable_set.mbt is 

fn balance[A : Compare](left : T[A], value : A, right : T[A]) -> T[A] {
  let left_height = left.height()
  let right_height = right.height()
  if left_height > right_height + 2 {
    match left {
...

I tried to modify it to if left_height >= right_height + 2, but there is no obvious performance improvement. I'm not sure if it's necessary to fix.

Lampese commented 1 month ago

image The implementer @muqiuhan of this library should be using the ocaml base implementation of janestreet, and they have done the same.