Поиск в двоичном дереве генерирует исключение StackOverflowException - PullRequest
Новая
       4

Поиск в двоичном дереве генерирует исключение StackOverflowException

0 голосов
/ 24 сентября 2018

Я создал двоичное дерево для поиска лучшего префикса для телефонного номера, но когда у меня самый большой список префиксов, следующий код иногда генерирует StackOverflowException для функции StartsWith ().

BTreeNode.cs 

public class BTreeNode<T>
{
    public BTreeNode(T item)
    {
        this.Item = item;
    }

    public T Item { get; set; }
    public BTreeNode<T> Left { get; set; }
    public BTreeNode<T> Right { get; set; }
}

BTree.cs 

public class BTree
{
    public BTreeNode<string> Root { get; set; }

    public BTree(IEnumerable<string> enumerable)
    {
        if (enumerable == null)
        {
            throw new ArgumentNullException(nameof(enumerable));
        }

        using (IEnumerator<string> enumerator = enumerable.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                AddNode(enumerator.Current);
            }
        }
    }

    public void AddNode(string key)
    {
        if (Root == null)
        {
            Root = new BTreeNode<string>(key);
        }
        else
        {
            AddNode(key, Root);
        }
    }

    private void AddNode(string key, BTreeNode<string> current)
    {
        if (key.StartsWith(current.Item))
        {
            if (current.Left == null)
            {
                current.Left = new BTreeNode<string>(key);
            }
            else
            {
                AddNode(key, current.Left);
            }
        }
        else
        {
            if (current.Right == null)
            {
                current.Right = new BTreeNode<string>(key);
            }
            else
            {
                AddNode(key, current.Right);
            }
        }
    }

    public string Search(string key)
    {
        if (Root == null)
        {
            return null;
        }

        return Search(key, Root, null);
    }

    private string Search(string key, BTreeNode<string> current, BTreeNode<string> match)
    {
        if (current != null)
        {
            if (current.Left != null)
            {
                if (key.StartsWith(current.Left.Item))
                {
                    return Search(key, current.Left, current.Left);
                }
            }
            if (current.Right != null)
            {
                if (key.StartsWith(current.Item))
                {
                    return Search(key, current.Left, current);
                }

                if (key.Length >= current.Right.Item.Length)
                {
                    if (long.Parse(key) >= long.Parse(current.Right.Item))
                    {
                        return Search(key, current.Right, match);
                    }
                }
            }
            else
            {
                if (key.StartsWith(current.Item))
                {
                    return Search(key, current.Left, current);
                }
            }
        }

        return match?.Item;
    }
}

Данные выборки

Исключение StackOverflowException, например, при поиске в цикле всех данных выборки, которыея загружаю в двоичное дерево.

Любое решение?

1 Ответ

0 голосов
/ 24 сентября 2018

Я не вижу механизма для балансировки этого дерева, поэтому при импорте большого количества данных некоторые дочерние ветви могут стать очень длинными.Возможно даже, что все дерево представляет собой одну линейную ветвь и не разбивается на несколько ветвей, особенно если упорядочен список с образцами данных.

Еще несколько улучшенных деревьев, например красно-черное дерево,иметь встроенный механизм для поддержания сбалансированного дерева.

У вас есть 35000 элементов, что означает, что идеально сбалансированное дерево должно быть не глубже, чем что-то около 15. (2 ^ 15 = 32768).Но когда дерево полностью несбалансировано, у вас есть одна очень длинная ветвь, которая почти совпадает с односвязным списком из 35000 элементов, доступ к которым осуществляется рекурсивно.

...