包含标签 的文章

一个系列彻底搞懂map(二):红黑树实现

上文讲到了利用哈希结构实现map,除此之外还可以用红黑树实现。相较于hash结构的实现,红黑树实现虽然查找删除的时间复杂度由O(1)退化为O(logN),但却拥有更优的空间效率,同时还提供了对key排序的功能,因此广泛应用于数据库存储领域。

阅读全文

手撕数据结构——平衡二叉树

二叉搜索树提供了平均效率为O(logN)级别的查找、删除、插入操作,但在极端情况下可能导致二叉树退化为单链表。平衡二叉树作为二叉搜索树的一种,通过平衡约束保证左右子树高度相近,能够保证更稳定的性能。本文就从原理出发,最终实现一个操作完备的平衡二叉树。

阅读全文