Java学习指南
  • Java 编程的逻辑
  • Java进阶
  • Java FrameWorks
  • 了解 USB Type-A,B,C 三大标准接口
  • 深入浅出DDD
  • 重构:改善既有代码的设计
  • 面试大纲
  • 云原生
    • 什么是无服务器(what is serverless)?
  • 博客
    • 深入分析Log4j 漏洞
  • 博客
    • Serverless之快速搭建Spring Boot应用
  • 博客
    • 使用 Prometheus + Grafana + Spring Boot Actuator 监控应用
  • 博客
    • 使用 Prometheus + Grafana 监控 MySQL
  • 博客
    • 使用Github Actions + Docker 部署Spring Boot应用
  • 博客
    • Redis分布式锁之Redisson的原理和实践
  • 博客
    • 数据库中的树结构应该怎样去设计
  • 学习&成长
    • 如何成为技术大牛
  • 开发工具
    • Git Commit Message Guidelines
  • 开发工具
    • git命名大全
  • 开发工具
    • Gradle vs Maven Comparison
  • 开发工具
    • Swagger2常用注解及其说明
  • 开发工具
    • 简明 VIM 练级攻略
  • 微服务
    • 十大微服务设计模式和原则
  • 微服务
    • 微服务下的身份认证和令牌管理
  • 微服务
    • 微服务坏味道之循环依赖
  • 设计模式
    • 设计模式 - JDK中的设计模式
  • 设计模式
    • 设计模式 - Java三种代理模式
  • 设计模式
    • 设计模式 - 六大设计原则
  • 设计模式
    • 设计模式 - 单例模式
  • 设计模式
    • 设计模式 - 命名模式
  • 设计模式
    • 设计模式 - 备忘录模式
  • 设计模式
    • 设计模式 - 概览
  • 设计模式
    • 设计模式 - 没用的设计模式
  • 质量&效率
    • Homebrew 替换国内镜像源
  • 质量&效率
    • 工作中如何做好技术积累
  • Java FrameWorks
    • Logback
      • 自定义 logback 日志过滤器
  • Java FrameWorks
    • Mybatis
      • MyBatis(十三) - 整合Spring
  • Java FrameWorks
    • Mybatis
      • MyBatis(十二) - 一些API
  • Java FrameWorks
    • Mybatis
      • Mybatis(一) - 概述
  • Java FrameWorks
    • Mybatis
      • Mybatis(七) - 结果集的封装与映射
  • Java FrameWorks
    • Mybatis
      • Mybatis(三) - mapper.xml及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(九) - 事务
  • Java FrameWorks
    • Mybatis
      • Mybatis(二) - 全局配置文件及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(五) - SqlSession执行流程
  • Java FrameWorks
    • Mybatis
      • Mybatis(八) - 缓存
  • Java FrameWorks
    • Mybatis
      • Mybatis(六) - 动态SQL的参数绑定与执行
  • Java FrameWorks
    • Mybatis
      • Mybatis(十) - 插件
  • Java FrameWorks
    • Mybatis
      • Mybatis(十一) - 日志
  • Java FrameWorks
    • Mybatis
      • Mybatis(四) - Mapper接口解析
  • Java FrameWorks
    • Netty
      • Netty 可靠性分析
  • Java FrameWorks
    • Netty
      • Netty - Netty 线程模型
  • Java FrameWorks
    • Netty
      • Netty堆外内存泄露排查盛宴
  • Java FrameWorks
    • Netty
      • Netty高级 - 高性能之道
  • Java FrameWorks
    • Shiro
      • Shiro + JWT + Spring Boot Restful 简易教程
  • Java FrameWorks
    • Shiro
      • 非常详尽的 Shiro 架构解析!
  • Java FrameWorks
    • Spring
      • Spring AOP 使用介绍,从前世到今生
  • Java FrameWorks
    • Spring
      • Spring AOP 源码解析
  • Java FrameWorks
    • Spring
      • Spring Event 实现原理
  • Java FrameWorks
    • Spring
      • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC容器源码分析
  • Java FrameWorks
    • Spring
      • Spring Integration简介
  • Java FrameWorks
    • Spring
      • Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • Spring bean 解析、注册、实例化流程源码剖析
  • Java FrameWorks
    • Spring
      • Spring validation中@NotNull、@NotEmpty、@NotBlank的区别
  • Java FrameWorks
    • Spring
      • Spring 如何解决循环依赖?
  • Java FrameWorks
    • Spring
      • Spring 异步实现原理与实战分享
  • Java FrameWorks
    • Spring
      • Spring中的“for update”问题
  • Java FrameWorks
    • Spring
      • Spring中的设计模式
  • Java FrameWorks
    • Spring
      • Spring事务失效的 8 大原因
  • Java FrameWorks
    • Spring
      • Spring事务管理详解
  • Java FrameWorks
    • Spring
      • Spring计时器StopWatch使用
  • Java FrameWorks
    • Spring
      • 详述 Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • 透彻的掌握 Spring 中@transactional 的使用
  • Java
    • Java IO&NIO&AIO
      • Java IO - BIO 详解
  • Java
    • Java IO&NIO&AIO
      • Java NIO - IO多路复用详解
  • Java
    • Java IO&NIO&AIO
      • Java N(A)IO - Netty
  • Java
    • Java IO&NIO&AIO
      • Java IO - Unix IO模型
  • Java
    • Java IO&NIO&AIO
      • Java IO - 分类
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 基础详解
  • Java
    • Java IO&NIO&AIO
      • Java IO - 常见类使用
  • Java
    • Java IO&NIO&AIO
      • Java AIO - 异步IO详解
  • Java
    • Java IO&NIO&AIO
      • Java IO概述
  • Java
    • Java IO&NIO&AIO
      • Java IO - 设计模式
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 零拷贝实现
  • Java
    • Java JVM
      • JVM 优化经验总结
  • Java
    • Java JVM
      • JVM 内存结构
  • Java
    • Java JVM
      • JVM参数设置
  • Java
    • Java JVM
      • Java 内存模型
  • Java
    • Java JVM
      • 从实际案例聊聊Java应用的GC优化
  • Java
    • Java JVM
      • Java 垃圾回收器G1详解
  • Java
    • Java JVM
      • 垃圾回收器Shenandoah GC详解
  • Java
    • Java JVM
      • 垃圾回收器ZGC详解
  • Java
    • Java JVM
      • 垃圾回收基础
  • Java
    • Java JVM
      • 如何优化Java GC
  • Java
    • Java JVM
      • 类加载机制
  • Java
    • Java JVM
      • 类字节码详解
  • Java
    • Java 基础
      • Java hashCode() 和 equals()
  • Java
    • Java 基础
      • Java 基础 - Java native方法以及JNI实践
  • Java
    • Java 基础
      • Java serialVersionUID 有什么作用?
  • Java
    • Java 基础
      • Java 泛型的类型擦除
  • Java
    • Java 基础
      • Java 基础 - Unsafe类解析
  • Java
    • Java 基础
      • Difference Between Statement and PreparedStatement
  • Java
    • Java 基础
      • Java 基础 - SPI机制详解
  • Java
    • Java 基础
      • Java 基础 - final
  • Java
    • Java 基础
      • Java中static关键字详解
  • Java
    • Java 基础
      • 为什么说Java中只有值传递?
  • Java
    • Java 基础
      • Java 基础 - 即时编译器原理解析及实践
  • Java
    • Java 基础
      • Java 基础 - 反射
  • Java
    • Java 基础
      • Java多态的面试题
  • Java
    • Java 基础
      • Java 基础 - 异常机制详解
  • Java
    • Java 基础
      • 为什么要有抽象类?
  • Java
    • Java 基础
      • 接口的本质
  • Java
    • Java 基础
      • Java 基础 - 枚举
  • Java
    • Java 基础
      • Java 基础 - 泛型机制详解
  • Java
    • Java 基础
      • Java 基础 - 注解机制详解
  • Java
    • Java 基础
      • 为什么 String hashCode 方法选择数字31作为乘子
  • Java
    • Java 并发
      • Java 并发 - 14个Java并发容器
  • Java
    • Java 并发
      • Java 并发 - AQS
  • Java
    • Java 并发
      • Java 并发 - BlockingQueue
  • Java
    • Java 并发
      • Java 并发 - CAS
  • Java
    • Java 并发
      • Java 并发 - Condition接口
  • Java
    • Java 并发
      • Java 并发 - CopyOnWriteArrayList
  • Java
    • Java 并发
      • Java 并发 - CountDownLatch、CyclicBarrier和Phaser对比
  • Java
    • Java 并发
      • Java 并发 - Fork&Join框架
  • Java
    • Java 并发
      • Java 并发 - Java CompletableFuture 详解
  • Java
    • Java 并发
      • Java 并发 - Java 线程池
  • Java
    • Java 并发
      • Java 并发 - Lock接口
  • Java
    • Java 并发
      • Java 并发 - ReentrantLock
  • Java
    • Java 并发
      • Java 并发 - ReentrantReadWriteLock
  • Java
    • Java 并发
      • Java 并发 - Synchronized
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal 内存泄漏问题
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal
  • Java
    • Java 并发
      • Java 并发 - Volatile
  • Java
    • Java 并发
      • Java 并发 - 从ReentrantLock的实现看AQS的原理及应用
  • Java
    • Java 并发
      • Java 并发 - 公平锁和非公平锁
  • Java
    • Java 并发
      • Java 并发 - 内存模型
  • Java
    • Java 并发
      • Java 并发 - 原子类
  • Java
    • Java 并发
      • Java 并发 - 如何确保三个线程顺序执行?
  • Java
    • Java 并发
      • Java 并发 - 锁
  • Java
    • Java 的新特性
      • Java 10 新特性概述
  • Java
    • Java 的新特性
      • Java 11 新特性概述
  • Java
    • Java 的新特性
      • Java 12 新特性概述
  • Java
    • Java 的新特性
      • Java 13 新特性概述
  • Java
    • Java 的新特性
      • Java 14 新特性概述
  • Java
    • Java 的新特性
      • Java 15 新特性概述
  • Java
    • Java 的新特性
      • Java 8的新特性
  • Java
    • Java 的新特性
      • Java 9 新特性概述
  • Java
    • Java 调试排错
      • 调试排错 - Java Debug Interface(JDI)详解
  • Java
    • Java 调试排错
      • 调试排错 - CPU 100% 排查优化实践
  • Java
    • Java 调试排错
      • 调试排错 - Java Heap Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java Thread Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java动态调试技术原理
  • Java
    • Java 调试排错
      • 调试排错 - Java应用在线调试Arthas
  • Java
    • Java 调试排错
      • 调试排错 - Java问题排查:工具单
  • Java
    • Java 调试排错
      • 调试排错 - 内存溢出与内存泄漏
  • Java
    • Java 调试排错
      • 调试排错 - 在线分析GC日志的网站GCeasy
  • Java
    • Java 调试排错
      • 调试排错 - 常见的GC问题分析与解决
  • Java
    • Java 集合
      • Java 集合 - ArrayList
  • Java
    • Java 集合
      • Java 集合 - HashMap 和 ConcurrentHashMap
  • Java
    • Java 集合
      • Java 集合 - HashMap的死循环问题
  • Java
    • Java 集合
      • Java 集合 - LinkedHashSet&Map
  • Java
    • Java 集合
      • Java 集合 - LinkedList
  • Java
    • Java 集合
      • Java 集合 - PriorityQueue
  • Java
    • Java 集合
      • Java 集合 - Stack & Queue
  • Java
    • Java 集合
      • Java 集合 - TreeSet & TreeMap
  • Java
    • Java 集合
      • Java 集合 - WeakHashMap
  • Java
    • Java 集合
      • Java 集合 - 为什么HashMap的容量是2的幂次方
  • Java
    • Java 集合
      • Java 集合 - 概览
  • Java
    • Java 集合
      • Java 集合 - 高性能队列Disruptor详解
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo&hsf&Spring cloud的区别
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo的架构原理
  • 分布式
    • RPC
      • ⭐️RPC - HSF的原理分析
  • 分布式
    • RPC
      • ⭐️RPC - 你应该知道的RPC原理
  • 分布式
    • RPC
      • ⭐️RPC - 动态代理
  • 分布式
    • RPC
      • 深入理解 RPC 之协议篇
  • 分布式
    • RPC
      • RPC - 序列化和反序列化
  • 分布式
    • RPC
      • ⭐️RPC - 服务注册与发现
  • 分布式
    • RPC
      • RPC - 核心原理
  • 分布式
    • RPC
      • ⭐️RPC - 框架对比
  • 分布式
    • RPC
      • ⭐️RPC - 网络通信
  • 分布式
    • 分布式事务
      • 分布式事务 Seata TCC 模式深度解析
  • 分布式
    • 分布式事务
      • 分布式事务的实现原理
  • 分布式
    • 分布式事务
      • 常用的分布式事务解决方案
  • 分布式
    • 分布式事务
      • 手写实现基于消息队列的分布式事务框架
  • 分布式
    • 分布式算法
      • CAP 定理的含义
  • 分布式
    • 分布式算法
      • Paxos和Raft比较
  • 分布式
    • 分布式算法
      • 分布式一致性与共识算法
  • 分布式
    • 分布式锁
      • ⭐️分布式锁的原理及实现方式
  • 分布式
    • 搜索引擎
      • ElasticSearch与SpringBoot的集成与JPA方法的使用
  • 分布式
    • 搜索引擎
      • 全文搜索引擎 Elasticsearch 入门教程
  • 分布式
    • 搜索引擎
      • 十分钟学会使用 Elasticsearch 优雅搭建自己的搜索系统
  • 分布式
    • 搜索引擎
      • 腾讯万亿级 Elasticsearch 技术解密
  • 分布式
    • 日志系统
      • Grafana Loki 简明教程
  • 分布式
    • 日志系统
      • 分布式系统中如何优雅地追踪日志
  • 分布式
    • 日志系统
      • 如何优雅地记录操作日志?
  • 分布式
    • 日志系统
      • 日志收集组件—Flume、Logstash、Filebeat对比
  • 分布式
    • 日志系统
      • 集中式日志系统 ELK 协议栈详解
  • 分布式
    • 消息队列
      • 消息队列 - Kafka
  • 分布式
    • 消息队列
      • 消息队列 - Kafka、RabbitMQ、RocketMQ等消息中间件的对比
  • 分布式
    • 消息队列
      • 消息队列之 RabbitMQ
  • 分布式
    • 消息队列
      • 消息队列 - 使用docker-compose构建kafka集群
  • 分布式
    • 消息队列
      • 消息队列 - 分布式系统与消息的投递
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的可靠性传输
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的顺序性
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息队列的高可用
  • 分布式
    • 消息队列
      • 消息队列 - 消息队列设计精要
  • 分布式
    • 监控系统
      • 深度剖析开源分布式监控CAT
  • 大数据
    • Flink
      • Flink架构与核心组件
  • 微服务
    • Dubbo
      • 基于dubbo的分布式应用中的统一异常处理
  • 微服务
    • Dubbo
      • Vim快捷键
  • 微服务
    • Service Mesh
      • Istio 是什么?
  • 微服务
    • Service Mesh
      • OCTO 2.0:美团基于Service Mesh的服务治理系统详解
  • 微服务
    • Service Mesh
      • Service Mesh是什么?
  • 微服务
    • Service Mesh
      • Spring Cloud向Service Mesh迁移
  • 微服务
    • Service Mesh
      • 数据挖掘算法
  • 微服务
    • Service Mesh
      • Seata Saga 模式
  • 微服务
    • Spring Cloud
      • Seata TCC 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Config
  • 微服务
    • Spring Cloud
      • Seata AT 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Gateway
  • 微服务
    • Spring Cloud
      • Spring Cloud OpenFeign 的核心原理
  • 微服务
    • Spring Cloud
      • Seata XA 模式
  • 数据库
    • Database Version Control
      • Liquibase vs. Flyway
  • 数据库
    • Database Version Control
      • Six reasons to version control your database
  • 数据库
    • MySQL
      • How Sharding Works
  • 数据库
    • MySQL
      • MySQL InnoDB中各种SQL语句加锁分析
  • 数据库
    • MySQL
      • MySQL 事务隔离级别和锁
  • 数据库
    • MySQL
      • MySQL 索引性能分析概要
  • 数据库
    • MySQL
      • MySQL 索引设计概要
  • 数据库
    • MySQL
      • MySQL出现Waiting for table metadata lock的原因以及解决方法
  • 数据库
    • MySQL
      • MySQL的Limit性能问题
  • 数据库
    • MySQL
      • MySQL索引优化explain
  • 数据库
    • MySQL
      • MySQL索引背后的数据结构及算法原理
  • 数据库
    • MySQL
      • MySQL行转列、列转行问题
  • 数据库
    • MySQL
      • 一条SQL更新语句是如何执行的?
  • 数据库
    • MySQL
      • 一条SQL查询语句是如何执行的?
  • 数据库
    • MySQL
      • 为什么 MySQL 使用 B+ 树
  • 数据库
    • MySQL
      • 为什么 MySQL 的自增主键不单调也不连续
  • 数据库
    • MySQL
      • 为什么我的MySQL会“抖”一下?
  • 数据库
    • MySQL
      • 为什么数据库不应该使用外键
  • 数据库
    • MySQL
      • 为什么数据库会丢失数据
  • 数据库
    • MySQL
      • 事务的可重复读的能力是怎么实现的?
  • 数据库
    • MySQL
      • 大众点评订单系统分库分表实践
  • 数据库
    • MySQL
      • 如何保证缓存与数据库双写时的数据一致性?
  • 数据库
    • MySQL
      • 浅谈数据库并发控制 - 锁和 MVCC
  • 数据库
    • MySQL
      • 深入浅出MySQL 中事务的实现
  • 数据库
    • MySQL
      • 浅入浅出MySQL 和 InnoDB
  • 数据库
    • PostgreSQL
      • PostgreSQL upsert功能(insert on conflict do)的用法
  • 数据库
    • Redis
      • Redis GEO & 实现原理深度分析
  • 数据库
    • Redis
      • Redis 和 I/O 多路复用
  • 数据库
    • Redis
      • Redis分布式锁
  • 数据库
    • Redis
      • Redis实现分布式锁中的“坑”
  • 数据库
    • Redis
      • Redis总结
  • 数据库
    • Redis
      • 史上最全Redis高可用技术解决方案大全
  • 数据库
    • Redis
      • Redlock:Redis分布式锁最牛逼的实现
  • 数据库
    • Redis
      • 为什么 Redis 选择单线程模型
  • 数据库
    • TiDB
      • 新一代数据库TiDB在美团的实践
  • 数据库
    • 数据仓库
      • 实时数仓在有赞的实践
  • 数据库
    • 数据库原理
      • OLTP与OLAP的关系是什么?
  • 数据库
    • 数据库原理
      • 为什么 OLAP 需要列式存储
  • 系统设计
    • DDD
      • Domain Primitive
  • 系统设计
    • DDD
      • Repository模式
  • 系统设计
    • DDD
      • 应用架构
  • 系统设计
    • DDD
      • 聊聊如何避免写流水账代码
  • 系统设计
    • DDD
      • 领域层设计规范
  • 系统设计
    • DDD
      • 从三明治到六边形
  • 系统设计
    • DDD
      • 阿里盒马领域驱动设计实践
  • 系统设计
    • DDD
      • 领域驱动设计(DDD)编码实践
  • 系统设计
    • DDD
      • 领域驱动设计在互联网业务开发中的实践
  • 系统设计
    • 基础架构
      • 容错,高可用和灾备
  • 系统设计
    • 数据聚合
      • GraphQL及元数据驱动架构在后端BFF中的实践
  • 系统设计
    • 数据聚合
      • 高效研发-闲鱼在数据聚合上的探索与实践
  • 系统设计
    • 服务安全
      • JSON Web Token 入门教程
  • 系统设计
    • 服务安全
      • 你还在用JWT做身份认证嘛?
  • 系统设计
    • 服务安全
      • 凭证(Credentials)
  • 系统设计
    • 服务安全
      • 授权(Authorization)
  • 系统设计
    • 服务安全
      • 理解OAuth2.0
  • 系统设计
    • 服务安全
      • 认证(Authentication)
  • 系统设计
    • 架构案例
      • 微信 Android 客户端架构演进之路
  • 系统设计
    • 高可用架构
      • 业务高可用的保障:异地多活架构
  • 计算机基础
    • 字符编码
      • Base64原理解析
  • 计算机基础
    • 字符编码
      • 字符编码笔记:ASCII,Unicode 和 UTF-8
  • 计算机基础
    • 操作系统
      • 为什么 CPU 访问硬盘很慢
  • 计算机基础
    • 操作系统
      • 为什么 HTTPS 需要 7 次握手以及 9 倍时延
  • 计算机基础
    • 操作系统
      • 为什么 Linux 默认页大小是 4KB
  • 计算机基础
    • 操作系统
      • 磁盘IO那些事
  • 计算机基础
    • 操作系统
      • 虚拟机的3种网络模式
  • 计算机基础
    • 服务器
      • mac终端bash、zsh、oh-my-zsh最实用教程
  • 计算机基础
    • 服务器
      • Nginx强制跳转Https
  • 计算机基础
    • 服务器
      • curl 的用法指南
  • 计算机基础
    • 网络安全
      • 如何设计一个安全的对外接口?
  • 计算机基础
    • 网络安全
      • 浅谈常见的七种加密算法及实现
  • 计算机基础
    • 网络编程
      • MQTT - The Standard for IoT Messaging
  • 计算机基础
    • 网络编程
      • 两万字长文 50+ 张趣图带你领悟网络编程的内功心法
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有 TIME_WAIT 状态
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有性能问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有粘包问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 建立连接需要三次握手
  • 计算机基础
    • 网络编程
      • 为什么 TCP/IP 协议会拆分数据
  • 计算机基础
    • 网络编程
      • 使用 OAuth 2 和 JWT 为微服务提供安全保障
  • 计算机基础
    • 网络编程
      • 四种常见的 POST 提交数据方式
  • 计算机基础
    • 网络编程
      • 有赞TCP网络编程最佳实践
  • 计算机基础
    • 网络编程
      • 看完这篇HTTP,跟面试官扯皮就没问题了
  • 计算机基础
    • 网络编程
      • 详细解析 HTTP 与 HTTPS 的区别
  • 质量&效率
    • 快捷键
      • Idea快捷键(Mac版)
  • 质量&效率
    • 快捷键
      • Shell快捷键
  • 质量&效率
    • 快捷键
      • conduit
  • 质量&效率
    • 敏捷开发
      • Scrum的3种角色
  • 质量&效率
    • 敏捷开发
      • Scrum的4种会议
  • 质量&效率
    • 敏捷开发
      • ThoughtWorks的敏捷开发
  • 质量&效率
    • 敏捷开发
      • 敏捷开发入门教程
  • 运维&测试
    • Docker
      • Docker (容器) 的原理
  • 运维&测试
    • Docker
      • Docker Compose:链接外部容器的几种方式
  • 运维&测试
    • Docker
      • Docker 入门教程
  • 运维&测试
    • Docker
      • Docker 核心技术与实现原理
  • 运维&测试
    • Docker
      • Dockerfile 最佳实践
  • 运维&测试
    • Docker
      • Docker开启Remote API 访问 2375端口
  • 运维&测试
    • Docker
      • Watchtower - 自动更新 Docker 镜像与容器
  • 运维&测试
    • Kubernetes
      • Kubernetes 介绍
  • 运维&测试
    • Kubernetes
      • Kubernetes 在有赞的实践
  • 运维&测试
    • Kubernetes
      • Kubernetes 学习路径
  • 运维&测试
    • Kubernetes
      • Kubernetes如何改变美团的云基础设施?
  • 运维&测试
    • Kubernetes
      • Kubernetes的三种外部访问方式:NodePort、LoadBalancer 和 Ingress
  • 运维&测试
    • Kubernetes
      • 谈 Kubernetes 的架构设计与实现原理
  • 运维&测试
    • 压测
      • 全链路压测平台(Quake)在美团中的实践
  • 运维&测试
    • 测试
      • Cpress - JavaScript End to End Testing Framework
  • 运维&测试
    • 测试
      • 代码覆盖率-JaCoCo
  • 运维&测试
    • 测试
      • 浅谈代码覆盖率
  • 运维&测试
    • 测试
      • 测试中 Fakes、Mocks 以及 Stubs 概念明晰
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP中的Bean是如何被AOP代理的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP原生动态代理和Cglib动态代理
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP实现方式(xml&注解)
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP是如何收集切面类并封装的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP概述
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的底层核心后置处理器
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的延伸知识
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(一)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(三)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(二)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(五)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(四) - 循环依赖与解决方案
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - 启动引导
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot JarLauncher
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot Web Mvc 自动装配
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 使用ApplicationListener监听器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 声明式事务
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 嵌入式容器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot引起的“堆外内存泄漏”排查及经验总结
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot的启动流程
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot自动化配置源码分析
  • Java FrameWorks
    • Spring
      • Spring Boot
        • 如何自定义Spring Boot Starter?
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 模块装配和条件装配
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 配置源(xml,注解)
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Environment
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ApplicationContext
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactory
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactoryPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(一) - 概述
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(三) - 实例化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(二) - BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(五) - 销毁阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(四) - 初始化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ComponentScan
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 基础篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 总结
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 进阶篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC容器的生命周期
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Resource
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的初始化原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的核心工作原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • WebMvc的架构设计与组件功能解析
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Boot 2 + Spring Security 5 + JWT 的单页应用 Restful 解决方案
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security Oauth
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(传统方式)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(函数式端点)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • WebFlux的自动装配
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速了解响应式编程与Reactive
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速使用WebFlux
  • 分布式
    • 协调服务
      • Zookeeper
        • Zookeeper - 客户端之 Curator
  • 分布式
    • 协调服务
      • Zookeeper
        • 详解分布式协调服务 ZooKeeper
  • 分布式
    • 协调服务
      • etcd
        • 高可用分布式存储 etcd 的实现原理
  • 数据库
    • Database Version Control
      • Flyway
        • Database Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • How Flyway works
  • 数据库
    • Database Version Control
      • Flyway
        • Rolling Back Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • The meaning of the concept of checksums
  • 数据库
    • Database Version Control
      • Liquibase
        • Introduction to Liquibase Rollback
  • 数据库
    • Database Version Control
      • Liquibase
        • LiquiBase中文学习指南
  • 数据库
    • Database Version Control
      • Liquibase
        • Use Liquibase to Safely Evolve Your Database Schema
  • 系统设计
    • 流量控制
      • RateLimiter
        • Guava Rate Limiter实现分析
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel 与 Hystrix 的对比
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel工作主流程
  • 系统设计
    • 流量控制
      • 算法
        • 分布式服务限流实战
  • 系统设计
    • 解决方案
      • 秒杀系统
        • 如何设计一个秒杀系统
  • 系统设计
    • 解决方案
      • 红包系统
        • 微信高并发资金交易系统设计方案--百亿红包背后的技术支撑
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 什么是预排序遍历树算法(MPTT,Modified Preorder Tree Traversal)
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 加密算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 推荐系统算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • linkerd
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 查找算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 缓存淘汰算法中的LRU和LFU
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 负载均衡算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Paxos算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Raft算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Snowflake算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - ZAB算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - 一致性Hash算法
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Bitmap & Bloom Filter
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Map & Reduce
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Trie树/数据库/倒排索引
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 分治/hash/排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 双层桶划分
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 外(磁盘文件)排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 布隆过滤器
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理算法
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 文本预处理:后缀树(Suffix Tree)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:BM 算法 (Boyer-Moore)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:KMP 算法(Knuth-Morris-Pratt)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分支限界算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分治算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 动态规划算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 回溯算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 贪心算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 十大排序算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(一)之3种简单排序(选择,冒泡,直接插入)
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(三)之堆排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(二)之希尔排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(四)之归并排序
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 树的高度和深度
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 红黑树深入剖析及Java实现
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - Hash
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - 数组、链表、栈、队列
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 逻辑结构 - 树
  • 运维&测试
    • 测试
      • Spock
        • Groovy 简明教程
  • 运维&测试
    • 测试
      • Spock
        • Spock 官方文档
  • 运维&测试
    • 测试
      • Spock
        • Spock单元测试框架介绍以及在美团优选的实践
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(一)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(三)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(二)
  • 运维&测试
    • 测试
      • TDD
        • 测试驱动开发(TDD)- 原理篇
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 服务注册的原理
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 配置中心原理分析
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • 服务调用过程
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Bus
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Consul
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Stream
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel 与 Hystrix 的对比
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • How Hystrix Works
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix原理与实战
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Spring Cloud Hystrix基本原理
由 GitBook 提供支持
在本页
  • 1. 二叉树
  • 2. 二叉查找树
  • 3. 平衡二叉树
  • 4. B树
  • 5. B+树
  • 6. B*树

这有帮助吗?

  1. 计算机基础
  2. 数据结构与算法
  3. 数据结构

逻辑结构 - 树

上一页数据结构下一页运维&测试

最后更新于2年前

这有帮助吗?

数据结构中有很多树的结构,其中包括二叉树、二叉搜索树、2-3树、红黑树等等。本文中对数据结构中常见的几种树的概念和用途进行了汇总,不求严格精准,但求简单易懂。

参考链接:

1. 二叉树

二叉树是数据结构中一种重要的数据结构,也是树表家族最为基础的结构。

二叉树的定义:二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2i-1个结点;深度为k的二叉树至多有2k-1个结点;对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。

深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0; 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;

二叉树的示例:

满二叉树和完全二叉树

满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值,所有叶子结点必须在同一层上。

满二叉树除了满足普通二叉树的性质,还具有以下性质:

  1. 满二叉树中第 i 层的节点数为 2n-1 个。

  2. 深度为 k 的满二叉树必有 2k-1 个节点 ,叶子数为 2k-1。

  3. 满二叉树中不存在度为 1 的节点,每一个分支点中都两棵深度相同的子树,且叶子节点都在最底层。

  4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~(h-1)层) 的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。

完全二叉树是效率很高的数据结构,堆是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。

2. 二叉查找树

二叉查找树定义:又称为是二叉排序树(Binary Sort Tree)或二叉搜索树。二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  1. 树中每个节点最多有两个子树,通常称为左子树和右子树。

  2. 若左子树不空,则左子树上所有结点的值均小于它的根结点的值。

  3. 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值。

  4. 左、右子树也分别为二叉排序树。

  5. 没有键值相等的节点。

二叉查找树的时间复杂度:它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度,这就是平衡查找树设计的初衷。

2.1 树的遍历

假设我们需要遍历树中所有节点,这里有许多递归方法可以实现:

  1. 中序遍历:当到达某个节点时,先访问左子节点,再输出该节点,最后访问右子节点。

    A, B, C, D, E, F, G, H, I.

  2. 前序遍历:当到达某个节点时,先输出该节点,再访问左子节点,最后访问右子节点。

    F, B, A, D, C, E, G, I, H.

  3. 后序遍历:当到达某个节点时,先访问左子节点,再访问右子节点,最后输出该节点。

    A, C, E, D, B, H, I, G, F.

  4. 层次遍历

    F, B, G, A, D, I, C, E, H.

2.2 树的搜索

树的搜索和树的遍历差不多,就是在遍历的时候只搜索不输出就可以了。

2.3 节点插入

  1. 递归地去查找该二叉树,找到应该插入的节点。

  2. 若当前的二叉查找树为空,则插入的元素为根节点。

  3. 若插入的元素值小于根节点值,则将元素插入到左子树中。

  4. 若插入的元素值不小于根节点值,则将元素插入到右子树中。

2.4 节点删除

首先需要搜索该节点,然后可以分为以下四种情况进行讨论:

  1. 如果找不到该节点,那么什么都不用做。

  2. 如果被移除的元素在叶节点(no children):那么直接移除该节点,并且将父节点原本指向该位置改为 null (如果是根节点,那就不用修改父节点指向位置)。

  3. 如果删除的元素只有一个儿子(one child):那么也很简单,直接删除该节点,并且将父节点原本指向的位置改为该儿子 (如果是根节点,那么该儿子成为新的根节点)。

  4. 如果删除的元素有两个儿子,那么可以取左子树中最大元素或者右子树中最小元素进行替换,然后将最大元素或最小元素原位置置空。

3. 平衡二叉树

我们知道,对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度O(log2n)同时也由此而决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性受到破坏,提高它的操作的时间复杂度。于是就有了我们下边介绍的平衡二叉树。

平衡二叉树定义:平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。

最小二叉平衡树的节点的公式如下:

F(n)=F(n-1)+F(n-2)+1

这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

3.1 平衡查找树之AVL树

AVL树定义:AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis,他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

AVL树的自平衡操作——旋转

AVL树最关键的也是最难的一步操作就是旋转。旋转主要是为了实现AVL树在实施了插入和删除操作以后,树重新回到平衡的方法。下面我们重点研究一下AVL树的旋转。

对于一个平衡的节点,由于任意节点最多有两个儿子,因此高度不平衡时,此节点的两颗子树的高度差2.容易看出,这种不平衡出现在下面四种情况:

  1. 6节点的左子树3节点高度比右子树7节点大2,左子树3节点的左子树1节点高度大于右子树4节点,这种情况成为左左。

  2. 6节点的左子树2节点高度比右子树7节点大2,左子树2节点的左子树1节点高度小于右子树4节点,这种情况成为左右。

  3. 2节点的左子树1节点高度比右子树5节点小2,右子树5节点的左子树3节点高度大于右子树6节点,这种情况成为右左。

  4. 2节点的左子树1节点高度比右子树4节点小2,右子树4节点的左子树3节点高度小于右子树6节点,这种情况成为右右。

从图2中可以可以看出,1和4两种情况是对称的,这两种情况的旋转算法是一致的,只需要经过一次旋转就可以达到目标,我们称之为单旋转。2和3两种情况也是对称的,这两种情况的旋转算法也是一致的,需要进行两次旋转,我们称之为双旋转。

单旋转

单旋转是针对于左左和右右这两种情况的解决方案,这两种情况是对称的,只要解决了左左这种情况,右右就很好办了。图3是左左情况的解决方案,节点k2不满足平衡特性,因为它的左子树k1比右子树Z深2层,而且k1子树中,更深的一层的是k1的左子树X子树,所以属于左左情况。

为使树恢复平衡,我们把k2变成这棵树的根节点,因为k2大于k1,把k2置于k1的右子树上,而原本在k1右子树的Y大于k1,小于k2,就把Y置于k2的左子树上,这样既满足了二叉查找树的性质,又满足了平衡二叉树的性质。

这样的操作只需要一部分指针改变,结果我们得到另外一颗二叉查找树,它是一棵AVL树,因为X向上一移动了一层,Y还停留在原来的层面上,Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同,插入操作使得X高度长高了。因此,由于这颗子树高度没有变化,所以通往根节点的路径就不需要继续旋转了。

双旋转

对于左右和右左这两种情况,单旋转不能使它达到一个平衡状态,要经过两次旋转。双旋转是针对于这两种情况的解决方案,同样的,这样两种情况也是对称的,只要解决了左右这种情况,右左就很好办了。图4是左右情况的解决方案,节点k3不满足平衡特性,因为它的左子树k1比右子树Z深2层,而且k1子树中,更深的一层的是k1的右子树k2子树,所以属于左右情况。

为使树恢复平衡,我们需要进行两步,第一步,把k1作为根,进行一次右右旋转,旋转之后就变成了左左情况,所以第二步再进行一次左左旋转,最后得到了一棵以k2为根的平衡二叉树。

3.2 平衡二叉树之红黑树

红黑树的定义:红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的,称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可在O(logn)时间内做查找,插入和删除,这里的n是树中元素的数目。

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用(real time application)中有价值,而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值;例如,在计算几何中使用的很多数据结构都可以基于红黑树。此外,红黑树还是2-3-4树的一种等同,它们的思想是一样的,只不过红黑树是2-3-4树用二叉树的形式表示的。

红黑树的性质:

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制的一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

  1. 节点是红色或黑色。

  2. 根节点是黑色。

  3. 每个叶子节点都是黑色的空节点(NIL节点)。

  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

正因为这些规则限制,才保证了红黑树的平衡,红黑树从根到叶子的最长路径不会超过最短路径的2倍。

下面是一个具体的红黑树的图例:

这些约束确保了红黑树的关键特性: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

要知道为什么这些性质确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

红黑树的应用:

红黑树的应用很多,其中JDK的集合类TreeMap和TreeSet底层就是红黑树实现的,在Java8中,连HashMap也用到了红黑树。

红黑树的自平衡操作:

因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为O(logn) 次。

我们首先以二叉查找树的方法增加节点并标记它为红色。如果设为黑色,就会导致根到叶子的路径上有一条路上,多一个额外的黑节点,这个是很难调整的(违背性质5)。但是设为红色节点后,可能会导致出现两个连续红色节点的冲突,那么可以通过颜色调换(color flips)和树旋转来调整。下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样,我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意:

  1. 性质1和性质3总是保持着。

  2. 性质4只在增加红色节点、重绘黑色节点为红色,或做旋转时受到威胁。

  3. 性质5只在增加黑色节点、重绘红色节点为黑色,或做旋转时受到威胁。

插入操作:

假设,将要插入的节点标为N,N的父节点标为P,N的祖父节点标为G,N的叔父节点标为U。在图中展示的任何颜色要么是由它所处情形这些所作的假定,要么是假定所暗含的。

情形1: 该树为空树,直接插入根结点的位置,违反性质1,把节点颜色有红改为黑即可。

情形2: 插入节点N的父节点P为黑色,不违反任何性质,无需做任何修改。在这种情形下,树仍是有效的。性质5也未受到威胁,尽管新节点N有两个黑色叶子子节点;但由于新节点N是红色,通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点,所以依然满足这个性质。

注: 情形1很简单,情形2中P为黑色,一切安然无事,但P为红就不一样了,下边是P为红的各种情况,也是真正难懂的地方。

情形3: 如果父节点P和叔父节点U二者都是红色,(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质4)。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G,在这些路径上的黑节点数目没有改变。但是,红色的祖父节点G的父节点也有可能是红色的,这就违反了性质4。为了解决这个问题,我们在祖父节点G上递归地进行上述情形的整个过程(把G当成是新加入的节点进行各种情形的检查)。比如,G为根节点,那我们就直接将G变为黑色(情形1);如果G不是根节点,而它的父节点为黑色,那符合所有的性质,直接插入即可(情形2);如果G不是根节点,而它的父节点为红色,则递归上述过程(情形3)。

情形4: 父节点P是红色而叔父节点U是黑色或缺少,新节点N是其父节点的左子节点,而父节点P又是其父节点G的左子节点。在这种情形下,我们进行针对祖父节点G的一次右旋转; 在旋转产生的树中,以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们知道以前的祖父节点G是黑色,否则父节点P就不可能是红色(如果P和G都是红色就违反了性质4,所以G必须是黑色)。我们切换以前的父节点P和祖父节点G的颜色,结果的树满足性质4。性质5也仍然保持满足,因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G,现在它们都通过以前的父节点P。在各自的情形下,这都是三个节点中唯一的黑色节点。

情形5: 父节点P是红色而叔父节点U是黑色或缺少,并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下,我们进行一次左旋转调换新节点和其父节点的角色; 接着,我们按情形4处理以前的父节点P以解决仍然失效的性质4。注意这个改变会导致某些路径通过它们以前不通过的新节点N(比如图中1号叶子节点)或不通过节点P(比如图中3号叶子节点),但由于这两个节点都是红色的,所以性质5仍有效。

注: 插入实际上是原地算法,因为上述所有调用都使用了尾部递归。

删除操作:

如果需要删除的节点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的节点的问题。对于二叉查找树,在删除带有两个非叶子儿子的节点的时候,我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素,并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点,它必定有少于两个非叶子的儿子。因为只是复制了一个值,不违反任何性质,这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空,即均为叶子,我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点(此时该节点的儿子将都为叶子节点),它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它,并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点,这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点,用它的红色儿子顶替上来的话,会破坏性质5,但是如果我们重绘它的儿子为黑色,则曾经通过它的所有路径将通过它的黑色儿子,这样可以继续保持性质5。

需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候,这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便,称呼这个儿子为N(在新的位置上),称呼它的兄弟(它父亲的另一个儿子)为S。在下面的示意图中,我们还是使用P称呼N的父亲,SL称呼S的左儿子,SR称呼S的右儿子。

如果N和它初始的父亲是黑色,则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这违反了性质5,树需要被重新平衡。有几种情形需要考虑:

情形1: N是新的根。在这种情形下,我们就做完了。我们从所有路径去除了一个黑色节点,而新根是黑色的,所以性质都保持着。

注意: 在情形2、5和6下,我们假定N是它父亲的左儿子。如果它是右儿子,则在这些情形下的左和右应当对调。

情形2: S是红色。在这种情形下我们在N的父亲上做左旋转,把红色兄弟转换成N的祖父,我们接着对调N的父亲和祖父的颜色。完成这两个操作后,尽管所有路径上黑色节点的数目没有改变,但现在N有了一个黑色的兄弟和一个红色的父亲(它的新兄弟是黑色因为它是红色S的一个儿子),所以我们可以接下去按情形4、情形5或情形6来处理。

情形3: N的父亲、S和S的儿子都是黑色的。在这种情形下,我们简单的重绘S为红色。结果是通过S的所有路径,它们就是以前不通过N的那些路径,都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点,这使事情都平衡了起来。但是,通过P的所有路径现在比不通过P的路径少了一个黑色节点,所以仍然违反性质5。要修正这个问题,我们要从情形1开始,在P上做重新平衡处理。

情形4: S和S的儿子都是黑色,但是N的父亲是红色。在这种情形下,我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目,但是它在通过N的路径上对黑色节点数目增加了一,添补了在这些路径上删除的黑色节点。

情形5: S是黑色,S的左儿子是红色,S的右儿子是黑色,而N是它父亲的左儿子。在这种情形下我们在S上做右旋转,这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点,但是现在N有了一个黑色兄弟,他的右儿子是红色的,所以我们进入了情形6。N和它的父亲都不受这个变换的影响。

情形6: S是黑色,S的右儿子是红色,而N是它父亲的左儿子。在这种情形下我们在N的父亲上做左旋转,这样S成为N的父亲(P)和S的右儿子的父亲。我们接着交换N的父亲和S的颜色,并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色,所以性质3没有被违反。但是,N现在增加了一个黑色祖先: 要么N的父亲变成黑色,要么它是黑色而S被增加为一个黑色祖父。所以,通过N的路径都增加了一个黑色节点。

此时,如果一个路径不通过N,则有两种可能性:

  • 它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲,而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。

  • 它通过N的新叔父,S的右儿子。那么它以前通过S、S的父亲和S的右儿子,但是现在只通过S,它被假定为它以前的父亲的颜色,和S的右儿子,它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。

在任何情况下,在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色,但是在变换前后都必须指定相同的颜色。

4. B树

B树也是一种用于查找的平衡树,但是它不是二叉树。

B树的定义:B树(B-tree)是一种树状数据结构,能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作,都在对数时间内完成。B树,概括来说是一个一般化的二叉查找树,可以拥有多于2个子节点。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

在B树中查找给定关键字的方法是,首先把根结点取来,在根结点所包含的关键字K1,…,Kn查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查找的关键字在Ki与Ki+1之间,Pi为指向子树根节点的指针,此时取指针Pi所指的结点继续查找,直至找到,或指针Pi为空时查找失败。

B 树是一种多路平衡查找树,它的每一个节点最多包含 k 个孩子,k 被称为 B 树的阶。k 的大小取决于磁盘页的大小。

一个m阶的B树具有如下几个特征:

  1. 根结点至少有两个子女。

  2. 每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m

  3. 每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m

  4. 所有的叶子结点都位于同一层。

  5. 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

下面就是3阶的B-树:

这棵树中,咱们重点来看(2,6) 节点。该节点有两个元素 2 和 6, 又有三个孩子 1 (3,5),8。其中 1 小于元素 2, (3,5) 在元素 2,6 之间,8 大于(3,5),正好符合刚刚所列的几条特征。

B-树的应用:

B-树主要用于文件系统以及部分数据库索引,比如著名的非关系型数据库MongoDB。而大部分关系型数据库则使用B+树作为索引。

5. B+树

B+树是B树的变体,也是一种多路搜索树,有着比B-树更高的查询性能:

一个m阶的B+树具有如下几个特征:

  1. 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。

  2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

  3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

B+树还具有一个特点,这个特点是在索引之外,确是至关重要的特点。那就是卫星数据的位置。

所谓卫星数据,指的是索引元素所指向的数据记录,比如数据库中的某一行。在 B-树中,无论中间节点还是叶子节点都带有卫星数据。

B-树中的卫星数据(Satellite Information):

而在 B+树当中,只有叶子节点带有卫星数据,其余中间节点仅仅是索引,没有任何数据关联。

B+树中的卫星数据(Satellite Information):

需要补充的是,在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。

B+树的好处主要体现在查询性能上。

下面我们分别通过单行查询和范围查询来做分析。

在单元素查询的时候,B 树会自顶向下逐层查找节点,最终找到匹配的叶子节点。与B-树的区别是,首先,B+树的中间节点没有卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素。这就意味着,数据量相同的情况下,B+树的结构比 B 树更加“矮胖”因此查询时 I0 次数也更少。

其次,B+树的查询必须最终查找到叶子节点,而 B-树只要找到匹配元素即可,无论匹配元素处于中间节点还是叶子节点。

因此,B-树的查找性能并不稳定(最好情况是只查根节点,最坏情况是查到叶子节点)。而 B+树的每一次查找都是稳定的。

下面我们再来看看范围查询。B-树如何倣范围查询呢?只能依靠繁琐的中序遍历。反观 B 树的范围查询,则要简单得多,只需要在链表上做遍历即可。

综合起来,B+树相比 B-树的优势有三个:

  1. I0 次数更少;

  2. 查询性能稳定;

  3. 范围查询简便。

6. B*树

B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针,将结点的最低利用率从1/2提高到2/3。

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

所以,B*树分配新结点的概率比B+树要低,空间使用率更高。

2021-03-05-k80G5l
2021-03-05-SBeDlK
2021-03-05-7AmeiD
2021-03-05-MMYqmR

有关AVL树的具体实现,可以参考。

参考链接:

以下内容整理自。

参考链接:

参考链接:

C小加的博客《一步一步写平衡二叉树(AVL)》
漫画:什么是红黑树?
wiki百科之红黑树
漫画:什么是B-树?
漫画:什么是B+树?
平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了
[Data Structure] 数据结构中各种树