将二叉搜索树更改为平衡

Question

我刚刚学习了如何创建二进制搜索数据结构，它将用于存储字典中的数千个单词。我遇到的问题是，统计添加和删除数据需要很长时间。通常为199263毫秒或200秒，计算100000个单词。有人告诉我，拥有一棵能够自我平衡的树将提高效率，使操作更快。

我的问题是如何使我的树自动平衡以使其高效。我通过消除重复的单词来使树的高度变短，从而做了一些小小的改进。

如果有人能给我一些建议，告诉我如何使树高效，以及如何在java中实现平衡树，将会很有帮助。

Answer 1

为了平衡二叉树，只需构建一个新的二叉树，以更好的顺序添加元素可能会更容易

BinaryTree balance(BinaryTree tree)
{
    BinaryTree out = new BinaryTree();
    String[] values = tree.toArray(); //a sorted array
    for(int i = Integer.highestOneBit(values.length); i > 0; i >>= 1)
        for(int j = i; j <= values.length; j += i)
            out.add(values[j - 1]);
    return out;
}

通过扩展，如果读入的单词不需要立即放入树中并排序，数组。排序（Object[]）可能会更快

List<String> wordList = new LinkedList<String>();
BufferedReader reader = [...];
for(String line = reader.readLine(); line != null; line = reader.readLine())
    wordList.add(line);
String[] words = wordList.toArray(new String[0]);
Arrays.sort(words);
BinaryTree tree = new BinaryTree();
for(int i = Integer.highestOneBit(words.length); i > 0; i >>= 1)
    for(int j = i; j <= words.length; j += i)
        out.add(words[j - 1]);

取决于您实际使用这些数据的目的（只是一个查找表？）使用哈希集可能会更快

Set<String> dict = new HashSet<String>();
BufferedReader reader = [...];
for(String line = reader.readLine(); line != null; line = reader.readLine())
    dict.add(line);

Answer 2

你应该看看红/黑的树，它们是自我平衡的。节点除存储元素外还存储颜色，每次修改树时，都会重新平衡树，使其符合红/黑树的属性：

（来自维基百科：）

>

根是黑色的。

所有的叶子（无）都是黑色的。

如果一个节点是红色的，那么它的两个子节点都是黑色的。

每一个

为了开始实现红黑树，我建议大家看看github上的这个示例实现，并阅读红黑树的解释。