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. BST
  • 1.1 BST的查找操作
  • 1.2 BST的插入操作
  • 1.3 BST的删除操作
  • 1.4 BST存在的问题
  • 2. RBTree
  • 2.1 RBTree的定义
  • 2.2 RBTree的旋转操作
  • 2.3 RBTree的查找操作
  • 2.4 RBTree的插入操作
  • 2.5 RBTree的删除操作
  • 2.6 RBTree的Java实现
  • 3. 总结
  • 4. 参考文献

这有帮助吗?

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

红黑树深入剖析及Java实现

上一页数据结构下一页计算机基础

最后更新于2年前

这有帮助吗?

转载:

红黑树是平衡二叉查找树的一种。为了深入理解红黑树,我们需要从二叉查找树开始讲起。

1. BST

二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找效率。

在理想的情况下,二叉查找树增删查改的时间复杂度为O(logN)(其中N为节点数),最坏的情况下为O(N)。当它的高度为logN+1时,我们就说二叉查找树是平衡的。

2021-03-19-4VBCSN

1.1 BST的查找操作

T  key = a search key
Node root = point to the root of a BST

while(true){
    if(root==null){
    	break;
    }
    if(root.value.equals(key)){
    	return root;
    }
    else if(key.compareTo(root.value)<0){
    	root = root.left;
    }
    else{
    	root = root.right;
    }
}
return null;

从程序中可以看出,当BST查找的时候,先与当前节点进行比较:

  • 如果相等的话就返回当前节点。

  • 如果少于当前节点则继续查找当前节点的左节点。

  • 如果大于当前节点则继续查找当前节点的右节点。

直到当前节点指针为空或者查找到对应的节点,程序查找结束。

1.2 BST的插入操作

Node node = create a new node with specify value
Node root = point the root node of a BST
Node parent = null;

//find the parent node to append the new node
while(true){
   if(root==null)break;
   parent = root;
   if(node.value.compareTo(root.value)<=0){
      root = root.left;  
   }else{
      root = root.right;
   } 
}
if(parent!=null){
   if(node.value.compareTo(parent.value)<=0){//append to left
      parent.left = node;
   }else{//append to right
	  parent.right = node;
   }
}

插入操作先通过循环查找到待插入的节点的父节点,和查找父节点的逻辑一样,都是比大小,小的往左,大的往右。找到父节点后,对比父节点,小的就插入到父节点的左节点,大就插入到父节点的右节点上。

1.3 BST的删除操作

删除操作的步骤如下:

  1. 查找到要删除的节点。

  2. 如果待删除的节点是叶子节点,则直接删除。

  3. 如果待删除的节点不是叶子节点,则先找到待删除节点的中序遍历的后继节点,用该后继节点的值替换待删除的节点的值,然后删除后继节点。

1.4 BST存在的问题

BST存在的主要问题是,数在插入的时候会导致树倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接的影响了树的查找效率。理想的高度是logN,最坏的情况是所有的节点都在一条斜线上,这样的树的高度为N。

2. RBTree

基于BST存在的问题,一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候,会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树。

红黑树(Red-Black Tree,以下简称RBTree)的实际应用非常广泛,比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等,各种语言的函数库如Java的TreeMap和TreeSet,C++ STL的map、multimap、multiset等。

RBTree也是函数式语言中最常用的持久数据结构之一,在计算几何中也有重要作用。值得一提的是,Java 8中HashMap的实现也因为用RBTree取代链表,性能有所提升。

2.1 RBTree的定义

RBTree的定义如下:

  1. 任何一个节点都有颜色,黑色或者红色。

  2. 根节点是黑色的。

  3. 父子节点之间不能出现两个连续的红节点。

  4. 任何一个节点向下遍历到其子孙的叶子节点,所经过的黑节点个数必须相等。

  5. 空节点被认为是黑色的。

数据结构表示如下:

class  Node<T>{
   public  T value;
   public   Node<T> parent;
   public   boolean isRed;
   public   Node<T> left;
   public   Node<T> right;
}

RBTree在理论上还是一棵BST树,但是它在对BST的插入和删除操作时会维持树的平衡,即保证树的高度在[logN,logN+1](理论上,极端的情况下可以出现RBTree的高度达到2*logN,但实际上很难遇到)。这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)。RBTree的查找操作就是BST的查找操作。

2.2 RBTree的旋转操作

旋转操作(Rotate)的目的是使节点颜色符合定义,让RBTree的高度达到平衡。 Rotate分为left-rotate(左旋)和right-rotate(右旋),区分左旋和右旋的方法是:待旋转的节点从左边上升到父节点就是右旋,待旋转的节点从右边上升到父节点就是左旋。

2.3 RBTree的查找操作

RBTree的查找操作和BST的查找操作是一样的。请参考BST的查找操作代码。

2.4 RBTree的插入操作

RBTree的插入与BST的插入方式是一致的,只不过是在插入过后,可能会导致树的不平衡,这时就需要对树进行旋转操作和颜色修复(在这里简称插入修复),使得它符合RBTree的定义。

新插入的节点是红色的,插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说,只有在父节点为红色节点的时候是需要插入修复操作的。

插入修复操作分为以下的三种情况,而且新插入的节点的父节点都是红色的:

  1. 叔叔节点也为红色。

  2. 叔叔节点为空,且祖父节点、父节点和新节点处于一条斜线上。

  3. 叔叔节点为空,且祖父节点、父节点和新节点不处于一条斜线上。

2.4.1 插入操作-Case 1

case 1的操作是将父节点和叔叔节点与祖父节点的颜色互换,这样就符合了RBTRee的定义。即维持了高度的平衡,修复后颜色也符合RBTree定义的第三条和第四条。下图中,操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话,则继续做修复操作。

2.4.2 插入操作-Case 2

case 2的操作是将B节点进行右旋操作,并且和父节点A互换颜色。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。如果B和C节点都是右节点的话,只要将操作变成左旋就可以了。

2.4.3 插入操作-Case 3

case 3的操作是将C节点进行左旋,这样就从case 3转换成case 2了,然后针对case 2进行操作处理就行了。case 2操作做了一个右旋操作和颜色互换来达到目的。如果树的结构是下图的镜像结构,则只需要将对应的左旋变成右旋,右旋变成左旋即可。

2.4.4 插入操作的总结

插入后的修复操作是一个向root节点回溯的操作,一旦牵涉的节点都符合了红黑树的定义,修复操作结束。之所以会向上回溯是由于case 1操作会将父节点,叔叔节点和祖父节点进行换颜色,有可能会导致祖父节点不平衡(红黑树定义3)。这个时候需要对祖父节点为起点进行调节(向上回溯)。

祖父节点调节后如果还是遇到它的祖父颜色问题,操作就会继续向上回溯,直到root节点为止,根据定义root节点永远是黑色的。在向上的追溯的过程中,针对插入的3中情况进行调节。直到符合红黑树的定义为止。直到牵涉的节点都符合了红黑树的定义,修复操作结束。

如果上面的3中情况如果对应的操作是在右子树上,做对应的镜像操作就是了。

2.5 RBTree的删除操作

删除操作首先需要做的也是BST的删除操作,删除操作会删除对应的节点,如果是叶子节点就直接删除,如果是非叶子节点,会用对应的中序遍历的后继节点来顶替要删除节点的位置。删除后就需要做删除修复操作,使的树符合红黑树的定义,符合定义的红黑树高度是平衡的。

删除修复操作在遇到被删除的节点是红色节点或者到达root节点时,修复操作完毕。

删除修复操作是针对删除黑色节点才有的,当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来,如果兄弟节点没有黑节点可以借调的话,就只能往上追溯,将每一级的黑节点数减去一个,使得整棵树符合红黑树的定义。

删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡,如果局部的平衡达到了,就看整体的树是否是平衡的,如果不平衡就接着向上追溯调整。

删除修复操作分为四种情况(删除黑节点后):

  1. 待删除的节点的兄弟节点是红色的节点。

  2. 待删除的节点的兄弟节点是黑色的节点,且兄弟节点的子节点都是黑色的。

  3. 待调整的节点的兄弟节点是黑色的节点,且兄弟节点的左子节点是红色的,右节点是黑色的(兄弟节点在右边),如果兄弟节点在左边的话,就是兄弟节点的右子节点是红色的,左节点是黑色的。

  4. 待调整的节点的兄弟节点是黑色的节点,且右子节点是是红色的(兄弟节点在右边),如果兄弟节点在左边,则就是对应的就是左节点是红色的。

2.5.1 删除操作-Case 1

由于兄弟节点是红色节点的时候,无法借调黑节点,所以需要将兄弟节点提升到父节点,由于兄弟节点是红色的,根据RBTree的定义,兄弟节点的子节点是黑色的,就可以从它的子节点借调了。

case 1这样转换之后就会变成后面的case 2,case 3,或者case 4进行处理了。上升操作需要对C做一个左旋操作,如果是镜像结构的树只需要做对应的右旋操作即可。

之所以要做case 1操作是因为兄弟节点是红色的,无法借到一个黑节点来填补删除的黑节点。

2.5.2 删除操作-Case 2

case 2的删除操作是由于兄弟节点可以消除一个黑色节点,因为兄弟节点和兄弟节点的子节点都是黑色的,所以可以将兄弟节点变红,这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点,继续向上调整,直到整颗树的颜色符合RBTree的定义为止。

case 2这种情况下之所以要将兄弟节点变红,是因为如果把兄弟节点借调过来,会导致兄弟的结构不符合RBTree的定义,这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后,达到了局部的平衡了,但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点,接着进行修复操作。

2.5.3 删除操作-Case 3

case 3的删除操作是一个中间步骤,它的目的是将左边的红色节点借调过来,这样就可以转换成case 4状态了,在case 4状态下可以将D,E节点都阶段过来,通过将两个节点变成黑色来保证红黑树的整体平衡。

之所以说case-3是一个中间状态,是因为根据红黑树的定义来说,下图并不是平衡的,他是通过case 2操作完后向上回溯出现的状态。之所以会出现case 3和后面的case 4的情况,是因为可以通过借用侄子节点的红色,变成黑色来符合红黑树定义4。

2.5.4 删除操作-Case 4

Case 4的操作是真正的节点借调操作,通过将兄弟节点以及兄弟节点的右节点借调过来,并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的,这样的话,整棵树还是符合RBTree的定义的。

Case 4这种情况的发生只有在待删除的节点的兄弟节点为黑,且子节点不全部为黑,才有可能借调到两个节点来做黑节点使用,从而保持整棵树都符合红黑树的定义。

2.5.5 删除操作的总结

红黑树的删除操作是最复杂的操作,复杂的地方就在于当删除了黑色节点的时候,如何从兄弟节点去借调节点,以保证树的颜色符合定义。由于红色的兄弟节点是没法借调出黑节点的,这样只能通过选择操作让他上升到父节点,而由于它是红节点,所以它的子节点就是黑的,可以借调。

对于兄弟节点是黑色节点的可以分成3种情况来处理,当所以的兄弟节点的子节点都是黑色节点时,可以直接将兄弟节点变红,这样局部的红黑树颜色是符合定义的。但是整颗树不一定是符合红黑树定义的,需要往上追溯继续调整。

对于兄弟节点的子节点为左红右黑或者 (全部为红,右红左黑)这两种情况,可以先将前面的情况通过选择转换为后一种情况,在后一种情况下,因为兄弟节点为黑,兄弟节点的右节点为红,可以借调出两个节点出来做黑节点,这样就可以保证删除了黑节点,整棵树还是符合红黑树的定义的,因为黑色节点的个数没有改变。

红黑树的删除操作是遇到删除的节点为红色,或者追溯调整到了root节点,这时删除的修复操作完毕。

2.6 RBTree的Java实现

public class RBTreeNode<T extends Comparable<T>> {
	private T value;//node value
	private RBTreeNode<T> left;//left child pointer
	private RBTreeNode<T> right;//right child pointer
	private RBTreeNode<T> parent;//parent pointer
	private boolean red;//color is red or not red
	
	public RBTreeNode(){}
	public RBTreeNode(T value){this.value=value;}
	public RBTreeNode(T value,boolean isRed){this.value=value;this.red = isRed;}
	
	public T getValue() {
		return value;
	}
	void setValue(T value) {
		this.value = value;
	}
	RBTreeNode<T> getLeft() {
		return left;
	}
	void setLeft(RBTreeNode<T> left) {
		this.left = left;
	}
	RBTreeNode<T> getRight() {
		return right;
	}
	void setRight(RBTreeNode<T> right) {
		this.right = right;
	}
	RBTreeNode<T> getParent() {
		return parent;
	}
	void setParent(RBTreeNode<T> parent) {
		this.parent = parent;
	}
	boolean isRed() {
		return red;
	}
	boolean isBlack(){
		return !red;
	}
	/**
	* is leaf node
	**/
	boolean isLeaf(){
		return left==null && right==null;
	}
	
	void setRed(boolean red) {
		this.red = red;
	}
	
	void makeRed(){
		red=true;
	}
	void makeBlack(){
		red=false;
	}
	@Override
	public String toString(){
		return value.toString();
	}
}




public class RBTree<T extends Comparable<T>> {
	private final RBTreeNode<T> root;
	//node number
	private java.util.concurrent.atomic.AtomicLong size = 
					new java.util.concurrent.atomic.AtomicLong(0);
	
	//in overwrite mode,all node's value can not  has same	value
	//in non-overwrite mode,node can have same value, suggest don't use non-overwrite mode.
	private volatile boolean overrideMode=true;
	
	public RBTree(){
		this.root = new RBTreeNode<T>();
	}
	
	public RBTree(boolean overrideMode){
		this();
		this.overrideMode=overrideMode;
	}
	
	
	public boolean isOverrideMode() {
		return overrideMode;
	}

	public void setOverrideMode(boolean overrideMode) {
		this.overrideMode = overrideMode;
	}

	/**
	 * number of tree number
	 * @return
	 */
	public long getSize() {
		return size.get();
	}
	/**
	 * get the root node
	 * @return
	 */
	private RBTreeNode<T> getRoot(){
		return root.getLeft();
	}
	
	/**
	 * add value to a new node,if this value exist in this tree,
	 * if value exist,it will return the exist value.otherwise return null
	 * if override mode is true,if value exist in the tree,
	 * it will override the old value in the tree
	 * 
	 * @param value
	 * @return
	 */
	public T addNode(T value){
		RBTreeNode<T> t = new RBTreeNode<T>(value);
		return addNode(t);
	}
	/**
	 * find the value by give value(include key,key used for search,
	 * other field is not used,@see compare method).if this value not exist return null
	 * @param value
	 * @return
	 */
	public T find(T value){
		RBTreeNode<T> dataRoot = getRoot();
		while(dataRoot!=null){
			int cmp = dataRoot.getValue().compareTo(value);
			if(cmp<0){
				dataRoot = dataRoot.getRight();
			}else if(cmp>0){
				dataRoot = dataRoot.getLeft();
			}else{
				return dataRoot.getValue();
			}
		}
		return null;
	}
	/**
	 * remove the node by give value,if this value not exists in tree return null
	 * @param value include search key
	 * @return the value contain in the removed node
	 */
	public T remove(T value){
		RBTreeNode<T> dataRoot = getRoot();
		RBTreeNode<T> parent = root;
		
		while(dataRoot!=null){
			int cmp = dataRoot.getValue().compareTo(value);
			if(cmp<0){
				parent = dataRoot;
				dataRoot = dataRoot.getRight();
			}else if(cmp>0){
				parent = dataRoot;
				dataRoot = dataRoot.getLeft();
			}else{
				if(dataRoot.getRight()!=null){
					RBTreeNode<T> min = removeMin(dataRoot.getRight());
					//x used for fix color balance
					RBTreeNode<T> x = min.getRight()==null ? min.getParent() : min.getRight();
					boolean isParent = min.getRight()==null;
							
					min.setLeft(dataRoot.getLeft());
					setParent(dataRoot.getLeft(),min);
					if(parent.getLeft()==dataRoot){
						parent.setLeft(min);
					}else{
						parent.setRight(min);
					}
					setParent(min,parent);
					
					boolean curMinIsBlack = min.isBlack();
					//inherit dataRoot's color
					min.setRed(dataRoot.isRed());
					
					if(min!=dataRoot.getRight()){
						min.setRight(dataRoot.getRight());
						setParent(dataRoot.getRight(),min);
					}
					//remove a black node,need fix color
					if(curMinIsBlack){
						if(min!=dataRoot.getRight()){
							fixRemove(x,isParent);
						}else if(min.getRight()!=null){
							fixRemove(min.getRight(),false);
						}else{
							fixRemove(min,true);
						}
					}
				}else{
					setParent(dataRoot.getLeft(),parent);
					if(parent.getLeft()==dataRoot){
						parent.setLeft(dataRoot.getLeft());
					}else{
						parent.setRight(dataRoot.getLeft());
					}
					//current node is black and tree is not empty
					if(dataRoot.isBlack() && !(root.getLeft()==null)){
						RBTreeNode<T> x = dataRoot.getLeft()==null 
											? parent :dataRoot.getLeft();
						boolean isParent = dataRoot.getLeft()==null;
						fixRemove(x,isParent);
					}
				}
				setParent(dataRoot,null);
				dataRoot.setLeft(null);
				dataRoot.setRight(null);
				if(getRoot()!=null){
					getRoot().setRed(false);
					getRoot().setParent(null);
				}
				size.decrementAndGet();
				return dataRoot.getValue();
			}
		}
		return null;
	}
	/**
	 * fix remove action
	 * @param node
	 * @param isParent
	 */
	private void fixRemove(RBTreeNode<T> node,boolean isParent){
		RBTreeNode<T> cur = isParent ? null : node;
		boolean isRed = isParent ? false : node.isRed();
		RBTreeNode<T> parent = isParent ? node : node.getParent();
		
		while(!isRed && !isRoot(cur)){
			RBTreeNode<T> sibling = getSibling(cur,parent);
			//sibling is not null,due to before remove tree color is balance
			
			//if cur is a left node
			boolean isLeft = parent.getRight()==sibling;
			if(sibling.isRed() && !isLeft){//case 1
				//cur in right
				parent.makeRed();
				sibling.makeBlack();
				rotateRight(parent);
			}else if(sibling.isRed() && isLeft){
				//cur in left
				parent.makeRed();
				sibling.makeBlack();
				rotateLeft(parent);
			}else if(isBlack(sibling.getLeft()) && isBlack(sibling.getRight())){//case 2
				sibling.makeRed();
				cur = parent;
				isRed = cur.isRed();
				parent=parent.getParent();
			}else if(isLeft && !isBlack(sibling.getLeft()) 
									&& isBlack(sibling.getRight())){//case 3
				sibling.makeRed();
				sibling.getLeft().makeBlack();
				rotateRight(sibling);
			}else if(!isLeft && !isBlack(sibling.getRight()) 
											&& isBlack(sibling.getLeft()) ){
				sibling.makeRed();
				sibling.getRight().makeBlack();
				rotateLeft(sibling);
			}else if(isLeft && !isBlack(sibling.getRight())){//case 4
				sibling.setRed(parent.isRed());
				parent.makeBlack();
				sibling.getRight().makeBlack();
				rotateLeft(parent);
				cur=getRoot();
			}else if(!isLeft && !isBlack(sibling.getLeft())){
				sibling.setRed(parent.isRed());
				parent.makeBlack();
				sibling.getLeft().makeBlack();
				rotateRight(parent);
				cur=getRoot();
			}
		}
		if(isRed){
			cur.makeBlack();
		}
		if(getRoot()!=null){
			getRoot().setRed(false);
			getRoot().setParent(null);
		}
		
	}
	//get sibling node
	private RBTreeNode<T> getSibling(RBTreeNode<T> node,RBTreeNode<T> parent){
		parent = node==null ? parent : node.getParent();
		if(node==null){
			return parent.getLeft()==null ? parent.getRight() : parent.getLeft();
		}
		if(node==parent.getLeft()){
			return parent.getRight();
		}else{
			return parent.getLeft();
		}
	}
	
	private boolean isBlack(RBTreeNode<T> node){
		return node==null || node.isBlack();
	}
	private boolean isRoot(RBTreeNode<T> node){
		return root.getLeft() == node && node.getParent()==null;
	}
	/**
	 * find the successor node
	 * @param node current node's right node
	 * @return
	 */
	private RBTreeNode<T> removeMin(RBTreeNode<T> node){
		//find the min node
		RBTreeNode<T> parent = node;
		while(node!=null && node.getLeft()!=null){
			parent = node;
			node = node.getLeft();
		}
		//remove min node
		if(parent==node){
			return node;
		}
		
		parent.setLeft(node.getRight());
		setParent(node.getRight(),parent);
		
		//don't remove right pointer,it is used for fixed color balance
		//node.setRight(null);
		return node;
	}
	
	
	
	private T addNode(RBTreeNode<T> node){
		node.setLeft(null);
		node.setRight(null);
		node.setRed(true);
		setParent(node,null);
		if(root.getLeft()==null){
			root.setLeft(node);
			//root node is black
			node.setRed(false);
			size.incrementAndGet();
		}else{
			RBTreeNode<T> x = findParentNode(node);
			int cmp = x.getValue().compareTo(node.getValue());
			
			if(this.overrideMode && cmp==0){
				T v = x.getValue();
				x.setValue(node.getValue());
				return v;
			}else if(cmp==0){
				//value exists,ignore this node
				return x.getValue();
			}
			
			setParent(node,x);
			
			if(cmp>0){
				x.setLeft(node);
			}else{
				x.setRight(node);
			}
			
			fixInsert(node);
			size.incrementAndGet();
		}
		return null;
	}
	
	/**
	 * find the parent node to hold node x,if parent value equals x.value return parent.
	 * @param x
	 * @return
	 */
	private RBTreeNode<T> findParentNode(RBTreeNode<T> x){
		RBTreeNode<T> dataRoot = getRoot();
		RBTreeNode<T> child = dataRoot;
		
		while(child!=null){
			int cmp = child.getValue().compareTo(x.getValue());
			if(cmp==0){
				return child;
			}
			if(cmp>0){
				dataRoot = child;
				child = child.getLeft();
			}else if(cmp<0){
				dataRoot = child;
				child = child.getRight();
			}
		}
		return dataRoot;
	}
	
	/**
	 * red black tree insert fix.
	 * @param x
	 */
	private void fixInsert(RBTreeNode<T> x){
		RBTreeNode<T> parent = x.getParent();
		
		while(parent!=null && parent.isRed()){
			RBTreeNode<T> uncle = getUncle(x);
			if(uncle==null){//need to rotate
				RBTreeNode<T> ancestor = parent.getParent();
				//ancestor is not null due to before before add,tree color is balance
				if(parent == ancestor.getLeft()){
					boolean isRight = x == parent.getRight();
					if(isRight){
						rotateLeft(parent);
					}
					rotateRight(ancestor);
					
					if(isRight){
						x.setRed(false);
						parent=null;//end loop
					}else{
						parent.setRed(false);
					}
					ancestor.setRed(true);
				}else{
					boolean isLeft = x == parent.getLeft();
					if(isLeft){
						rotateRight(parent);
					}
					rotateLeft(ancestor);
					
					if(isLeft){
						x.setRed(false);
						parent=null;//end loop
					}else{
						parent.setRed(false);
					}
					ancestor.setRed(true);
				}
			}else{//uncle is red
				parent.setRed(false);
				uncle.setRed(false);
				parent.getParent().setRed(true);
				x=parent.getParent();
				parent = x.getParent();
			}
		}
		getRoot().makeBlack();
		getRoot().setParent(null);
	}
	/**
	 * get uncle node
	 * @param node
	 * @return
	 */
	private RBTreeNode<T> getUncle(RBTreeNode<T> node){
		RBTreeNode<T> parent = node.getParent();
		RBTreeNode<T> ancestor = parent.getParent();
		if(ancestor==null){
			return null;
		}
		if(parent == ancestor.getLeft()){
			return ancestor.getRight();
		}else{
			return ancestor.getLeft();
		}
	}
	
	private void rotateLeft(RBTreeNode<T> node){
		RBTreeNode<T> right = node.getRight();
		if(right==null){
			throw new java.lang.IllegalStateException("right node is null");
		}
		RBTreeNode<T> parent = node.getParent();
		node.setRight(right.getLeft());
		setParent(right.getLeft(),node);
		
		right.setLeft(node);
		setParent(node,right);
		
		if(parent==null){//node pointer to root
			//right  raise to root node
			root.setLeft(right);
			setParent(right,null);
		}else{
			if(parent.getLeft()==node){
				parent.setLeft(right);
			}else{
				parent.setRight(right);
			}
			//right.setParent(parent);
			setParent(right,parent);
		}
	}
	
	private void rotateRight(RBTreeNode<T> node){
		RBTreeNode<T> left = node.getLeft();
		if(left==null){
			throw new java.lang.IllegalStateException("left node is null");
		}
		RBTreeNode<T> parent = node.getParent();
		node.setLeft(left.getRight());
		setParent(left.getRight(),node);
		
		left.setRight(node);
		setParent(node,left);
		
		if(parent==null){
			root.setLeft(left);
			setParent(left,null);
		}else{
			if(parent.getLeft()==node){
				parent.setLeft(left);
			}else{
				parent.setRight(left);
			}
			setParent(left,parent);
		}
	}
	
	
	private void setParent(RBTreeNode<T> node,RBTreeNode<T> parent){
		if(node!=null){
			node.setParent(parent);
			if(parent==root){
				node.setParent(null);
			}
		}
	}
	/**
	 * debug method,it used print the given node and its children nodes,
	 * every layer output in one line
	 * @param root
	 */
	public void printTree(RBTreeNode<T> root){
		java.util.LinkedList<RBTreeNode<T>> queue =new java.util.LinkedList<RBTreeNode<T>>();
		java.util.LinkedList<RBTreeNode<T>> queue2 =new java.util.LinkedList<RBTreeNode<T>>();
		if(root==null){
			return ;
		}
		queue.add(root);
		boolean firstQueue = true;
		
		while(!queue.isEmpty() || !queue2.isEmpty()){
			java.util.LinkedList<RBTreeNode<T>> q = firstQueue ? queue : queue2;
			RBTreeNode<T> n = q.poll();
			
			if(n!=null){
				String pos = n.getParent()==null ? "" : ( n == n.getParent().getLeft() 
																		? " LE" : " RI");
				String pstr = n.getParent()==null ? "" : n.getParent().toString();
				String cstr = n.isRed()?"R":"B";
				cstr = n.getParent()==null ? cstr : cstr+" ";
				System.out.print(n+"("+(cstr)+pstr+(pos)+")"+"\t");
				if(n.getLeft()!=null){
					(firstQueue ? queue2 : queue).add(n.getLeft());
				}
				if(n.getRight()!=null){
					(firstQueue ? queue2 : queue).add(n.getRight());
				}
			}else{
				System.out.println();
				firstQueue = !firstQueue;
			}
		}
	}
	
	
	public static void main(String[] args) {
		RBTree<String> bst = new RBTree<String>();
		bst.addNode("d");
		bst.addNode("d");
		bst.addNode("c");
		bst.addNode("c");
		bst.addNode("b");
		bst.addNode("f");
		
		bst.addNode("a");
		bst.addNode("e");
		
		bst.addNode("g");
		bst.addNode("h");

		
		bst.remove("c");

		bst.printTree(bst.getRoot());
	}
}

代码调试的时候,printTree输出格式如下:

d(B)
b(B d LE) g(R d RI)
a(R b LE) e(B g LE) h(B g RI)
f(R e RI)

括号左边表示元素的内容。括号内的第一个元素表示颜色,B表示black,R表示red;第二个元素表示父元素的值;第三个元素表示左右,LE表示在父元素的左边。RI表示在父元素的右边。

第一个元素d是root节点,由于它没有父节点,所以括号内只有一个元素。

3. 总结

作为平衡二叉查找树里面众多的实现之一,红黑树无疑是最简洁、实现最为简单的。红黑树通过引入颜色的概念,通过颜色这个约束条件的使用来保持树的高度平衡。作为平衡二叉查找树,旋转是一个必不可少的操作。通过旋转可以降低树的高度,在红黑树里面还可以转换颜色。

红黑树里面的插入和删除的操作比较难理解,这时要注意记住一点:操作之前红黑树是平衡的,颜色是符合定义的。在操作的时候就需要向兄弟节点、父节点、侄子节点借调和互换颜色,要达到这个目的,就需要不断的进行旋转。所以红黑树的插入删除操作需要不停的旋转,一旦借调了别的节点,删除和插入的节点就会达到局部的平衡(局部符合红黑树的定义),但是被借调的节点就不会平衡了,这时就需要以被借调的节点为起点继续进行调整,直到整棵树都是平衡的。在整个修复的过程中,插入具体的分为3种情况,删除分为4种情况。

整个红黑树的查找,插入和删除都是O(logN)的,原因就是整个红黑树的高度是logN,查找从根到叶,走过的路径是树的高度,删除和插入操作是从叶到根的,所以经过的路径都是logN。

4. 参考文献

  1. Cormen T H, Leiserson C E, Rivest R L, 等. 算法导论(第3版). 殷建平, 等. 机械工业出版社, 2012.

  2. Sedgewick R, Wayne K. 算法(第4版). 谢路云 译. 人民邮电出版社, 2012.

  3. Weiss M A. 数据结构与算法分析(第2版). 冯舜玺 译. 机械工业出版社, 2004.

  4. Knuth D E. 计算机程序设计艺术 卷3:排序与查找(英文版 第2版). 人民邮电出版社, 2010.

2021-03-19-FKBoZL
2021-03-19-nWxfar
2021-03-19-6IuOOO
2021-03-19-GXpcO6
2021-03-19-8OgdFz
2021-03-19-chqPA5
2021-03-19-9erAff
2021-03-19-GF2060
2021-03-19-dXHr58
红黑树深入剖析及Java实现