队列
队列
最经典的应用: MQ, MQ本质就是一个阻塞队列
树
二叉排序树/二叉查找树/二叉搜索树
特点
左孩子 < 根 < 右孩子
对二叉排序树进行中序遍历,可以得到一个升序排列的节点值序列
在二叉排序树中查找一个特定值的节点时,平均时间复杂度为O(logn)
插入操作时,根据节点值的大小关系,从根节点开始比较,找到合适的位置插入新节点,保持二叉排序树的性质不变。插入操作的平均时间复杂度也是O(logn)
删除操作相对复杂一些,但也可以在保持树的性质的前提下完成,平均时间复杂度同样为 O(logn)
平衡二叉树
平衡二叉树一般指平衡二叉排序树,且具有以下性质
- 如果不是空树,它的左右两个子树的高度差的绝对值不超过 1
- 并且左右两个子树都是一棵平衡二叉树
二叉排序树可能退化为链表,而平衡二叉树不会:普通的二叉排序树在某些极端情况下(如按顺序插入节点)会导致树的高度过大,从而使查找效率降低;而平衡二叉树
通过自动调整树的结构,始终保持树的平衡,树高度不会过高, 保证了操作的高效性