红黑数原理及存在原因

红黑数原理及存在原因"/>

红黑数原理及存在原因

我红黑树那么牛，你们为什么不用？_哔哩哔哩_bilibili

面试时经常会被问到红黑树，它到底有什么优点呢？

对于查找数据，数组二分查询速度最快，时间复杂度为O(logN)。但是如果增加和删除数据，数组就要进行平移，时间复杂度是O(N)。

相比之下，链表的插入和删除就很简单，时间复杂度是O(1)，但是它查询速度慢，时间复杂度为O(N)。

所以就考虑到，能不能找到一种数据结构，即满足查询快，又满足增删快？有，就是二叉搜索树，搜索就是二分查找的思路，小于当前节点的往左子树找，大于节点的往右子树找。增删就通过左右子树增删数据。

但是，如果增加的数据一直挂在右子树或者左子树上，二叉搜索树就变成了一个单链表，查找效率就递减。

这个时候就需要红黑树出场了，它会对如上不平衡的结构进行处理，将一些节点移动到左边，在保证搜索效率的同时，还能保证增删的效率。相当于兼具二者的优势