二叉搜索树和AVL树（红黑树前奏）

小咪咪 2022-12-17 07:02 163阅读 0赞

### 二叉搜索树和AVL树 ###

二叉树是指树的每个节点最多只能有两个子节点，如果我们给二叉树加上以下条件，就可以得到二叉搜索树

二叉搜索树要求：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 
    若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 
    它的左、右子树也分别为二叉排序树。

查找值比当前节点值大，则搜索右子树；
    查找值等于当前节点值，停止搜索（终止条件）；
    查找值小于当前节点值，则搜索左子树；

二叉搜索树插入节点：

要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，
    待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，
    反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置

二叉搜索树遍历节点：

遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历。
    中序遍历:左子树——》根节点——》右子树
    前序遍历:根节点——》左子树——》右子树
    后序遍历:左子树——》右子树——》根节点

要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。  
同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值

删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。

1.  该节点是叶节点（没有子节点），只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 3]
2.  该节点有一个子节点，只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 4]
3.  该节点有两个子节点，那么删除之后，两个子节点的位置我们就没办法处理了。  
    既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？  
    我们知道二叉搜索树中的节点是按照关键字来进行排列的，某个节点的关键字次高节点是它的中序遍历后继节点。  
    用后继节点来代替删除的节点，显然该二叉搜索树还是有序的  
    那么如何找到删除节点的中序后继节点呢？实际上就是要找比删除节点关键值大的节点集合中最小的一个节点，  
    只有这样代替删除节点后才能满足二叉搜索树的特性。
    
    **后继节点也就是：比删除节点大的最小节点**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 5]  
普通二叉搜索树致命缺陷：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 6]  
怎么解决 二叉搜索树 退化成线性链表的问题？  
如果插入元素时，树可以自动调整两边平衡，会保持不错的查找性能。  
所以有了AVL树

AVL树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 7]

**AVL树有什么特点？**  
1、具有二叉查找树的全部特性。  
2、每个节点的左子树和右子树的高度差至多等于1

**为什么有了平衡树还需要红黑树？**

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，  
因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，  
几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。  
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树！！！

现在我们再来看红黑树就不会很迷了，关于红黑树我写在了另一篇文章中  
[红黑树原理讲解][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1ecdc185839e4f56b72d5ac59c238072.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/a2adf0004f0f4826903658f27e3d3f97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/868d43f953d44564a5155922a3582705.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/3e6a696e5c4d434b9d3988ee700d2a66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/fa5298952b5a48b398c652c0ab72941f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/71ed8e2f4b7f410498cda8904696627d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/3898c10a7bd1463ab9e76dd1440b4886.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/bf3e4db887f04fc08df2371c77532b92.png
[Link 1]: https://blog.csdn.net/weixin_44624410/article/details/109222181