二叉搜索树 & 平衡树

[giscus[bot]]

二叉搜索树 & 平衡树

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

https://oi-wiki.org/ds/bst/

[cyrxdzj]

请问一下，最后一段右旋左旋的代码中，update函数的作用和基本逻辑和代码示例是什么？

[seye11]

我理解这里指的是节点信息的更新操作，比如以当前节点为根的子树大小之类的信息，具体根据题目要求来。

[OuZhou-J]

更新以该节点为根节点的树的高度
int height(node *t){return(t==NULL)?-1:t->height;}

[algo-is-my-GF]

查找排名为 k 的元素中最后一行代码中0是否应该改为 root->count，因为没有左子树，右子树应该找第k- root->count个元素啊

[demeter1210]

我认为应该是这样的

[Xuhrrr]

所以现在的代码确实没问题

[FATE-512]

在remove函数里
TreeNode* successor = findMinNode(root->right);
root->key = successor->key;
root->count = successor->count; // 更新重复数量
root->right = remove(root->right, successor->key);
如果successor->count>1，那么就没办法删掉successor了

[zxh719333938]

应该在 root->count = successor->count; 之后加上一行代码
successor->count = 1;这样可以保证删除 successor

[liukai2019]

原来是这样

[Little-Tiger29]

请问二叉搜索树与二叉查找树和二叉排序树有什么区别？

[selfboot]

就是一个东西，不同叫法

[demeter1210]

你好 二叉搜索树、二叉查找树和二叉排序树其实是同一种数据结构，都是指一种特殊的二叉树结构，具有以下特点： 1. 每个节点最多有两个子节点； 2. 左子节点的键值小于父节点的键值； 3. 右子节点的键值大于父节点的键值； 4. 左右子树也分别为二叉搜索树。 因此，这三个术语实际上是同一种树的不同称呼，没有实质性的区别。

…

________________________________ 发件人: Little-Tiger29 ***@***.***> 发送时间: 2024年8月19日 11:24 收件人: OI-wiki/gitment ***@***.***> 抄送: demeter1210 ***@***.***>; Comment ***@***.***> 主题: Re: [OI-wiki/gitment] 二叉搜索树 & 平衡树 (Discussion #1174) 请问二叉搜索树与二叉查找树和二叉排序树有什么区别？ ― Reply to this email directly, view it on GitHub<#1174 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/BIYBOA2GFMCDKZLUANN3T6DZSFQPHAVCNFSM6AAAAAATTS26ISVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAMZXG44DCMY>. You are receiving this because you commented.Message ID: ***@***.***>

[demeter1210]

那个，我是之前在oi-wiki改了什么吗？没有印象了。（笑

…

________________________________ 发件人: Little-Tiger29 ***@***.***> 发送时间: 2024年8月19日 11:24 收件人: OI-wiki/gitment ***@***.***> 抄送: demeter1210 ***@***.***>; Comment ***@***.***> 主题: Re: [OI-wiki/gitment] 二叉搜索树 & 平衡树 (Discussion #1174) 请问二叉搜索树与二叉查找树和二叉排序树有什么区别？ ― Reply to this email directly, view it on GitHub<#1174 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/BIYBOA2GFMCDKZLUANN3T6DZSFQPHAVCNFSM6AAAAAATTS26ISVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAMZXG44DCMY>. You are receiving this because you commented.Message ID: ***@***.***>

[Skys0]

我感觉 querykth 中的 k == 1 这里有点问题，应该改成k <= root->count ，因为查询到最后叶节点可能会存在count大于1但是没有左右节点。

[selfboot]

写了个 [二叉搜索树可视化页面](https://gallery.selfboot.cn/zh/algorithms/binarysearchtree)（admin: 含广告脚本，含疑似 AI 生成的内容，请考虑后使用） ，可以方便理解二叉搜索树的查找，插入和删除操作