Создание сбалансированного дерева двоичного поиска
Существует ли метод для создания сбалансированного дерева двоичного поиска?
Пример:
1 2 3 4 5 6 7 8 9
5
/ \
3 etc
/ \
2 4
/
1
Я думаю, что существует метод, чтобы сделать это, не используя более сложные самоуравновешивающиеся деревья. Иначе я могу сделать это самостоятельно, но кто-то, вероятно, уже сделал это :)
Спасибо за ответы! Это - заключительный код Python:
def _buildTree(self, keys):
if not keys:
return None
middle = len(keys) // 2
return Node(
key=keys[middle],
left=self._buildTree(keys[:middle]),
right=self._buildTree(keys[middle + 1:])
)
3 ответа
Для каждого поддерева:
- Найдите средний элемент поддерева и поместите его в верхнюю часть дерева.
- Найдите все элементы перед средним элементом и рекурсивно используйте этот алгоритм, чтобы получить левое поддерево.
- Найдите все элементы после среднего элемента и рекурсивно используйте этот алгоритм, чтобы получить правильное поддерево.
Если вы сначала отсортируете элементы (как в вашем примере), то поиск среднего элемента поддерева может быть выполнен за постоянное время.
Это простой алгоритм построения одноразового сбалансированного дерева. Это не алгоритм для самобалансирующегося дерева.
Вот исходный код на C #, который вы можете попробовать сами:
public class Program
{
class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
}
TreeNode constructBalancedTree(List<int> values, int min, int max)
{
if (min == max)
return null;
int median = min + (max - min) / 2;
return new TreeNode
{
Value = values[median],
Left = constructBalancedTree(values, min, median),
Right = constructBalancedTree(values, median + 1, max)
};
}
TreeNode constructBalancedTree(IEnumerable<int> values)
{
return constructBalancedTree(
values.OrderBy(x => x).ToList(), 0, values.Count());
}
void Run()
{
TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9));
// displayTree(balancedTree); // TODO: implement this!
}
static void Main(string[] args)
{
new Program().Run();
}
}
Сделайте медиану ваших данных (или, точнее, ближайший к медиане элемент в вашем массиве) корнем дерева. И так далее рекурсивно.
В этом документе подробно объясняется:
Ребалансировка дерева в оптимальном времени и пространстве
http://www.eecs.umich.edu/~qstout/abs/CACM86.html
Также здесь:
Одноразовая балансировка дерева двоичного поиска:
Алгоритм Дэй / Стаут / Уоррен (DSW)
http://penguin.ewu.edu/~trolfe/DSWpaper/
Если вы действительно хотите делать это на лету, вам нужен самобалансирующийся дерево.
Если вы просто хотите построить простое дерево, не утруждая себя его балансировкой, просто рандомизируйте элементы, прежде чем вставлять их в дерево.