二叉搜索树插入操作中height高度变量的正确递增实现问题

问题原因 #

你当前的实现逻辑是每新增一个节点就全局height加1，这个统计的是树的节点总数，和树的高度完全不匹配。树的高度是根节点到最远叶子节点的最长路径上的节点数（或边数，可根据需求调整初始值），只有当新插入的节点深度超过当前树的最大高度时，才需要更新高度值。

解决方案 #

方案1：给Node节点新增height属性（推荐，适配增删操作）

这种方式每个节点存储以自身为根的子树高度，插入完成后回溯更新父节点高度即可，根节点的height值就是整棵树的高度。

1. 调整Node类定义：

class Node {
    String key;
    Node left, right;
    int height; // 新增字段，存储以当前节点为根的子树高度
    public Node(String key) {
        this.key = key;
        this.height = 1; // 叶子节点初始高度为1
    }
}

2. 重写插入逻辑：

// 辅助方法，避免空节点空指针异常
private int getHeight(Node x) {
    return x == null ? 0 : x.height;
}

public Node insertRec(Node x, String key) {
    if (x == null) {
        return new Node(key);
    }
    if (key.compareTo(x.key) < 0) {         
        x.left = insertRec(x.left, key);
    } else if (key.compareTo(x.key) > 0) {
        x.right = insertRec(x.right, key);
    } else {
        // 重复key不做插入，直接返回
        return x;
    }
    // 插入完成后更新当前节点高度：左右子树最大高度+1
    x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
    return x;
}

方案2：记录插入深度对比更新全局高度（无需修改Node结构）

如果不想调整Node类的定义，可以在递归插入时传递当前深度，只有插入深度超过当前最大高度时才更新全局height：

private int maxHeight = 0; // 全局存储整棵树的高度

public Node insertRec(Node x, String key, int currentDepth) {
    if (x == null) {
        Node newNode = new Node(key);
        // 仅当新节点深度超过当前最大高度时更新
        if (currentDepth > maxHeight) {
            maxHeight = currentDepth;
        }
        return newNode;
    }
    if (key.compareTo(x.key) < 0) {         
        x.left = insertRec(x.left, key, currentDepth + 1);
    } else if (key.compareTo(x.key) > 0) {
        x.right = insertRec(x.right, key, currentDepth + 1);
    }
    return x;
}

// 对外调用的入口方法，初始深度从1开始（如果按边数定义高度，初始值设为0即可）
public void insert(String key) {
    root = insertRec(root, key, 1);
}

如果需要支持节点删除操作，方案2需要在删除后重新遍历全树计算高度，性能比方案1差很多

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