关于二叉排序树

This topic created in 2871 days ago, the information mentioned may be changed or developed.

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

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

Supplement 1 · Jul 7, 2018

我的问题来源：如果叶子节点破坏平衡调整的话题中的 T1 和 T3 不能保证相同的，而答案选择的是 23
http://m.nowcoder.com/questionTerminal?uuid=dda11740572c4059bcb929feca543751

叶子

节点

排序

二叉树

14 replies • 2018-07-07 11:40:00 +08:00

honeyshine75

Jul 6, 2018

我明明有回车的呀。。。

lovefantasy

Jul 6, 2018 via Android

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

honeyshine75

Jul 6, 2018

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

lcdtyph

Jul 6, 2018

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

zzj0311

Jul 7, 2018 via Android

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

ynyounuo

Jul 7, 2018 via iPhone

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

honeyshine75

Jul 7, 2018 via Android

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

honeyshine75

Jul 7, 2018 via Android

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

honeyshine75

Jul 7, 2018 via Android

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

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

honeyshine75

Jul 7, 2018 via Android

@lovefantasy
@lcdtyph
@zzj0311
@ynyounuo

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

liuhaotian

Jul 7, 2018 via iPhone

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

akiakiseofficial

Jul 7, 2018 via iPhone

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

honeyshine75

Jul 7, 2018 via Android

@liuhaotian
@xlui
谢谢😘😘😘

burenshiwo

Jul 7, 2018

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