算法 标签

红黑树和平衡二叉树有什么区别? 有更新!

  |   0 评论   |   0 浏览

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

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