Удалить операцию в массиве Двоичное дерево

Question

Я знаю, что вы, ребята, будете жаловаться на повторение этого вопроса снова и снова. Извините, но я не нашел свой ответ в Google/Stackoverflow/Forums ... и т. Д.

Я создаю двоичное дерево Array (это не поиск) на Java.

1) Мой узел имеет атрибуты: родительский, левый и правый. Каковы числа индексов родительского, левого дочернего и правого дочерних элементов. Мой профессор сказал мне сделать это так, я не знаю, почему, потому что вы можете найти индексы родителя и детей с формулой, и я хотел бы, чтобы кто-то сказал мне, как добавлять индексы родительского/левого/правого whould помогите мне в сложности операций.

2) И я просто не могу найти, что должно быть сложностью операции удаления, когда у вас есть указатель на узел в массиве. Я собираюсь переместить все узлы влево при удалении узла. Я думаю, что это O (n), и я не знаю, как его улучшить. Я читал, что некоторые люди выполняют эту операцию с помощью O (log n). Но они не говорят, как это сделать. (Я был бы признателен за любой код кода в Java).

* Имейте в виду, что я работаю с ArrayList с Java.

Некоторый Код:

public class ArrayBinaryTree<E> implements BinaryTree<E> { 
    private class BTPos<T> implements Position<T> { 
     private T element; 
     private int parent; 
     private int left; 
     private int right; 
     private int index; 

     /** Main constructor */ 
     public BTPos(T element, int index, int parent, int left, int right) { 
      setIndex(index); 
      setElement(element); 
      setParent(parent); 
      setLeft(left); 
      setRight(right); 
     } 

     /** Returns the index */ 
     public int getIndex() { 
      return index; 
     } 

     /** Sets the index */ 
     public void setIndex(int i) { 
      index = i; 
     } 

     /** Returns the element stored at this position */ 
     public T getElement() { 
      return element; 
     } 

     /** Sets the element stored at this position */ 
     public void setElement(T o) { 
      element = o; 
     } 

     /** Returns the parent */ 
     public int getParent() { 
      return parent; 
     } 

     /** Sets the index */ 
     public void setParent(int i) { 
      parent = i; 
     } 

     /** Returns the left */ 
     public int getLeft() { 
      return left; 
     } 

     /** Sets the left */ 
     public void setLeft(int i) { 
      left = i; 
     } 

     /** Returns the right */ 
     public int getRight() { 
      return right; 
     } 

     /** Sets the right */ 
     public void setRight(int i) { 
      right = i; 
     } 
    } 
    private List<BTPos<E>> tree; 
    private int size; 
    private final int MAX_SIZE; 

    /** Creates an empty binary tree. */ 
    public ArrayBinaryTree() { 
     this.MAX_SIZE = 100; 
     this.tree = new ArrayList<BTPos<E>>(this.MAX_SIZE); 
     this.size = 0; 
    } 
} 

Answer 1

Ну на 1), имеющий формулу для индексов работает только если у вас есть фиксированный макет. Однако, если у вас нет сбалансированного дерева, это лишний пробел в вашем массиве. На 2) решение delete на O (log n) требует сбалансированного дерева (если не BST - я не уверен). Вы можете найти объяснение, как это сделать с помощью Google;).

Answer 2

1) Наличие индексов родительских/левых/правых, хранящихся в узле, просто уничтожит память, как вы можете в любом случае достичь ее с помощью формулы.

2) Если у вас уже есть указатель на узел, который вы хотите удалить, то для удаления будет сложность O (1), и вы можете просто отметить этот узел специальным символом, обозначив его как удаленный, вместо того чтобы переместить все узлы влево. Таким образом вы можете повторно использовать узел при вставке (также вы не создаете BST, тогда любая вставка может быть выполнена в удаленном узле).