面试真题

结论：跳表是链表+概率索引，红黑树是平衡二叉树；核心差异在结构、区间查询、实现复杂度和并发。要点：1.结构：跳表多层链表，红黑树节点有颜色和左右子节点；2.查找：均为O(log n)，但跳表常数稍大；3.区间查询：跳表定位起点后顺链表扫描，红黑树需树遍历；4.插入删除：跳表改指针，红黑树需旋转重着色；5.内存：跳表额外索引指针（约1/(1-p)倍），红黑树存颜色等；6.并发：跳表易无锁，红黑树难；7.稳定性：红黑树严格平衡，跳表概率平衡。