Я смог написать свое собственное двоичное дерево поиска, но мне трудно понять, как превратить его в дерево сбалансированного двоичного поиска.Включение обычного двоичного дерева поиска в сбалансированное двоичное дерево поиска
Может ли кто-нибудь помочь мне реализовать сбалансированный двоичный код дерева поиска с использованием обычного двоичного дерева.
Я думаю, что мне удалось изменить класс TreeNode, чтобы внести необходимые изменения.
Я добавил еще один ключ и другое значение вместе с другим средним значком TreeNode, чтобы удерживать средний указатель, когда вы попадаете в 3 узла в дереве.
Затем я добавил еще один конструктор для хранения корпуса, если это был 3 узла. Я считаю, что я сделал это правильно.
public class TreeNode<V>
{
public int key;
public int key1;
public V value;
public V value1;
public TreeNode<V> left;
public TreeNode<V> right;
public TreeNode<V> middle;
public TreeNode(int key, V value)
{
this.key = key;
this.value = value;
this.left = null;
this.right = null;
}
public TreeNode(int key, V value, int key1, V value1)
{
this.key = key;
this.key1 = key1;
this.value = value;
this.value1 = value1;
this.left = null;
this.right = null;
this.middle = null;
}
Жесткая часть возникает, когда мне нужно изменить фактический класс BST. Я знаю, что put изменится совсем немного, потому что мы должны проверить и посмотреть, является ли это 2 узла или 3 узла, а также проверить, что такое родительский узел.
Вот то, что я до сих пор:
public class BST<V>
{
private TreeNode<V> root;
public BST()
{
this.root = null;
}
public V get(int key)
{
return get(root, key);
}
private V get(TreeNode<V> current, int key)
{
if (current == null)
return null;
else if (key == current.key)
return current.value;
else if (key < current.key)
return get(current.left, key);
else
return get(current.right, key);
}
public void put(int key, V value)
{
if (root == null)
root = new TreeNode<>(key, value);
else
put(root, key, value);
}
private void put(TreeNode<V> current, int key, V value)
{
if (key == current.key)
{
current.value = value;
return;
}
else if (key < current.key)
{
if (current.left == null)
{
current.left = new TreeNode<>(key, value);
return;
}
else
put(current.left, key, value);
}
else
{
if (current.right == null)
{
current.right = new TreeNode<>(key, value);
return;
}
else
put(current.right, key, value);
}
}
}
Мой трудно приходит большинство с рекурсией. Я понимаю, как работает базовая рекурсия, но использование ее для реализации сбалансированного дерева двоичного поиска выглядит гораздо более трудным, чем первоначально предполагалось.