前言
整理了一下记录在手机中的技术知识点,包含JAVA、MYSQL、数据结构等,自用笔记,放博客上备份以备不时之需,如若有人发现错误还请指出。
由于太长,分成两篇记录,笔记二地址: 自自技术笔记(二)
红黑树笔记
红黑树
红黑树其实就是平衡二叉树,该规则可保证每个节点都是平衡的,不会出现单个节点过长的情况
红黑树的作用,红黑树是一种平衡二叉树,不会退化为链表,多用于搜索查找,时间复杂度logn,也就是树的深度,倍数增长,红黑树是局部平衡二叉树
普通二叉树的局限性是子节点都比父节点小因此全排在右,会退化成链表
红黑树4个性质
- 1.节点是红色或者黑色
- 2.红色节点不会连在一起(子父节点不能同为红色)
- 3.根节点都是黑色
- 4.空的叶子节点都是黑色(既无子节点)
红黑树有三种变化规则
1.红变黑 2.黑变红 3.旋转
红黑树的操作规则
- 0.所有变换后的节点不可违背红黑树的基本性质,既当插入节点后规则不符合红黑树基本性质时依次尝试,变色、左旋、右旋
- 1.所有插入的节点默认为红色
- 2.变换颜色条件,当子节点和父节点以及父节点的兄弟节点都是红色时需要变换颜色,颜色变换规则为将父节点以及父节点的兄弟节点变换成红色,将祖节点变换为红色
- 3.左旋条件,当前节点的父节点是红色,叔叔节点是黑色,且当前节点是父节点的右子树时,旋转父节点和祖节点
- 4.右旋条件,当前父节点是红色,叔叔节点是黑色,且当前节点是左子树时右旋转,与左旋不同的是右旋转操作是旋转祖节点和祖父节点
右旋有3步
- 1.把父节点变为黑色
- 2.把祖节点变为红色
- 3.把以祖节点为旋转点旋转(不同于左旋以父节点为旋转点)