# Go实现红黑树RBTree

**Repository Path**: winie/RBTree

## Basic Information

- **Project Name**: Go实现红黑树RBTree
- **Description**: Go实现的红黑树，节点中的数据结构可以自己定义
- **Primary Language**: Go
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-07-03
- **Last Updated**: 2022-07-03

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# RBTree

#### 介绍
Go实现的红黑树，树中节点中的数据结构可以自己定义  

#### 软件架构  
在调整平衡和插入的时候加了读锁  
因此在并发的情况下，保证查询数据的时候是树平衡的状态  
而且实现了一些操作红黑树的基本常用的函数  
但是interface数据接口得自己根据自己的需求定义  
    1、我设计的是通常是要存结构体的，要把结构体中的一项值作为ID  
    2、存进去一个结构体，如果树中有结构体的ID值和你要存的结构体ID值一样，则那个节点会修改为现在的结构体的内容  
    3、2的特性就像 map数据结构一样 map[key]value   key是唯一的  
    

#### 安装教程
git clone https://gitee.com/hoemfei/RBTree.git   
mv RBTree /你自己的项目目录里    



#### 使用说明
需要自己根据自己的需求定义自己的数据结构  
你要明白的是红黑树中每个节点的结构体是以下这些，其中的Item 数据接口是需要你自己定义的
修改interface.go 文件即可，怎么修改已经写在了interface.go 文件里了

红黑树节点结构  
type rbNode struct{   
	Left *rbNode  //左节点  
	Right *rbNode  //右边节点  
	Parent *rbNode //父亲节点  
	Color bool      //颜色  
	Item//数据接口  
}    

以下是基本的使用方法

MyRBTree := RBTree.NewRBTree()                                      //new一个树  
  
MyStruct := RBTree.MyInfo{ID: 1, Name: "王飞", Age: 18}             // 自己的结构体  
  
MyRBTree.Insert(MyStruct)                                           //向树中插入你的结构体    
  
fmt.Println(MyRBTree.Search(RBTree.MyInfo{ID: 1}).GetInfo())        //搜索ID 为1 的节点，返回结构体{王飞 18 1}    
  
fmt.Println(MyRBTree.SearchLe(RBTree.MyInfo{ID:2}).GetInfo())       //近似搜索ID 为2的节点，如果树中没有，则会返回最相近的一个节点,返回结构体{王飞 18 1}   
  
fmt.Println(MyRBTree.Len())                                         //获取树中的节点个数  
  
fmt.Println(MyRBTree.GetDepth())                                    //获取树的高度  
  
MyRBTree.PrePrintAll()                                              //前序遍历整个树  
  
MyRBTree.InPrintAll()                                               //中序遍历整个树  
  
MyRBTree.PostPrintAll()                                             //后续遍历整个树  
  
MyRBTree.Delete(RBTree.MyInfo{ID: 1})                               //删除ID为1的 节点  
  

当然以下这样写都可以，主要就是靠你传进去的结构体中的ID来找的  
MyRBTree.Delete(Mystruct).GetInfo()    
MyRBTree.Search(Mystruct).GetInfo()  
MyRBTree.SearchLe(Mystruct).GetInfo()    


![使用例子](https://images.gitee.com/uploads/images/2021/0611/130045_039c8074_6507691.png "微信截图_20210611130027.png")
![测试例子](https://images.gitee.com/uploads/images/2021/0611/130238_43f07140_6507691.png "2.png")