平衡二叉搜索树

Question

我正在尝试在 Java 中实现二叉搜索树 class，如果存在高度差异，该方法可以重新平衡树。我试图通过首先将节点的值存储在列表中（class 的属性）来实现。

然后我想取这个列表的中间元素并将其分配给树的根。在此之后，我获取列表的左右部分，并递归地对根的左右子节点执行相同的操作，依此类推。

虽然我的算法似乎不起作用，但我不明白我做错了什么。我想知道是否有人可以看一下我的代码并解释问题出在哪里？我所做的基本上是将树元素的有序列表（class 的一个属性）和根传递给下面的函数：

public void build(BinaryNode<E> n,List<E> list) {
    int idx = (int)Math.floor(list.size()/2);
    if(n!=null) {
        n.element = list.get(idx);
    } else if(n==null) {
        n = new BinaryNode<E>(list.get(idx));
    }

    if(!list.subList(0,idx).isEmpty()) {
        build(n.left,list.subList(0,idx));
    } 

    if(!list.subList(idx+1,list.size()).isEmpty() ){
        build(n.right,list.subList(idx+1,list.size()));
    }
    return;
}

亲切的问候，

Answer 1

Java 方法调用是“按值调用”。这意味着更改参数（如 n 在您的情况下）在方法之外没有任何影响。

尝试像这样定义你的方法

public BinaryNode<E> build(List<E> list) { ... }

Answer 2

尝试调查 AVL 树

一些有用的链接： https://en.wikipedia.org/wiki/AVL_tree https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

平衡二叉搜索树

Balance a binary search tree

java

recursion

binary-search-tree