【数据结构与算法之树结构】二叉排序树与AVL树

冷不防 2024-03-25 14:12 109阅读 0赞

#### 【数据结构与算法之树结构】二叉排序树与AVL树 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之树结构】二叉排序树与AVL树

二叉排序树也称为二叉查找树。

它或者是一棵空树，或者是具有下列性质的二叉树：

*  若其左子树不为空，则其左子树上所有节点的值均小于根节点
 *  若其右子树不为空，则其右子树上所有节点的值均大于根节点。
 *  二叉排序树的左右子树都是二叉排序树。

![在这里插入图片描述][a7118b5f0124431a83cfd1bb6c59e65f.png_pic_center]

除了在二叉排序树中查找节点，还可以向二叉排序树中插入节点。因为二叉排序树主要用作动态查找表，也就是表结构可以在查找的过程中动态生成，所以插入节点的操作通常在查找不成功时进行，而且新插入节点一定是查找路径上最后一个节点的左孩子或右孩子，插入后二叉树仍然是一棵二叉排序树。

![在这里插入图片描述][ddd70eb6b4ad4e369aa5c09d49424ab5.png_pic_center]

但是删除操作要复杂一些，因为删除节点后还要仍然需要保持二叉排序树的结构

三种情况：

*  删除的节点为P，P是二叉排序树的叶子节点，直接删除即可( 修改该叶子节点的双亲节点的指针域)。
    
    ![在这里插入图片描述][2aa5cc9b7fba449c8003fbdc4d8c5dec.png_pic_center]
 *  要删除的节点为P，其双亲节点为Q，且P节点只有左子树 P L P\_L PL 或者右子树 P R P\_R PR，则删除P节点后， P L 或 P R P\_L 或 P\_R PL或PR 直接取代P的位置，成为Q的左子树或右子树。
    
    ![在这里插入图片描述][a00c6291e0244d9da32ebca5ac8fe9b7.png_pic_center]
 *  要删除的节点为P，双亲节点为Q，且P节点既有左子树 P L P\_L PL 又有  P R P\_R PR，则处理起来比较复杂。
    
     *  第1种方法是将P的右子树 P R P\_R PR 变为S的右子树，然后将P 的左子树 P L P\_L PL 变为Q的左子树。
        
        ![在这里插入图片描述][3df0506457c94d69a3e74cf86ea4811c.png_pic_center]
     *  第2种方法是用P节点在中序遍历序列中的直接前驱，即S，代替P节点，这样S节点就从原来的位置上被删除，S节点的左子树 S L S\_L SL(如果存在)则直接作为 R 节点的右子树。
        
        ![在这里插入图片描述][97abaf11ba7040be88d927987c14491f.png_pic_center]

在一棵具有n个 节点的二叉排序树中随机查找一个节点的时间复杂度为  O ( l o g 2 n ) O(log\_2^n) O(log2n)。

如果创建二叉排序树时插入的关键字是按值有序的，则该二叉排序树会退化为单枝树，在这样的二叉排序树中查找元素相当于在一个线性序列中顺序查找，时间复杂度为  O ( n ) O(n) O(n)，这样体现不出二叉排序树的优势。

![在这里插入图片描述][4cac4226c59643aba125d185227dfe6f.png_pic_center]

所以最好的情况是二叉排序树完全处于平衡状态，此时二叉排序树的形态与折半查找的判定树相同，平均查找长度与  l o g 2 n log\_2^n log2n 成正比。

![在这里插入图片描述][ecfc488987b049ed902f8de6482836b5.png_pic_center]

为了使得二叉排序树始终尽可能的保持平衡，AVL 树诞生了。

AVL树或者是一棵空树，或者是具有下面性质的二叉树：

*  它的左右子树都是AVL树
 *  左右子树的深度差绝对值不超过1

[a7118b5f0124431a83cfd1bb6c59e65f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/adac2a8510344cb3b3b4c8d9a938798c.png
[ddd70eb6b4ad4e369aa5c09d49424ab5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c5c86158ede8424292ae623c0bf1bf15.png
[2aa5cc9b7fba449c8003fbdc4d8c5dec.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0087edfe612646f898d5beae9e4cffb6.png
[a00c6291e0244d9da32ebca5ac8fe9b7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/723b30196b7e482e8d8306eb6374b452.png
[3df0506457c94d69a3e74cf86ea4811c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c33a563e885f42f4b550b5950c25fd43.png
[97abaf11ba7040be88d927987c14491f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/101d94103d1c4719957d12ddbcd82a1d.png
[4cac4226c59643aba125d185227dfe6f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f912bcc314da4c009fd2453c2f5f136a.png
[ecfc488987b049ed902f8de6482836b5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/fda9b80d870340adb6c00ce74d73e613.png