平衡二叉搜索树详解

平衡二叉搜索树

平衡二叉搜索树(英语：Balanced Binary Search Tree)是一种结构平衡的[二叉搜索树] ，它是一种每个节点的左右两子[树] 高度差都不超过一的[二叉树] 。它能在O(logn)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为[AVL树] 。

之前的BST已经可以解决很多查找问题，而且时间复杂度在O(logN),但是如果出现单支树的情况，时间复杂度就会退化到O(N),也就是类似于单链表的查询。

AVL树

AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

平衡因子

它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(Balance Factor)定义为LH-RH，那么BF只能是-1,0,1。只要|BF|>=1，则二叉树就是不平衡的。

平衡二叉树

不平衡的二叉树

旋转

OK，现在我们一眼可以看出哪种是平衡，哪种是不平衡的。如果不平衡的二叉树，就需要做旋转

哪些操作会导致原来平衡的二叉树，变得不平衡?插入一个新的节点，或者删除一个节点，都有可能导致二叉树的平衡结构被破坏。此时就会需要通过自身旋转，来修复。

假设平衡因子是左子树的高度减去右子树的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先节点)，则失去平衡后进行的规律可归纳为下列四种情况：

单向右旋平衡处理LL：由于在*a的左子树根节点的左子树上插入节点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行一次右旋转操作;

单向左旋平衡处理RR：由于在*a的右子树根节点的右子树上插入节点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行一次左旋转操作;

双向旋转(先左后右)平衡处理LR：由于在*a的左子树根节点的右子树上插入节点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行两次旋转(先左旋后右旋)操作。

双向旋转(先右后左)平衡处理RL：由于在*a的右子树根节点的左子树上插入节点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作。