chapter_tree/binary_search_tree/

[giscus[bot]]

chapter_tree/binary_search_tree/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_tree/binary_search_tree/

[NiceIICU]

删除结点的C++代码部分，TreeNode* child = cur->left != nullptr ? cur->left : cur->right;怎么理解鸭，有点看不懂，欢迎解答

[NiceIICU]

晚上好，其实我还有一个问题，remove函数是不是还需要传入一个参数TreeNode*root，不然函数里的root不知道是啥

[krahets]

晚上好，建议去 binary_search_tree.cpp 代码源文件里运行一下看看，完整的代码能看到 root 在哪定义的。

[NiceIICU]

好的谢谢，您的书籍深入浅出，容易上手，对我这种初学算法的同学真的很有帮助！

[krahets]

谢谢鼓励！

[1clay]

这是一个条件表达式，也称为三元运算符。它的含义是，如果当前节点cur的左子节点不为空，则将其左子节点赋值给child，否则将其右子节点赋值给child。

[KIDPhantom1412]

您好，未来会添加get_inorder_next这个函数的具体实现吗？

[krahets]

您好，源码包含完整实现 hello-algo/codes/python/chapter_tree/binary_search_tree.py ，建议配合源码学习～

[zzkgggg]

K神，想问下删除节点那里的代码
// 释放内存
delete cur;

为什么需要手动释放呢

[krahets]

Hi! 在 C/C++ 中，我们需要手动释放初始化在堆上的内存，以避免内存泄漏。

当我们删除一个结点后，后面就无法访问到它了，因此需要在退出方法前把它 delete 掉

[GongZhiXiaoBai]

javascript的插入节点函数最后返回应该是root吧

[krahets]

Hi 返回的是插入的结点

[GarveyH]

大佬您好，关于删除节点的部分，子节点数量等于2的图片中的例子，如果叶节点5改为3，那个这个情况下该怎么进行删除呢？

[krahets]

Hi 叶结点 5 改成 3 已经不满足二叉搜索树条件了哈

[GarveyH]

啊，光注意相邻节点，忘了5也是4的右子树了，感谢解答！

[TujinLee]

二叉搜索树插入节点都是在叶子节点上插入的吗

[krahets]

是的，都是在叶结点之下插入

[fiona-liu12]

二叉搜索树中间会有些节点的节点值为null的情况吗

[Wangyongkang69]

同问

[krahets]

@fiona-liu12 不会，那样就不满足二叉搜索树定义了

[SunAlsoRise97]

插入节点值也可用递归实现，语言：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;
    }

[TravelerEntity]

小小地提一个问题，当二叉搜索树要删除的节点有两个子节点的时候，执行步骤是这样：

1. 先遍历要删除的结点的右子树，找出最小的节点，记为 tmp
2. 然后删除 tmp 结点
3. 最后 cur.val = tmp.val

我的疑问是，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;
    }

[TravelerEntity]

TreeNode tmp = cur.right; 是引用传递嘛，为什么它在remove(tmp.val);后，还有值呢？

[krahets]

是的。remove(tmp.val) 只是将节点 tmp 从二叉树中删除，但 tmp 对象仍未被回收，因此我们还可以访问它的值。Java 等语言拥有自动内存回收机制，系统会在合适的时刻回收 tmp 。

[Ruijie-Qin]

正确的做法应该是先设置再删除吧

[minghowwww]

删除是递归调用remove的，先设置再删除的话，就删不掉了吧

[chenghui-ch]

先设置再删除就死循环了吧

[ThreeAurora]

大佬，看的时候思考了一下，“二叉搜索树的中序遍历序列是升序的”是否也是二叉搜索树应该满足的条件呢？如果现在将本页最上方的“3”换成“999”，也满足条件1和2，但中序遍历就无序了

[Ruijie-Qin]

“3”换成“999”，就不满足“左子树中所有节点的值 < 根节点的值”这个条件了

[ThreeAurora]

谢谢哈，是我看得不仔细，没注意到“所有的值”包括右子树

[ThreeAurora]

我明白二叉搜索树的优点了，它就像一个脚手架，搭起来以后方便以后动态的操作，所以值得花时间先把它构建起来。如果数据是需要经常维护的，那么它的优势就大大发挥起来了，另外中序遍历的有序性是在它搭建的过程中实现的，算是一个隐含的条件

[krahets]

没错，实际上所有数据结构都像“脚手架”。它们拥有各自的特点、优势、局限性，适用于不同任务。

[yblsy]

你好，想问下，删除部分的代码，有两个子节点的时候，换成下面的代码，会有什么问题吗

           TreeNode tmp = targetNode.left;
            while (tmp.right != null) {
                tmp = tmp.right;
            }

[yblsy]

就是，我不太明白，在删除部分 子节点数量 = 2 的情况下，为什么是 TreeNode tmp = cur.right; 而不是 TreeNode tmp = cur.left;，或者两种都可以？

[woLQL]

可以的。你这样就是将小于被删除值中的最大值放上去，作者是将大于被删除值中的最小值放上去。

[yblsy]

了解了，谢谢

[krahets]

补充 @woLQL 的回答。在子节点数量 = 2 时，我们删除该节点，则需要从二叉树中找一个合适的节点替代该节点的位置。这里“合适”的含义是：这个替换操作不会破坏二叉搜索树的性质。那么就有两种选法：

1. 选择该节点的左子树中的最大节点；
2. 选择该节点的右子树中的最小节点；

文中采取的是方法 2. ，你提到的是方法 1. ，都是可以的。

[lxl876]

补充@krahets的回答：说白了在子节点数量 = 2 时的删除操作，两种替换情况就是利用了二叉搜索树中序遍历的升序性质，找待删除这个节点前后最临近的两个节点进行替换，这样不影响升序性质

[fallenleavesguy]

请问 一下最后的递归删除这个，不是又从树顶部搜索到最底部再删除了吗？这是不是性能很不好，能不能直接删除，记录父节点的引用，直接prev.left = null。

// 递归删除节点 tmp
        remove(tmp!.val);
`

[krahets]

确实。也可以记录父节点并直接删除，但应该用 prev.left = tmp.right 。因为我们不能确定 tmp 有没有右子节点。

[github15238484509]

居然把我的疑问也给解决了，还学到了，是否有右子节点

[ZhaoLLe]

我发现这些评论是宝藏

[krahets]

是的，讨论是很好的学习方式！

[longsizhuo]

我们会在summary里总结很多评论，欢迎来看哦

[amoyonglee]

我们会在summary里总结很多评论，欢迎来看哦

请问一下这个summary在哪里呀? 我还没有找到

[krahets]

@amoyonglee 在每一章的最后一节“小结”中～

[ronalgao]

请问如何构建一棵搜索树呢？选择根节点岂不是很重要。

[krahets]

没错，构建树的方法是 build_tree() 。至于根节点的选择，我们一般会将输入数据排序，然后用中点元素作为根节点，再递归地构建左右子树，这样可以最大程度保证树的平衡性。

[zhuasdfg]

删除操作好难啊，看了40多分钟才看明白，特别是子节点数量 = 0 / 1 时，我画图一个一个比对的。是不是分开写会清晰一点。

[krahets]

确实，分开写可读性会更好一些。不过主要是要明白原理，代码实现比较自由

[selfboot]

https://gallery.selfboot.cn/zh/algorithms/binarysearchtree 这里有个可视化页面，可以方便理解其中的查找，插入和删除操作

[panumat]

老师您好，文中提到搜索树的增删操作容易造成退化，我试着实现了重排方法，使得搜索树尽可能接近完美二叉树，这么做在现实中有意义吗？
如果有意义，应该以什么指标去触发重排比较科学合理？

[travonf]

平衡二叉树

[YumeAyai]

红黑树

[ianhwu]

当然是为了维护树高，树高直观体现在查找的时间复杂度

[mcbegin]

7.4.2 二叉搜索树的效率：数组插入元素的时间复杂度不应该是O(n)么，为什么这里写O(1)？

[1435646097]

与查找节点相同，插入节点使用 O(logN) 时间。并没有说使用O(1)啊

[mcbegin]

左边一列的是数组的效率，我指的是数组插入元素的时间复杂度

[wondon101]

因为是无序数组吧，所以直接插入到末尾即可

[awentaoGit]

这个图是用什么画的？作者帮忙解答一下 。

[blight19]

这个插入的时候，如果正好不是叶子节点的情况没有处理吧

[xiaozhengF]

二叉搜索树插入新节点要保证有序性只可能是在叶子节点下插入,不可能是非叶子结点的情况

[blight19]

了解了

[xza-m]

我理解没有这么绝对吧，插入叶子结点只是最简单的构造方式。

[DBook111]

我也感觉处理的不对，他这是严格的等差为1的递增情况，正好在叶子上插入了。

[Kino-Qin]

二叉树搜索树只会在叶子节点处插入，这是二叉搜索树的缺陷，会导致二叉搜索树的退化。后面的AVL树通过加入旋转操作，修复了这个缺陷

[xiaozhengF]

二叉搜索树删除一个结点后,再重新插入,插入后的二叉搜索树是不是和最开始的不一样啊,k神再说下如果是平衡二叉树会是什么结果啊

[1159249257]

妙蛙，好一步递归删除tmp节点

[1159249257]

删除两个子节点，中序遍历cur节点的左子树最大的节点val或者cur右子树最小的val，再递归删除临时节点最后对对cur的数值进行覆盖

[Blueman123456]

对的·

[Than-Sing]

NOTE：递归删除的tmp节点至多只有右子树，度为1。直接把右子树传给tmp的父节点应该就可以了

[LiHuigui]

新手刚把树这章学完。但是期间遇到了一些问题（现已解决）在这里分享一下对这一部分内容安排的反馈和建议：
我希望作者在7.4二叉搜索树部分，把查找插入和删除的利用递归实现的代码进行讲解。让读者深刻理解到二叉搜索树递归插入和递归删除后面的思想，这样在下一节7.5的AVL树处才能比较好的理解AVL树的查找，插入，删除代码，因为7.5的代码都是递归思想。而7.4的代码其实都是迭代思想。对我这种新手来说这种安排会出现比较难消化7.5的内容的情况。
我是事后去找了课外（本书以外）的教学内容，把7.4的查插删的用递归实现的思想完全搞懂了，回过头来再看7.5的代码才感觉容易理解了。

[WUZHUHE38]

public Object remove(T key) {
BSTNode<T, V> p = root;
BSTNode<T, V> parent = null;
while (p != null) {
int res = key.compareTo(p.key);
if (res == 0) {
break;
}
parent = p;
p = (res < 0) ? p.left : p.right;
}
if (p == null) return null;
V returnValue = p.value;
if (p.left == null || p.right == null) {
BSTNode<T, V> child = (p.left != null) ? p.left : p.right;
if (p != root) {
if (parent.left == p) {
parent.left = child;
} else {
parent.right = child;
}
} else {
root = child;
}
} else {
BSTNode<T, V> tmp = p.right;
BSTNode<T, V> tmpParent = p;
while (tmp.left != null) {
tmpParent = tmp;
tmp = tmp.left;
}
p.key = tmp.key;
p.value = tmp.value;
if (tmpParent != p) {
if (tmpParent.left == tmp) {
tmpParent.left = tmp.right;
}
} else {
tmpParent.right = tmp.right;
}
}
return returnValue;
}

[WUZHUHE38]

非递归实现

[tstanon]

非递归实现从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);
    }
}

[OrangeAlien]

递归删除那里，tmp 的左子树必然是 null，递归深度最大也只有1层。可以直接判断有没有右子树，有的话用 tmp_pre 保存 tmp 的父节点，tmp_pre->left=tmp->right ，没有的话不操作。后面 cur->val=tmp->val; free(tmp); tmp_pre->left=null 就好

[FrierenGreatDemonLord]

也可以通过三元运算符优化选择左右子树的判断，如：

cur = cur->val < val? cur->right : cur->left;

[PeriZhao]

删除的时候“假设我们选择右子树的最小节点（中序遍历的下一个节点）”中序遍历确实tmp就是5，但是为啥cur.right就代表中序，如果是前序岂不是就不对了？（我好迷）没明白哪一步是“查找cur在中序遍历的后继节点”

[xjjeffery]

中序是从 cur.right 节点开始 ，而中序遍历又是一直遍历左子树，所以先获取 cur.right 节点，然后循环获取此子树中最小值的节点

[Allen-ZGD]

"如图 7-22 所示，二叉树的中序遍历遵循“左 根 右”的遍历顺序，而二叉搜索树满足“左子节点< 根节点 < 右子节点”的大小关系。"
中序遍历正好和二叉搜索树一致.

[xiaos2021]

用 tmp 的值覆盖待删除节点的值，并在树中递归删除节点 tmp

[xiaos2021]

补充：这句话的前后操作的顺序错误了，应该是：在树中递归删除节点 tmp，用 tmp 的值覆盖待删除节点的值

[xiaos2021]

或者拆分开，两步，更加清晰易懂：2，在树中递归删除节点 tmp，注意提前保留 tmp 节点的值。3，用 tmp 的值覆盖待删除节点的值。

[krahets]

Hi，这里不用太纠结顺序，我们可以将思路和实现之间进行解耦。

用 tmp 的值覆盖待删除节点的值，并在树中递归删除节点 tmp 。

原文用了“并”这个连词，想要表达的是这是一个整体的操作，目标是想要将 tmp 移动至待删除节点的位置。而在代码实现上，再考虑两者的先后。

[FanRec]

在C语言版本的删除函数中，是不是没有对删除根节点进行处理？
如果要删除根节点在访问pre的时候会出现访问空节点的问题。