|
上面的过程已经很清晰了，在查找的时候，先与根节点比较，比根节点大则从右子树查找，比根节点小则从左子树查找，然后重复上面的过程，一直到找到我们需要的元素为止。
这个过程是查找操作，对于添加和删除呢?其实原理也是一样的，我们第一步就是找到我们需要插入的位置，然后把元素插入即可。这样看二叉查找树挺好的呀?别着急我们继续往下看这种情况。
如果我们在刚刚开始的时候还是以9为根节点，然后依次插入13、15、17、19。我们看会发生什么情况：们发现经过调整之后，我们二叉树就重新回到了平衡。对于其他插入的情况，大家可以自己私下试一遍，最终你会发现一个结论，那就是平衡二叉树在插入时最多只需要两次旋转就会重新恢复平衡。
从上面这个过程我们会发现，平衡二叉树真的很不错，在查找时既有着二叉查找树的优越性，在插入时还能通过调整继续保持着。那么为什么还要使用到红黑树呢?我觉得可以从以下两个方面来考虑：
(1)删除：对于平衡二叉树来说，在最坏情况下，需要维护从被删节点到根节点这条路径上所有节点的平衡性，旋转的量级是O(logN)。但是红黑树就不一样了，最多只需3次旋转就会重新平衡，旋转的量级是O(1)。
(2)保持平衡：平衡二叉树高度平衡，这也就意味着在大量插入和删除节点的场景下，平衡二叉树为了保持平衡需要调整的频率会更高。
注意：在大量查找的情况下，平衡二叉树的效率更高，也是首要选择。
在大量增删的情况下，红黑树是首选。
鉴于以上原因，因此我们才使用到了红黑树这种更好的结构。上面提了这么多次红黑树，相信你已经迫不及待的想要认识一下了。下面就正式拉开红黑树的序幕。
三、红黑树
红黑树听名字就知道，里面涉及到两种颜色：红色和黑色。我们直接来看一下：
（编辑：吉安站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
