参考答案
内容深度:基础 · 无代码示例 · 来源:种子题库 · 未复核 · 89 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
- 二叉树:每个节点最多两子,通用结构。
- BST:左<根<右,查找 O(h)(h 为树高),但有序插入会退化成链表(O(n))。
- 平衡二叉树(AVL):左右子树高度差 ≤1,严格平衡,查找极快但插入删除旋转多。
- 红黑树:弱平衡(黑高平衡,最长路径≤2倍最短),插入删除旋转少,综合更优,是工程首选(Java TreeMap/HashMap 树化、C++ map、 epoll)。
演进动机:在“查找快”与“增删代价”间取舍,红黑树折中最实用。