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]

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

[dxu104]

else:
# 获取中序遍历中 cur 的下一个节点
tmp: TreeNode = cur.right
while tmp.left is not None:
tmp = tmp.left
# 递归删除节点 tmp
self.remove(tmp.val)
# 用 tmp 覆盖 cur
cur.val = tmp.val
请教一个问题
如果tmp有一个右子节点， self.remove(tmp.val)，是不是就把右子节点弄丢了呢？

[krahets]

不会哦，因为我们是递归调用 self.remove() 方法，它会正确处理度为 0, 1, 2 的这三种情况

[dxu104]

@krahets 好像还是哪里不对，这里的temp是待删除的节点有2个节点的情况，也就是2的情况。
while tmp.left is not None:
tmp = tmp.left
# 递归删除节点 tmp
self.remove(tmp.val)
# 用 tmp 覆盖 cur
cur.val = tmp.val
这里只考虑了temp的left的情况，如果temp.left是空的话，就跳出while循环，然后删除temp这个节点，是不是没有考虑到temp会有right的节点，从而丢失了temp的右子节点呢？

[dxu104]

打错了，这里的curr是待删除的节点有2个节点的情况，也就是2的情况

[krahets]

如果 tmp 有右子节点，那么 tmp 是度为 1 的情况。self.remove(tmp.val) 会正确处理度为 1 的情况，具体来看，会将 tmp.right 放到 tmp 的位置 ，并将 tmp 从树中移除。请注意，我们是在“递归调用”删除方法，并不是直接操作指针删除 tmp 。

[dxu104]

终于明白了，是递归删除！谢谢

[amoyonglee]

递归删除的部分理解了好久才勉强想通...

int tmpVal = tmp->val;
        // 递归删除节点 tmp
        remove(tmp->val);
        // 用 tmp 覆盖 cur
        cur->val = tmpVal;

一看到递归就犯晕,就觉得它要往下递很多层,难以在脑海中展开.
其实这里只会往下递一层,对吧? 因为tmp节点符合「子节点数量为0或1」的条件,在下一层递归中就会被delete,不会再继续递下去了,就比较容易想象一些.
这里用递归删除remove(tmp->val)可以省去手动处理tmp子节点的代码

[krahets]

没错，在这里向下递归删除只可能遇到度为 0 或 1 的情况，因为 tmp 不可能有左子节点。

不过，即使有可能存在度为 2 的情况，也不需要担心，我们只需要关注“一层递归”的正确性，只要一层是正确的，递归下去也会是正确的，不用每一层都分析。

[amoyonglee]

谢谢你的提示! 我会试着从你提示的角度去加深对递归的认识!

[ShiinaMahiru-repo]

哥，所以这个到底会不会有度为2的节点啊， 我感觉有呢， 但是我知道这么写是对的

[ShiinaMahiru-repo]

我懂了， 是没有度为2 的tmp

[rymuscle]

“然而，如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为图 7-23 所示的链表，” 感觉不用不断地插入和删除，在初始化二叉树的过程中，如果数据是有序的比如 "1,2,3,4,5,6,7"， 这样构造的单链表直接就是链表 不知道这样想对不

[amoyonglee]

你当然可以通过初始化二叉树来构建出形如图7-23的链表, 但是这里说 [退化为链表] , 主要是从效率层面, 也就是时间复杂度层面来描述的, 经过不断地插入和删除节点, 时间复杂度为O(logn)的二叉搜索树可能会 [退化] 成时间复杂度为O(n)、效率更低的链表. (个人理解)

[BigggZ123]

各位大佬，我在学的时候写了一个交互式读节点的，大家实现的是时候可以拿来查看，方便一点
def READ(node : BiTreeNode) :
nodes = []
cur = node
nodes.append(cur)

print(node.data)
print()

while True:
    
    
    cmd = input("输入指令:\t")
    
    if cmd == "a" :
        if cur.LChild is not None:
            cur = cur.LChild 
            nodes.append(cur)
            print(cur.data)
        else :
            print("触底!")

    elif cmd == "d":
        if cur.RChild is not None:
            cur = cur.RChild
            nodes.append(cur)
            print(cur.data)
        else :
            print("触底!")

    elif cmd == "w" :
        if len(nodes) == 0 :
            print("无前驱!")
            continue
        
        nodes.pop()
        cur = nodes[len(nodes) - 1]
        print(cur.data)
    
    elif cmd == 'i' :
        InOrder(node , lambda n : print(n.data , end = ' '))
    elif cmd == ' ':
        print("结束")
        return
    else :
        print("无效指令!")

    print()
    print()

[cuppar]

勘误： Rust 版本的remove 函数中有个小bug：
let left = pre.borrow().left.clone().unwrap(); // ######### 该行有可能panic，因为pre可能没有左子树，需要先进行is_some()判断后再unwrap() ######

原文：

if cur.borrow().left.is_none() || cur.borrow().right.is_none() {
        // 当子节点数量 = 0 / 1 时， child = nullptr / 该子节点
        let child = cur.borrow().left.clone().or_else(|| cur.borrow().right.clone());
        let pre = pre.unwrap();
        **let left = pre.borrow().left.clone().unwrap();** // #########    该行有可能`panic`，因为pre可能没有左子树，需要先进行is_some()判断后再unwrap()  ######
        // 删除节点 cur
        if !Rc::ptr_eq(&cur, self.root.as_ref().unwrap()) {
            if Rc::ptr_eq(&left, &cur) {
                pre.borrow_mut().left = child;
            } else {
                pre.borrow_mut().right = child;
            }
        } else {
            // 若删除节点为根节点，则重新指定根节点
            self.root = child;
        }
    }

另外有个小建议：Rust支持模式匹配，在进行多分支判断的时候使用match很容易理解，也更易读，可以考虑使用，例如：

if let Some(to_remove) = cur {
            let (left_child, right_child) = (
                to_remove.borrow().left.clone(),
                to_remove.borrow().right.clone(),
            );
            match (left_child.clone(), right_child.clone()) {
                (None, None) | (None, Some(_)) | (Some(_), None) => {
                    // only has 0/1 child, to remove the node...
                (Some(_), Some(_)) => {
                    // has 2 child, so recursion remove...
                }
            }
        } // else cur is none and nothing to remove

本章节之前的数据结构我学习的时候都用Rust实现了一遍，如有需要，可以参考：
https://github.com/cuppar/dsa_in_rust

[cuppar]

还有个小细节，recursion remove的时候应该可以直接从待删除节点的右子树开始递归删除，而不需要重新从根节点开始搜索待删除节点右子树的最左节点吧？

例如这样实现：

pub fn remove(&mut self, val: T) {
        Self::_remove(&mut self.root, val);
}

fn _remove(root: &mut Option<Edge<T>>, val: T) {
        let mut cur = root.clone();
        let mut pre = None;

        while let Some(node) = cur.clone() {
            use std::cmp::Ordering::*;
            match node.borrow().val.cmp(&val) {
                Less => {
                    pre = cur.clone();
                    cur = node.borrow().right.clone();
                }
                Equal => break,
                Greater => {
                    pre = cur.clone();
                    cur = node.borrow().left.clone();
                }
            }
        }

        if let Some(to_remove) = cur {
            let (left_child, right_child) = (
                to_remove.borrow().left.clone(),
                to_remove.borrow().right.clone(),
            );
            match (left_child.clone(), right_child.clone()) {
                (None, None) | (None, Some(_)) | (Some(_), None) => {
                    let child = left_child.or(right_child);
                    if let Some(pre) = pre {
                        let left = pre.borrow().left.clone();
                        if left.is_some() && Rc::ptr_eq(&left.unwrap(), &to_remove) {
                            pre.borrow_mut().left = child;
                        } else {
                            pre.borrow_mut().right = child;
                        }
                    } else {
                        *root = child;
                    }
                }
                (Some(_), Some(_)) => {
                    let mut to_change = to_remove.borrow().right.clone();
                    while let Some(node) = to_change.clone() {
                        if node.borrow().left.is_none() {
                            break;
                        } else {
                            to_change = node.borrow().left.clone();
                        }
                    }

                    let to_change_val = to_change.unwrap().borrow().val.clone();
                    Self::_remove(&mut Some(to_remove.clone()), to_change_val.clone());

                    to_remove.borrow_mut().val = to_change_val;
                }
            }
        } // else cur is none and nothing to remove
    }

[night-cruise]

提了一个 pr 修复了：#996，recursion remove 的代码没变主要是跟 Java 版的代码保持一致。

[krahets]

还有个小细节，recursion remove的时候应该可以直接从待删除节点的右子树开始递归删除，而不需要重新从根节点开始搜索待删除节点右子树的最左节点吧？

@cuppar 是的，这是一个可以优化的点，可以给 remove() 方法添加一个参数，用于指示从哪个节点开始搜索。

[shenhai-ran]

你好，请问在C语言实现removeItem中， 没有释放cur指针的内存，而是改变pre的left或者right的指向。是不需要释放吗？还是哪里操作了我没有看到。谢谢

[Gonglja]

Hi, cur 是需要释放的，已修复
Gonglja@4fba7c5

[mxmkeep]

老师好，C语言代码，在第3点，删掉节点那，递归删除，只需要遍历cur->right就可以吧？为何填了bst？
int tmpVal = tmp->val;
// 递归删除节点 tmp
removeItem(bst, tmp->val);
// 用 tmp 覆盖 cur
cur->val = tmpVal;

[night-cruise]

这个讨论里面已经提到这个了：#27 (reply in thread)

[qw124341789]

作者，你好，看完我有个疑问，二叉排序树删除节点后，是向左找最大，还是向右找最小。

[dabensongbing]

你说的二叉排序树应该是上面的二叉搜索树，删除节点后，如果节点的度是2，那么需要满足 左根右的顺序，需要找到一个比右小的数，那么这个数就是右的下一层的左，因为左< 根。

[qw124341789]

你说的是向左找最大，但是向右找最小也能构成新的且成立的二叉排序树

[krahets]

Hi，找中序遍历的下一个节点（右子树中最小的节点） 或者 找中序遍历的上一个节点（左子树中最大的节点），都是可以的

[fanenr]

建议在二叉搜索树章节中增加查找，插入，删除的递归操作版本，作为下一节 AVL 树中插入，删除操作的先导，也能进一步增强对递归操作的理解。

[krahets]

谢谢建议！

[WalkerInAI]

是的，每次碰到递归还是会没有头绪。推荐做一个特殊章节，章节里收录一些零碎的，使用相对频繁的，但不易理解的知识点，也可以包含一些小tips等。

[xxc111111]

我7-4-3看了几个小时正常吗

[krahets]

正常，删除操作确实比较复杂

[mrCR100]

是7.4.1中的删除节点部分吗？

[JasonNum1]

老师你好,为什么表7-2数组与搜索树的效率对比图中的无序数组的时间复杂度查找元素是O(n),插入元素是O(1),我理解数组的查找是根据索引操作的,时间复杂度应该是O(1),插入元素,后面元素都会向后移动一位,时间复杂度是O(n),麻烦老师帮忙解答下

[wooooohao]

我理解的：数组查找元素是需要遍历所有索引对应得元素，找哪个元素是你需要的，所以是O(n)，插入元素对于数组这个数据结构来说不需要按一定顺序排列，直接再后面插入就好，就不存在后面得元素都后移一位。

[JasonNum1]

如果这么理解感觉和第四章讲的就有出入了

[mrCR100]

数组中根据索引来访问元素而不是查找元素。数组支持随机访问，随机访问的时间复杂度为O(1)。

[a2635814919]

老师您好，7.4.1二叉搜索树的操作中3.删除节点部分的示例（度为2）如果修改成nex节点还有个右孩子，并且代码中

        // 递归删除节点 tmp
        remove(tmp->val);

注释”//递归删除节点tmp“如果修改为“//单层递归删除节点tmp，处理tmp节点度为1”
这样是不是会更好理解一点

[HuaWang135608]

我觉得把这个注释改为：“删除节点 tmp (递归实现)”，更合适一点；
这个节点 tmp 必然是度小于等于 1 的节点，它要么是叶节点，要么只有右子节点

[Tianyu-Huang-letsgo]

k神，强烈希望红黑树上架啊

[1435646097]

红黑树好像太难太难了，相比较之下，跳表更简单一点。

[AstoraGray]

有个问题哇，查找节点部分的Python可视化运行显示的是插入节点的可视化

[krahets]

Hi，前面几步“插入节点”是为了初始化二叉树。初始化后，后面执行的就是“查找节点”

[AllofMortal]

老师，在删除那里我有一点不明白。
把5换成4不会造成根节点比左子树大吗，为什么不把3继续挂载到左子树然后把5挂载到3的右子树