# DataStruture

**Repository Path**: MoTuoCheRiJi/DataStruture

## Basic Information

- **Project Name**: DataStruture
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-04-22
- **Last Updated**: 2021-12-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

满二叉树
            所有的叶子节点都在最后一层 
            节点总数为 2^n-1

完全二叉树
            所有的叶子节点在最后一层或倒数第二层
            最后一层的叶子结点在左边连续， 空位都在右边

平衡二叉树 
            对于一棵树的来说，最大深度和最小深度的差最多为1
            对于任意一个节点，左子树和右子树的高度差最多为1

二分搜索树
            二分搜索树是二叉树
            二分搜索树的每一个节点的值，大于其左子树的所有节点的值，小于其右字树所有节点的值

堆 二叉堆
            二叉堆是一完全二叉树
            二叉堆分两种：最大堆和最小堆
            最大堆：堆中某个节点的值总是不大于其父节点的值
            
            
 
线段树 （区间查询）不考虑 添加和删除
            二叉树的每一个节点表示一个区间
            
            

字典树
            
            

并查集 
            第一版     quickfind 直接用数组实现
            第二版     将每一个元素看做是一个节点，子节点指向自己的父节点
            第三本     基于size的优化
            第四版     基于rank的优化
            第五版     路径压缩
            第六版     递归实现路径压缩
            
            


平衡二叉树
            对于任意一个节点，左子树和右子树的高度差最多为1
            平衡二叉树是二分搜索树
            AVL树也是一棵二分搜索树，AVL树对二分搜索树的改进，改进了二分搜索树会退化成链表的可能
            二分搜索树->记录高度->计算平衡因子->判断是否是二分搜索树->判断是否是平衡二叉树->右旋转->左旋转

2-3树
            2-3树满足二分搜索树的基本性质
            节点可以存放一个元素或者两个元素
            2-3树一颗绝对平衡的的树，左右两颗字数的高度相等
            添加节点永远不会添加到空的位置

           

红黑树
            红黑树是二分搜索树
            红黑树与2-3树等价