chapter_tree/binary_search_tree/ #27
Replies: 49 comments 95 replies
-
删除结点的C++代码部分,TreeNode* child = cur->left != nullptr ? cur->left : cur->right;怎么理解鸭,有点看不懂,欢迎解答 |
Beta Was this translation helpful? Give feedback.
-
您好,未来会添加get_inorder_next这个函数的具体实现吗? |
Beta Was this translation helpful? Give feedback.
-
K神,想问下删除节点那里的代码 为什么需要手动释放呢 |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
大佬您好,关于删除节点的部分,子节点数量等于2的图片中的例子,如果叶节点5改为3,那个这个情况下该怎么进行删除呢? |
Beta Was this translation helpful? Give feedback.
-
二叉搜索树插入节点都是在叶子节点上插入的吗 |
Beta Was this translation helpful? Give feedback.
-
插入节点值也可用递归实现,语言:Java,请指正 public void insert(Integer value){
root = insertRecursive(root, value);
}
public TreeNode insertRecursive(TreeNode current, int value) {
if (current == null) {
return new TreeNode(value);
}
if (value > current.value){
current.right = insertRecursive(current.right,value);
}
if (value < current.value) {
current.left = insertRecursive(current.left,value);
}
return current;
} |
Beta Was this translation helpful? Give feedback.
-
小小地提一个问题,当二叉搜索树要删除的节点有两个子节点的时候,执行步骤是这样:
我的疑问是,tmp 结点都被删除了,为什么它的 tmp.val 还有值呢? // 子节点数量 = 2
else {
// 获取中序遍历中 cur 的下一个节点
TreeNode tmp = cur.right;
while (tmp.left != null) {
tmp = tmp.left;
}
// 递归删除节点 tmp
remove(tmp.val);
// 用 tmp 覆盖 cur
cur.val = tmp.val;
} |
Beta Was this translation helpful? Give feedback.
-
大佬,看的时候思考了一下,“二叉搜索树的中序遍历序列是升序的”是否也是二叉搜索树应该满足的条件呢?如果现在将本页最上方的“3”换成“999”,也满足条件1和2,但中序遍历就无序了 |
Beta Was this translation helpful? Give feedback.
-
我明白二叉搜索树的优点了,它就像一个脚手架,搭起来以后方便以后动态的操作,所以值得花时间先把它构建起来。如果数据是需要经常维护的,那么它的优势就大大发挥起来了,另外中序遍历的有序性是在它搭建的过程中实现的,算是一个隐含的条件 |
Beta Was this translation helpful? Give feedback.
-
你好,想问下,删除部分的代码,有两个子节点的时候,换成下面的代码,会有什么问题吗 TreeNode tmp = targetNode.left;
while (tmp.right != null) {
tmp = tmp.right;
} |
Beta Was this translation helpful? Give feedback.
-
请问 一下最后的递归删除这个,不是又从树顶部搜索到最底部再删除了吗?这是不是性能很不好,能不能直接删除,记录父节点的引用,直接prev.left = null。 // 递归删除节点 tmp
remove(tmp!.val);
` |
Beta Was this translation helpful? Give feedback.
-
我发现这些评论是宝藏 |
Beta Was this translation helpful? Give feedback.
-
请问如何构建一棵搜索树呢?选择根节点岂不是很重要。 |
Beta Was this translation helpful? Give feedback.
-
删除操作好难啊,看了40多分钟才看明白,特别是子节点数量 = 0 / 1 时,我画图一个一个比对的。是不是分开写会清晰一点。 |
Beta Was this translation helpful? Give feedback.
-
老师你好,为什么表7-2数组与搜索树的效率对比图中的无序数组的时间复杂度查找元素是O(n),插入元素是O(1),我理解数组的查找是根据索引操作的,时间复杂度应该是O(1),插入元素,后面元素都会向后移动一位,时间复杂度是O(n),麻烦老师帮忙解答下 |
Beta Was this translation helpful? Give feedback.
-
老师您好,7.4.1二叉搜索树的操作中3.删除节点部分的示例(度为2)如果修改成nex节点还有个右孩子,并且代码中
注释”//递归删除节点tmp“如果修改为“//单层递归删除节点tmp,处理tmp节点度为1” |
Beta Was this translation helpful? Give feedback.
-
k神,强烈希望红黑树上架啊 |
Beta Was this translation helpful? Give feedback.
-
有个问题哇,查找节点部分的Python可视化运行显示的是插入节点的可视化 |
Beta Was this translation helpful? Give feedback.
-
老师,在删除那里我有一点不明白。 |
Beta Was this translation helpful? Give feedback.
-
老师您好,文中提到搜索树的增删操作容易造成退化,我试着实现了重排方法,使得搜索树尽可能接近完美二叉树,这么做在现实中有意义吗? |
Beta Was this translation helpful? Give feedback.
-
7.4.2 二叉搜索树的效率:数组插入元素的时间复杂度不应该是O(n)么,为什么这里写O(1)? |
Beta Was this translation helpful? Give feedback.
-
这个图是用什么画的?作者帮忙解答一下 。 |
Beta Was this translation helpful? Give feedback.
-
这个插入的时候,如果正好不是叶子节点的情况没有处理吧 |
Beta Was this translation helpful? Give feedback.
-
二叉搜索树删除一个结点后,再重新插入,插入后的二叉搜索树是不是和最开始的不一样啊,k神再说下如果是平衡二叉树会是什么结果啊 |
Beta Was this translation helpful? Give feedback.
-
妙蛙,好一步递归删除tmp节点 |
Beta Was this translation helpful? Give feedback.
-
NOTE:递归删除的 |
Beta Was this translation helpful? Give feedback.
-
新手刚把树这章学完。但是期间遇到了一些问题(现已解决)在这里分享一下对这一部分内容安排的反馈和建议: |
Beta Was this translation helpful? Give feedback.
-
public Object remove(T key) { |
Beta Was this translation helpful? Give feedback.
-
非递归实现从BST中删除一个节点的C语言版本代码 void removeFromBST(TreeNode **root, float x){ // 使用**root是因为可能会改变根节点
TreeNode *cur = *root, *pre = NULL;
while (cur){ // 查找节点x
if (fabs(x - cur->val) < 1e-5) {break;} pre = cur;
if (x < cur->val) cur = cur->left; else cur = cur->right;
}
if (!cur) return; // 没有找到节点x,直接返回
if ( !(cur->left) && !(cur->right)){ // 情况1:删除叶子节点
if (pre){ // 如果不是根节点
if (pre->left == cur) pre->left = NULL; else pre->right = NULL; // 删除的方法是将父节点的指针指向NULL
} else{ *root = NULL; }
free(cur);
}else if (!(cur->left) || !(cur->right)){ // 情况2:删除有一个子节点的节点
TreeNode *tmp = cur->left ? cur->left : cur->right;
if (pre) { // 如果不是根节点
if (pre->left == cur) pre->left = tmp; else pre->right = tmp; // 删除的方法是将父节点的指针指向子节点
} else { *root = tmp; }
free(cur);
}else{ // 情况3:删除有两个子节点的节点
TreeNode *tmp = cur->right, *pretmp = cur; while (tmp->left) {pretmp = tmp; tmp = tmp->left;} cur->val = tmp->val;// 在右子树中找到最小的节点,用最小节点的值替换当前节点的值
// 因为tmp是右子树中的最小节点,所以它不可能有左子节点。它可能有一个右子节点(或者没有任何子节点)。因此,我们可以直接将tmp节点的右子节点连接到tmp的父节点(即pretmp)。
if (pretmp->left == tmp) pretmp->left = tmp->right; else pretmp->right = tmp->right;
free(tmp);
}
} |
Beta Was this translation helpful? Give feedback.
-
chapter_tree/binary_search_tree/
Your first book to learn Data Structure And Algorithm.
https://www.hello-algo.com/chapter_tree/binary_search_tree/
Beta Was this translation helpful? Give feedback.
All reactions