深入理解经典红黑树
原文中文，约9300字，阅读约需22分钟。发表于：。本篇我们讲红黑树的经典实现，Java中对红黑树的实现便采用的是经典红黑树。在正文开始之前我们先看如下问题：为什么红黑树比AVL树要应用得更广泛呢？关于红黑树和 AVL 树，大家可能看过“在最坏情况下，AVL 树和红黑树的查找次数都是对数级别的，虽然红黑树的系数更高一些，但是没有本质的区别，是可以容忍的。AVL 树最致命的地方在于删除节点时旋转次数是对数级别的，而红黑树最多只需要 3 次旋转，这导致...
本文介绍了红黑树的经典实现，与2-3-4搜索树同构。红黑树比AVL树应用更广泛的原因是在插入和删除操作混合进行的情况下，红黑树的均摊时间复杂度保持在O(1)，而AVL树的均摊时间复杂度为O(logn)。文章还详细介绍了红黑树的插入和删除节点操作的实现逻辑。红黑树的删除方法的时间复杂度为O(logn)。
