Код Java для 2-4 сбалансированного узла дерева поиска?

Question

Может ли кто-нибудь показать мне базовую структуру узла 2,3,4 balanced search tree в Java? Я не уверен, как представить 3 ключевых узла. Должен ли я использовать массив размером три? Или я должен иметь левую запись (entry = key + value object), средние и правые поля ввода?

И как работает левый ребенок и правый ребенок? В двоичном дереве поиска левый и правый дочерние элементы для узла. В дереве 2,3,4 левый и правый дети кажутся для каждого ключа. Итак, должен ли сам узел 2,3,4 дерева быть объектом, который содержит 3 узла двоичного дерева, вместо того, чтобы удерживать 3 записи?

Answer 1

Опция «традиционный OO» с отдельными классами для 4-х вариантов узла (0 для листьев, 2, 3 или 4 детей в противном случае) неудобна, потому что ссылки на узел затем должны быть обновлены, что приведет к для хранения обратной ссылки на родителя и обновления родителя при каждом изменении числа детей.

Вместо этого, он кажется гораздо более простым и производительным, чтобы сломать «состояние влияет на поведение, а не подкласса» анти-шаблон и использовать LinkedLists для обоих значений и дочерних узлов:

public class Node<T> { 
    LinkedList<Node<T>> children = new LinkedList<>(); 
    LinkedList<T> values = new LinkedList<>(); 

    public Node(T value) { 
     values.add(value); // there is always a value 
    } 
    // other methods to find, insert, delete, etc 
} 

Используя LinkedList дает вы постоянное время (т.е. O(1) временная сложность) для всех операций (хотя n = 4 мало, все же каждый бит помогает), возможность итерации без итератора через next(), который необходим для итератора, удобно по обоим спискам одновременно, и более удобный API для балансировки.