关于二叉排序树

[honeyshine75]

可能是我理解不到位，有个问题想请教各位

如果在删除二叉排序树叶子节点过程中使得该叶子节点的父节点平衡因子变为 2，那么这时候要不要调整呢？ 之所以这么问是因为都说叶子直接删，可又说破坏了平衡二叉树的条件就要旋转。 所以我就不明白了。。。

[honeyshine75]

我明明有回车的呀。。。

[lovefantasy]

建议去看下课本吧，百度下也行啊

[honeyshine75]

@lovefantasy 以及看过了都说叶子直接删

[lcdtyph]

@honeyshine75 #3
平衡二叉树的删除一般分两步：1.普通查找二叉树上的删除； 2.保持平衡
你可能只看了第一步

[zzj0311]

叶子又没有儿子当然直接删，破坏了平衡当然要旋转恢复平衡，一点毛病都没有啊😯

[ynyounuo]

删除当然要调整，否则删除还有什么难度。当然也有 lazy deletion 的形式，不过那是最笨的写法了吧。

[honeyshine75]

@lcdtyph 不是的，我看到一个选择说把叶子节点删掉之后，再插入一个同样的节点，结果一样，如果调整的话就不一样了

[honeyshine75]

@ynyounuo 书上都说的是叶子节点直接删，有子树的才调整啊

[honeyshine75]

@zzj0311 有一个问题，请各位看一下这个题，如果叶子节点删除之后调整了，那么 T1 和 T3 不能保证相同

http://m.nowcoder.com/questionTerminal?uuid=dda11740572c4059bcb929feca543751
@ynyounuo
@zzj0311
@lcdtyph

[honeyshine75]

@lovefantasy
@lcdtyph
@zzj0311
@ynyounuo

谢谢各位，我知道了，对方没说是平衡二叉排序树😅

[liuhaotian]

二叉排序树下 binary search tree
没有平衡条件
叶子：直接删 不是叶子要调整

[xlui]

二茬搜索树和平衡二叉树是不一样的，二叉搜索树不考虑失衡情况也不需要旋转。

[honeyshine75]

@liuhaotian
@xlui
谢谢😘😘😘

[chenjian026]

你这是 AVL 树吧 和二叉搜索树 BST 不一样