java - 迭代存储为无序数组的二叉搜索树(BST)的最快方法？

Question

我有一个 BST，它存储为数组。

例如，树可能如下所示

        4
     /    \
    2      6
   / \   /  \
  1   3  5  7

作为数组，该树将存储为 [4, 2, 6, 1, 3, 5, 7, null 等]

我需要实现一种方法来在O(log(n))时间内查找值的索引。问题是，这个数组未排序，这意味着我无法实现二分搜索。

解决方案是什么样的？

我已经迭代了所有元素，并找到了一种查找索引的方法，但它是 O(n)，这不是所需要的。

public class Item<A extends Comparable<? super A>>
{
protected A[] items;

public Item
    {
      //Code to construct array of size 10. 
    }

public int index(A value)
{
for (int i=0; i < items.length; i++) {
 //Method to iterate through array element by element. Time complexity of O(n).
}
}

}

这是示例代码。

谢谢。

Answer 1

听起来索引 i 处的元素的元素左右链接将是 2*i+1 和 2*(i+1) 。您可以使用与常规 BST 相同的算法:

public int index(A value)
{
    for (int i=0; i < items.length; ) {
        if (items[i] == null) {
            return -1;
        }
        int r = value.compareTo(items[i]);
        if (r < 0) {
            i = 2*i+1;
        } else if (r > 0) {
            i = 2*(i+1);
        } else {
            return i;
        }
    }
    return -1;
}