平衡二叉查找树的插入删除查找操作

1、删除的节点可能是叶子节点，也有可能不是，不是的话就对要删除节点的子节点前序遍历找到后继节点

 

2、查询操作

二叉查找树的查询复杂度，和二分查找一样，插入和查找的时间复杂度均为 O(logn) ，但是在最坏的情况下仍然会有 O(n) 的时间复杂度（线性链表结构）。

由于普通二叉查找树会容易失去平衡，极端情况下二叉查找树会退化成线性的链表，导致插入查找复杂度变为O(N),所以引入了平衡二叉树（对左右子树的高度差进行限制）

3、

左旋

右旋

平衡二叉树插入操作以后不平衡问题：

不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。

 参考：https://blog.****.net/qq_25940921/article/details/82183093

左图在没插入前”19“节点前，该树还是平衡二叉树，但是在插入”19“后，导致了”15“的左右子树失去了”平衡“，所以此时可以将”15“节点进行左旋，让”15“自身把节点出让给”17“作为”17“的左树，使得”17“节点左右子树平衡，而”15“节点没有子树，左右也平衡了。（右边多左旋把右边的旋转到左边）如下图，

 

 参考：https://blog.****.net/qq_25940921/article/details/82183093

这篇博客详细讲了左右旋的使用

总结一下就是：

左左，左右，右左，右右。

例如：在原来平衡二叉树基础上左子树节点下右子树下插入：左右

左左   右旋

左右   左旋  +  右旋

右左   右旋  +  左旋

右右   左旋