写作目的:
本博客旨在了解并回顾数据结构中涉及的平衡二叉树与红黑树,同时探讨基于红黑树实现的TreeSet和TreeMap。
1.二叉搜索树的弊端
二叉搜索树在执行查找、插入及删除操作时,其时间复杂度取决于树的高度,通常为O(log(n))。然而,同一组数据在不同插入顺序的影响下,可能导致二叉搜索树的高度发生变化。若采用有序方式插入数据,则该结构可能退化为链表形式,从而使得查找操作的时间复杂度上升至O(n)。
图 插入顺序不同对二叉搜索树的影响
2.平衡二叉树(AVL树)
[维基百科]:在计算机科学中,AVL树是最早被提出的一种自平衡二叉查找树。在AVL树中,