数据结构：二叉树、红黑树等

谁践踏了优雅 2023-02-25 10:30 13阅读 0赞

> **二叉查找树**： 二叉查找树又叫二叉搜索树、二叉排序树。  
> 1、如果它的左子树不为空，则左子树上的结点的值都小于根节点。  
> 2、如果它的右子树不为空，则右子树上的结点的值都小于根节点。  
> 3、子树同样也要遵循以上2点。
> 
> **时间复杂度**：O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(nk) < O(2n)  
>     二叉查找树：  
>         平衡：2^x=n(数据个数) x=log2n  => O(log2n)   
>         不平衡：O(n),退化为链表，有几个数对比几次。  
>     Arraylist：  
>         O(1),因为是通过唯一下标查找唯一值。  
>           
> **AVL树**：平衡二叉树，它的左右子树高度之差不超过1。
> 
> **红黑树**：特殊的二叉查找树  
>     演变过程：链表 -> 二叉树 -> 二叉查找树 -> 红黑树  
>     性质(规则)：  
>         1、不是黑色就是红色  
>         2、不可能存在相邻2个红色节点  
>         3、根节点都是黑的  （root节点）  
>         4、红色节点的两个子节点都是黑色。叶子节点都是黑色。
> 
>     红黑树变换规则：  
>         旋转和颜色变换规则： 所有插入的点默认为红色。  
>         1、变色要求：当前结点的父亲是红色，且它的叔叔结点也是红色  
>             （1）把父节点设为黑色     
>             （2）把叔叔节点也设为黑色   
>             （3）把祖父节点设为红色（爷爷节点）  
>             （4）把指针定义到祖父节点设为当前要操作的节点。（爷爷节点） 分析的点变换的规则  
>         2、左旋要求：当前父节点是红色，叔叔节点是黑色，且当前的节点是右子树。进行左旋。  
>             （1）根节点左下进1，  
>             （2）根节点的右子节点左上进1  
>             （3）根节点的右子节点的左子节点 变更为 根节点的右子节点  
>         3、右旋要求：当前父节点是红色，叔叔节点是黑色，且当前的节点是左子树。进行右旋。  
>             （1）根节点右下进1，  
>             （2）根节点的左子节点右上进1  
>             （3）根节点的左子节点的右子节点 变更为 根节点的左子节点