2020 年 07 月 - 8 文章

红黑树和平衡二叉树有什么区别？ 有更新！

  |   0 评论   |   0 浏览

本节内容会介绍二叉树、二叉查找树及红黑树的概念，还有红黑树的五个特性。

普通二叉查找树在特殊情况下会退化成链表的数据结构，因此操作和查询的时间复杂度变成了 O(n)，而红黑树可以实现自平衡，因此它的操作（插入、删除）和查找的时间复杂度都是 O(logn)，效率更高更稳定，红黑树保证平衡的手段有三个：变色、左旋和右旋。