# dataStruct

**Repository Path**: myd123/data-struct

## Basic Information

- **Project Name**: dataStruct
- **Description**: AVL,    
RED_BLACK Tree,      
B+ Tree/BPlusTree
- **Primary Language**: Java
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2022-05-11
- **Last Updated**: 2023-09-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Java, red-blackTree, bplustree, avl

## README

# dataStruct

![image](./balanceTree/src/main/resources/picture/staffbase.svg)
![image](./balanceTree/src/main/resources/picture/magento.svg)
#### 介绍
暂时只有以下几种数据结构的实现：<br>
<B>AVL<br>
RED_BLACK Tree<br>
B+ Tree

<hr>

#### AVL Tree 
avl树是一个平衡二叉搜索树，平衡要求： 所有节点的左右分支高度差不能大于1；<br>
avl树的最重要操作的是旋转；当节点不平衡的时候通过旋转来调节节点的平衡；总共有四种不平衡类型：
- LL
- LR
- RR
- RL

旋转其实非常简单，只要自己动手在纸上画一下旋转的操作就明白了；<br>
旋转在红黑树，B+ 树 ，中也会遇到，因此这是一个必须要掌握的;

<hr>

### red_black Tree

红黑树其实也是一种平衡二叉搜索树，只不过他对平衡的要求没有那么严格；红黑树通过定义来限制了红黑树的高度和调整策略；<br>
红黑树定义：
- 1.根节点是黑色
- 2.叶子节点是黑色（不同于一般定义的叶子节点，红黑树中叶子节点都是null节点）
- 3.所有节点只能是红色或者黑色节点
- 4.不能出现连续的红色节点
- 5.所有从叶子节点到根节点的黑色节点树相等

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;红黑树在add操作时需要调节平衡情况：出现连续红色节点时，要如何调整节点颜色保持所有分支到root节点的黑色节点数目相等？这其实比较简单,只需要考虑4种类型的旋转即可<br>
delete操作这是红黑树调整平衡的难点，当删除黑色节点时就必须要调整节点的颜色了；关于这部分讨论其实网上有很多博客都有详细的分析，但是很少有从整体分析然后再到细节的，基本只分析了细节没有从整体上来讲为什么要这么做。<br>
又因为红黑树的情况比较多（其实大多都是对称的，去掉对称结构来看其实情况也并不是很复杂）当你分析红黑树时直接分析细节就会觉得细节点太多导致你看不清整个操作的目的迷失在细节中，自然就G了。因此，我们需要先从整体到细节的过程来分析，
下面我简单的说下自己的理解，红黑树在删除时会有以下几种情况：
- 1.被删除的节点是叶子节点
- 2.被删除的节点有一个节点
- 3.被删除的节点有2个节点
#### 1.被删除的节点是叶子节点 
- 1.1 被删除节点颜色是红色；<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;====> 直接删除
- 1.2 被删除节点颜色是黑色；(最复杂的情况)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;====>删除黑色节点直接破坏了定义的第5个条件，需要调整节点颜色；这种情况从细节上来说情况比较多；但从整体上来讲调整的目的很简单；
可以分为2种情况：<br>
     - 1.2.1 通过旋转，相当于从兄弟节点借一个红色节点过来染成黑色来补充被因删除而损失的黑色节点；这样即可以保持该分支的黑色节点数不变，又不会影响兄弟节点的黑色节点数；这对兄弟节点及其子节点的颜色有要求满足下面2个条件的任何一个，就可以通过一次旋转操作来平衡红黑树<br>
        - 兄弟节点颜色是红色
        - 兄弟节点是黑色，兄弟节点的子节点有红色节点
     - 1.2.2 当兄弟节点是黑色并且兄弟节点的子节点也是黑色，直接将兄弟节点的颜色染红来保持当前节点的父节点:parent的左右分支的黑色节点数相同；<br>
     但是这样操作会导致一个问题，所有经过parent节点的黑色节点数比不经过parent节点的黑色节点数少一个；这个时候需要判断parent颜色：
        - 如果parent是红色，直接染黑parent增加一个黑色节点保持删除前后黑色节点数不变；
        - 如果parent是黑色，则不能通过染黑parent来增加黑色节点；这个时候只能将parent节点当作需要被调节的点，重复1.2.1  ,  1.2.2的操作；<br>
        如果一直没能通过旋转的操作从兄弟节点中获取到一个节点来补充当前分支损失的黑色节点，就要一直向上递归到root节点；让所有的分支都减少一个黑色节点保持所有分支黑色节点数相同；<br>


#### 2.被删除的节点有一个节点

我们只需要想清楚一个问题：当一个节点node只有一个子节点时，node节点的颜色一定是黑色。

证明：<br>
假设node颜色是红色，那么子节点: son颜色一定是黑色；
    
                   node(red)
                    /   \
                   /     \
                  /       \
            son(black)    null(black)
             /   \
            /     \
           /       \
          /         \
         /           \
     null(black)    null(black)

当node是红色时可以通过上图看出，必定会导致node节点的左右分支黑色节点数不一样；<br>
因此node节点的颜色只能是黑色并且子节点颜色一定是红色；这样才能保持node左右分支黑色节点数相同；（这个可以自己画图证明,为什么son一定是红色）<br>
想清楚上面的问题之后，实际操作其实非常简单；将son节点数据和node节点数据互换，然后删除son节点即可；<br>
因为son是红色节点删除红色节点不会影响红黑树，因此不用调节红黑树；

#### 3.被删除的节点有2个节点
直接找左分支的最大值（或者找右分支的最小值）来代替被删除的节点；这样就会将删除的情形转化成上面2种情况；


       
<hr>
        
### B+ tree

未完待续。。

<hr>




#### 特技

1.  使用 Readme\_XXX.md 来支持不同的语言，例如 Readme\_en.md, Readme\_zh.md
2.  Gitee 官方博客 [blog.gitee.com](https://blog.gitee.com)
3.  你可以 [https://gitee.com/explore](https://gitee.com/explore) 这个地址来了解 Gitee 上的优秀开源项目
4.  [GVP](https://gitee.com/gvp) 全称是 Gitee 最有价值开源项目，是综合评定出的优秀开源项目
5.  Gitee 官方提供的使用手册 [https://gitee.com/help](https://gitee.com/help)
6.  Gitee 封面人物是一档用来展示 Gitee 会员风采的栏目 [https://gitee.com/gitee-stars/](https://gitee.com/gitee-stars/)