minghu6

Hope for your merge @bluss

这里讲得是左偏红黑树（下文用LLRB代替），红黑树（下文用RB代替）的对应的是B4树，LLRB可以在插入的时候**部分**对应B4树（允许新产生的4-node, 然后在后续自平衡的时候可能会被分离，而B4树总是允许4-node，所以只能说部分对应）。 在删除的时候，原始paper里面只给了B3树的对应实现的代码，没有B4的具体实现（这个资料真的少）。 不管类比B3还是B4, 对于理解插/删时的重新平衡的算法，坦白讲，就完全没有用！RB就不挨着，LLRB好像很接近，但实际更是坑：我模拟B4树的插入算法可以写出LLRB的插入算法，但由于部分对应的性质，模拟B4的删除算法根本行不通。 现在网上一些学习资料里介绍LLRB都喜欢比较大篇幅地提及与B3/B4的类比，这从认知角度讲并不有利，还不如只是讲一下RB的平衡因子是黑平衡，对比一下AVL是BF因子。

另外删除的时候，左右子树递归操作的时候只能在分别h.left, h.right 不为null的情况下进行 也就是： ``` def delete(h, key): assert h is not None # 确认不是一棵空树 if key < h.key: # 在左子树中 if h.left != null: if h.left is black and...

It seems that this plan is a little outdated? https://github.com/f0rki/mapping-high-level-constructs-to-llvm-ir/issues/mapping-exception-handling-to-llvm-ir/zero-cost-exception-handling.md has moved to .rst format, And It's still an empty file (just a Title), the target isn't completed indeed.

我是很不理解AVL难以实现或者代码又臭又长的说法，在实现过程中，AVL增删时重平衡的代码非常少而且易于理解，特别是比起红黑树来！ 红黑树（RB、LLRB）不仅代码冗长，还情况复杂，不好理解（特别是删除时的重平衡，粗数了一下，代码行数RB是AVL的小3倍，LLRB也有1.5倍，而且LLRB比RB更不好理解），关于它俩的评价应该掉个个儿。

另外插入操作时要多一个步骤是复位被惰性删除的节点

插入的时候就如果找所有替罪羊节点，如果向上全部重构会导致插入开销太大，耗时的感觉几乎是二次的; 但如果只找第一个替罪羊节点，有时候个别随机输入会导致查询接近原始构造的二叉树！ （测试alpha：0.6, 0.7，0.8,表现差别不大） 我看有的实现把检查平衡的函数换成完全二叉树的测试，插入的时候也是只找第一个替罪羊节点， ```rust fn is_unbalanced(&self, alpha: f32) -> bool { // max(size(self.left), size(self.right)) > alpha as usize * self.size size(self.left).abs_diff(size(self.right)) > 1 } ``` 这样测试下来感觉不错，插入和查询的性能表现都贴近其他自平衡二叉树

> Thanks for the bug report. I tried to quickly press cursor down on a long list with 100 entries, but could not get your described behavior (on Ubuntu 22.04...

> Thanks for the bug report. I tried to quickly press cursor down on a long list with 100 entries, but could not get your described behavior (on Ubuntu 22.04...

> Python already has built-in edit support with libreadline. Do you really need `rlwrap` here? It looks like i could use `import readline` to replace rlwrap.