java - 在插入 BST 期间获取实际索引

Question

我想创建一个 BST，它在插入元素时将在完美平衡的树中返回它的索引。例如(括号中的数字表示实际索引):

  5(1)
    / \
   /   \
  3(2)  6(3)
 /
2(4)

或

1(1)
 \
  \
   2(3)
    \
     \
      3(7)

在第二个示例中，我们可以看到元素 1 没有左子元素，但元素 2 的索引仍然为 3，就像完美平衡树中的情况一样。

根节点从1开始。

在插入时返回索引的有效方法是什么？

现在在 BST 中插入一个元素，我的代码如下:

Node newNode = new Node(id);
if(root==null){
            root = newNode;
            return 1;
        }

Node current = root;
        Node parent = null;
        while(true){
            parent = current;
            if(id<current.data){                
                current = current.left;
                if(current==null){
                    parent.left = newNode;
                    return;
                }
            }else{

                current = current.right;
                if(current==null){
                    parent.right = newNode;
                    return;
                }
            }
        }

我无法理解我应该如何维护插入元素的级别以计算索引。

可插入的元素数量最多为 3*10^5。存储在数组中以获取索引不会是一种有效的方法

Answer 1

一种解决方案是将二叉树表示为一维数组。这在二叉堆的实现中很常见。

你的实现不会像堆一样平衡，但你可以使用相同的概念，因为你知道在二叉树中的每个级别 i(从 0 开始为根)都有 2^i 个空格.

您的实现需要从具有左右指针的节点更改为树包含的任何数据类型的一维数组(在您的情况下为整数)。

您可以通过计算索引来导航树:

• 节点 i 的父节点:array[i/2]
• 节点 i 的左子节点:array[2i]
• 节点i的右 child :数组[2i+1]

从http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html获得的信息