← 返回目录

队列

第 21 / 24 卷

队列

最经典的应用: MQ, MQ本质就是一个阻塞队列

树

二叉排序树/二叉查找树/二叉搜索树

特点

左孩子 < 根 < 右孩子

对二叉排序树进行中序遍历,可以得到一个升序排列的节点值序列

在二叉排序树中查找一个特定值的节点时,平均时间复杂度为O(logn)

插入操作时,根据节点值的大小关系,从根节点开始比较,找到合适的位置插入新节点,保持二叉排序树的性质不变。插入操作的平均时间复杂度也是O(logn)

删除操作相对复杂一些,但也可以在保持树的性质的前提下完成,平均时间复杂度同样为 O(logn)

平衡二叉树

平衡二叉树一般指平衡二叉排序树,且具有以下性质

  1. 如果不是空树,它的左右两个子树的高度差的绝对值不超过 1
  2. 并且左右两个子树都是一棵平衡二叉树

二叉排序树可能退化为链表,而平衡二叉树不会:普通的二叉排序树在某些极端情况下(如按顺序插入节点)会导致树的高度过大,从而使查找效率降低;而平衡二叉树

通过自动调整树的结构,始终保持树的平衡,树高度不会过高, 保证了操作的高效性

全站分卷索引 · 24 卷
  1. 1计算机基础
  2. 2网络层协议
  3. 3说一下 TCP 粘包是怎么产生的?怎么解决粘包问题的
  4. 4TCP 如何保证可靠性
  5. 5慢开始算法 – Slow Start
  6. 6三次握手
  7. 7HTTP
  8. 8什么是跨域, 如何解决跨域
  9. 9HTTP/2.0和HTTP1.1有什么区别
  10. 10SSL/TLS怎么确保安全通信
  11. 11DNS是什么
  12. 12操作系统
  13. 13进程间的通信方式
  14. 14死锁, 活锁, 饥饿
  15. 15内存管理
  16. 16快表和多级页表
  17. 17CPU 寻址了解吗?为什么需要虚拟(逻辑地址)地址空间?
  18. 18什么是虚拟内存/虚拟存储技术/虚拟存储器
  19. 19请求分页与分页存储管理有何不同呢
  20. 20磁盘和IO
  21. 21队列
  22. 22堆
  23. 23单例模式的应用场景
  24. 24工厂模式