关于二叉排序树

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2319 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

第 1 条附言 · 2018-07-07 08:41:12 +08:00

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

叶子

节点

排序

二叉树

14 条回复 • 2018-07-07 11:40:00 +08:00

honeyshine75

2018-07-06 20:24:53 +08:00

我明明有回车的呀。。。

lovefantasy

2018-07-06 20:41:44 +08:00 via Android

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

honeyshine75

2018-07-06 21:20:03 +08:00

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

lcdtyph

2018-07-06 21:38:34 +08:00

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

zzj0311

2018-07-07 00:17:10 +08:00 via Android

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

ynyounuo

2018-07-07 03:42:27 +08:00 via iPhone

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

honeyshine75

2018-07-07 08:34:08 +08:00 via Android

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

honeyshine75

2018-07-07 08:34:48 +08:00 via Android

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

honeyshine75

2018-07-07 08:38:35 +08:00 via Android

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

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

honeyshine75

2018-07-07 08:44:16 +08:00 via Android

@lovefantasy
@lcdtyph
@zzj0311
@ynyounuo

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

liuhaotian

2018-07-07 08:47:12 +08:00 via iPhone

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

xlui

2018-07-07 08:49:47 +08:00 via iPhone

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

honeyshine75

2018-07-07 10:00:42 +08:00 via Android

@liuhaotian
@xlui
谢谢😘😘😘

chenjian026

2018-07-07 11:40:00 +08:00

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