如何修改红黑树插入代码以避免插入重复值？

修改思路 #

要避免插入重复值，核心是在查找插入位置的阶段就检测是否存在相同值，如果发现重复，直接终止插入流程，不执行后续的节点创建、挂载和修复操作，这样树结构完全不会改变。

修改后的完整代码 #

public void insert(int i) {
    Node x = this.root;
    Node y = null;
    
    // 遍历查找插入位置，同时检查是否存在重复值
    while (x != null) {
        y = x;
        if(i < x.data)
            x = x.left;
        else if(i > x.data)
            x = x.right;
        else {
            // 发现重复值，直接返回，不进行插入
            return;
        }
    }
    
    // 确认无重复后，创建新节点并挂载
    Node z = new Node(i, Color.RED);
    z.parent = y;
    
    if(y == null)
        this.root = z;
    else if(i < y.data)
        y.left = z;
    else
        y.right = z;
    
    z.left = z.right = null;
    z.color = Color.RED;
    insertFixup(z);
}

关键修改点 #

• 新增重复值检测逻辑：在while循环中，当发现当前节点值与要插入的i相等时，直接return，终止整个插入流程，不会对树做任何改动。
• 优化节点创建时机：把新节点的创建移到重复值检测之后，避免了重复场景下不必要的对象内存分配。
• 简化比较逻辑：遍历阶段直接用传入的i和节点值比较，无需提前创建新节点，代码更简洁高效。

这样修改后，红黑树会自动忽略所有重复的插入请求，树的结构和原有数据不会受到任何影响。

内容的提问来源于stack exchange，提问作者Tiffany