Двоичное дерево индексов в java

Я изучаю, как реализовать двоичное дерево индексов. Как мне следует строить двоичное дерево с набором строк в качестве моего ввода? Я считаю, что две структуры данных 1) регулярное бинарное дерево - где мы Симметричного postorder 2) Бинарные индексного дереваДвоичное дерево индексов в java

public static void main(String[] args) 
{ 
    String[] docs = {"The idea is that all are strings", 
        "position of the node is considered", 
        "Being positive helps", 
        "I want to learn then add and search in the tree" 
        }; 
}

Bstnode

public class BSTNode 
{ 
private String key; 
private Object value; 
private BSTNode left, right; 

public BSTNode(String key, Object value) 
{ 
    this.key = key; 
    this.value = value; 
} 

//if key not found in BST then it is added. If jey already exists then that node's value 
//is updated. 
public void put(String key, Object value) 
{ 
    if (key.compareTo(this.key) < 0)   
    {    
     if (left != null)    
     {     
      left.put(key, value);    
     }    
     else    
     {     
      left = new BSTNode(key, value);    
     }   
    }   
    else if (key.compareTo(this.key) > 0) 
    { 
     if (right != null) 
     { 
      right.put(key, value); 
     } 
     else 
     { 
      right = new BSTNode(key, value); 
     } 
    } 
    else 
    { 
     //update this one 
     this.value = value; 
    } 
} 

//find Node with given key and return it's value 
public Object get(String key) 
{ 
    if (this.key.equals(key)) 
    { 
     return value; 
    } 

    if (key.compareTo(this.key) < 0) 
    { 
     return left == null ? null : left.get(key); 
    } 
    else 
    { 
     return right == null ? null : right.get(key); 
    } 
}

}

Пожалуйста, дайте мне знать хороший учебник или начать строить двоичное индексированное дерево.

источник

2016-05-11 shockwave

Попробуйте этот учебник https://www.youtube.com/watch?v=CWDQJGaN1gY – 11thdimension

Примечание: [бинарные индексные деревья] (https: //en.wikipedia. org/wiki/Fenwick_tree) или BIT (также известные как деревья Фенвика) имеют мало или ничего общего с бинарными деревьями поиска (aka BST); они используются для целей, например, для эффективного запроса текущей суммы в данной точке/узле или суммы по заданному диапазону. Как таковые, эти звери полностью отличаются от бинарных деревьев поиска. IOW, двоичное дерево поиска не является двоичным деревом индексов *, даже если оно используется как некоторый индекс. – DarthGizka

Trees и Lists должно быть общим на Java. Нет никакого смысла ограничивать себя Strings.

Любая хорошая книга по структурам данных даст вам хорошее начало.

Я сделал это на Java. Вы можете источник:

https://github.com/duffymo

источник

2016-05-11 18:21:21 duffymo

Двоичное дерево индексов в java

ответ

Смежные вопросы