更改二分搜索树以平衡 [英] Change binary search tree to balance

问题描述

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

I have just learnt how to create a binary search data structure, which is going to be used to store thousands of words from a dictionary. The problem that I am getting is that it is taking a long time to count add and remove data. Usually 199263ms or 200 seconds for 100000 words to count. I was told that having a tree that can self balance will improve the efficiency and make the operations faster.

我的问题是如何使我的树自动平衡，以使其高效.通过消除重复的单词使树的高度更短，我进行了一些改进.

My question is how can I make my tree auto balance so to make it efficient. I have made slight improvements by eliminating duplicate words to make the height of the tree to be shorter.

如果有人可以给我一些建议，以帮助我提高树的效率以及如何在Java中实现平衡树，则将很有帮助.

If someone can give me advice on how i can make the tree efficient and how I can implement balancing tree in java will be helpful.

推荐答案

您应该查看具有自平衡功能的红色/黑色树.节点除了存储元素之外还存储颜色，并且每次修改树时，都需要重新平衡树，使其符合红色/黑色树的属性:

You should look into red/black trees, which are self balancing. The nodes store a color in addition to an element, and every time the tree is modified, you rebalance the tree so that it meets the properties of a red/black tree:

(来自维基百科:)

1. 每个节点为红色或黑色.

1. Each node is either red or black.

根是黑色的.

所有叶子(NIL)都是黑色的.

All leaves (NIL) are black.

如果节点为红色，则其两个子节点均为黑色.

If a node is red, then both its children are black.

从给定节点到其任何后代NIL节点的每条路径 包含相同数量的黑色节点.

Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

要开始实施一棵红黑树，我建议您查看此示例实现，并阅读对红黑树的解释.

To get started implementing a red black tree, I recommend looking at this example implementation on github, and reading this explanation of red black trees.

这篇关于更改二分搜索树以平衡的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！