鲁达 概述
对于一组元素 [7, 3, 10, 12, 5, 1, 9] 可以有很多种存储方式，但无论使用哪种数据结构，都或多或少有缺陷。比如使用线性结构存储，排序方便，但查找效率低。二叉排序树的特点就是能在保证元素有序的同时，提高查找的效率。
二叉排序树的定义
二叉排序树，也叫二叉查找树，二叉搜索树，英文名 Binary Sort Tree（BST）。它或者是一颗空树，或者是一颗具有以下性质的二叉树
- 若左子树不为空，则左子树上所有结点的值均小于它的根结点的值
- 若右子树不为空，则右子树上所有结点的值均大于它的根结点的值
- 左、右子树也分别为二叉排序树
序列 [7, 3, 10, 12, 5, 1, 9] 以二叉排序树存储的结构如图：
创建二叉排序树 & 添加 & 查找 & 遍历
值得注意的是，对二叉排序树作中序遍历，结果正好是一个有序序列。
public class Node { int value; Node left; Node right; public Node(int value) { = value; } /** * 向子树添加结点 * @param node 要添加的结点 */ public void add(Node node) { if (node != null) { // 添加的结点比当前结点的值小 if < ) { // 左结点为空 if == null) { = node; } else { // 左结点不为空 .add(node); } // 添加的结点比当前结点的值大 } else { // 右结点为空 if == null) { = node; // 右结点不为空 } else { .add(node); } } } } /** * 中序遍历 */ public void midShow() { // 输出左结点内容 if (left != null) { le(); } // 输出当前结点内容 Sy(value); // 输出右结点内容 if (right != null) { rig(); } } /** * 查找结点 * @param value 目标结点的值 * @return 目标结点 */ public Node search(int value) { if ( == value) { return this; } else if (value < ) { if (left == null) { return null; } return le(value); } else { if (right == null) { return null; } return rig(value); } } } public class BinarySortTree { private Node root; /** * 向二叉排序树添加结点 * @param node */ public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } /** * 中序遍历 */ public void midShow() { if (root != null) { root.midShow(); } } /** * 查找结点 * @param value 目标结点的值 * @return 目标结点 */ public Node search(int value) { if (root == null) { return null; } else { return root.search(value); } } } 删除结点
二叉排序树的删除操作相对麻烦些，我们不能像以前那样直接删除结点对应的整个子树，而是要把子结点保留下来，并重新拼接成新的排序二叉树。针对不同的情况，也有不同的应对策略：
- 删除叶子结点。直接砍掉就好了，不会对其他结点有影响。
- 删除只有一个子结点的结点。子结点代替原结点的位置。
- 删除有两个子结点的结点。被删除结点同时也是对应二叉排序子树的根结点，根据二叉排序树的性质，根结点就是序列的中间值，所以要补上中间值的位置，要用中间值的后一位的元素（对应右子树的最小结点）或前一位元素（对应左子树的最大结点）
public class BinarySortTree { private Node root; ...... /** * 删除结点 * @param value 要删除结点的值 */ public void delete(int value) { if (root != null) { // 找到目标结点 Node target = search(value); if (target != null) { // 找到目标结点的父结点 Node parent = searchParent(value); // 要删除的结点是叶子结点 if == null && == null) { // 要删除的结点是父结点的左子结点 if () == value) { = null; // 要删除的结点是父结点的右子结点 } else { = null; } // 要删除的结点有两个子结点 } else if != null && != null) { // 删除右子树中值最小的结点，并获取该结点的值 int min = deleteMin(); // 替换目标结点的值 = min; // 要删除的结点只有一个子结点 } else { // 有左子结点 if != null) { // 要删除的结点是父结点的左子结点 if () == value) { // 父结点的左子结点指向目标结点的左子结点 = ; // 要删除的结点是父结点的右子结点 } else { // 父结点的右子结点指向目标结点的左子结点 = ; } // 有右子结点 } else { // 要删除的结点是父结点的左子结点 if == value) { // 父结点的左子结点指向目标结点的左子结点 = ; // 要删除的结点是父结点的右子结点 } else { = ; } } } } } } /** * 删除最小值结点 * @param node 目标二叉树的根结点 * @return 最小值 */ public int deleteMin(Node node) { Node target = node; while != null) { target = (); } delete(); return ; } /** * 查找父结点 * @param value 目标父结点的子结点的值 * @return 目标父结点 */ public Node searchParent(int value) { if (root == null) { return null; } else { return root.searchParent(value); } } } public class Node { int value; Node left; Node right; public Node(int value) { = value; } ...... /** * 查找结点 * @param value 目标结点的值 * @return 目标结点 */ public Node search(int value) { if ( == value) { return this; } else if (value < ) { if (left == null) { return null; } return le(value); } else { if (right == null) { return null; } return rig(value); } } /** * 查找父结点 * @param value 目标父结点的子结点的值 * @return 目标父结点 */ public Node searchParent(int value) { if ( != null && .value == value) || != null && .value == value)) { return this; } else { if != null && > value) { return .searchParent(value); } else if != null && < value) { return .searchParent(value); } else { return null; } } } } 平衡二叉树
上述的排序二叉树，如果结构良好，那么检索数据时的时间开销为 O(logn)，其中 n 为结点个数。但如果排序二叉树的结构畸形，那么最坏时间开销可能为 O(n)，如下图所示：
这样也满足二叉排序树的定义，但和单链表无异，如果是这样的话，那使用排序二叉树还有什么意义呢？所以我们下一步要思考的是如何保证一颗排序二叉树结构良好
平衡二叉树，也叫 AVL 树，除了具有二叉排序树的性质以外，它要求每一个结点的左右子树的高度之差的绝对值不超过一
每一次插入新元素后，树的平衡都有可能被破坏，因此每次插入时都要通过旋转来维持平衡二叉树的结构。假设需平衡的结点为 8，那么破坏平衡的情况有四种：
- 左左：对 8 的左儿子的左子树进行一次插入
- 左右：对 8 的左儿子的右子树进行一次插入
- 右左：对 8 的右儿子的左子树进行一次插入
- 右右：对 8 的右儿子的右子树进行一次插入
要解决上述的问题，找到距离新插入结点最近的不平衡子树进行旋转，对于左左情况使用右旋转，右右情况使用左旋转，可以统称为单旋转。左右和右左情况则使用双旋转。左旋转和右旋的旋转方式是互为镜像的，掌握其中一个，另一个自然也会了。左右、右左也是如此
以左左为例讲解单旋转：
- 找到最近的不平衡子树 8
- 创建一个新结点，值等于当前结点的值，即是 8
- 把新结点的右子树设置为当前结点的右子树，即是 9
- 把新结点的左子树设置为当前结点的左子树的右子树，即是 7，到这里得出下面结果
- 再接下来目的就很明确了，将 6 当作根结点，新结点作为 6 的右儿子，这样就完成了一次右旋转，可以想象成 8 向右转了一个角度
双旋转其实就是做两次旋转，对于左右情况，先对 6 做一次左旋转，然后才是 8 做一次右旋转；对于右左情况，先对 8 做一次右旋转，然后才是 5 做一次左旋转
代码实现如下：
public class AVLNode { int value; AVLNode left; AVLNode right; public AVLNode(int value) { = value; } /** * 返回当前结点的高度 * @return 当前结点的高度 */ public int getHeight() { return Ma(left == null ? 0 : le(), right == null ? 0 : rig()) + 1; } /** * 获取左子树的高度 * @return 左子树的高度 */ public int getLeftHeight() { if (left == null) { return 0; } return le(); } /** * 获取右子树的高度 * @return 右子树的高度 */ public int getRightHeight() { if (right == null) { return 0; } return rig(); } /** * 向子树添加结点 * @param node 要添加的结点 */ public void add(AVLNode node) { if (node != null) { // 添加的结点比当前结点的值小 if < ) { // 左结点为空 if == null) { = node; // 左结点不为空 } else { .add(node); } // 添加的结点比当前结点的值大 } else { // 右结点为空 if == null) { = node; // 右结点不为空 } else { .add(node); } } } // 判断是否平衡 // 进行右旋转 if (getLeftHeight() - getRightHeight() >= 2) { // 双旋转 if (left != null && le() < le()) { // 先左旋转 le(); // 再右旋转 rightRotate(); } else { // 单旋转 rightRotate(); } } // 进行左旋转 if(getLeftHeight() - getRightHeight() <= -2) { if (right != null && rig() < rig()) { // 先右旋转 rig(); // 再左旋转 leftRotate(); } else { // 单旋转 leftRotate(); } } } /** * 左旋转 */ private void leftRotate() { AVLNode node = new AVLNode(value); node.left = left; node.right = rig; value = rig; right = rig; left = node; } /** * 右旋转 */ private void rightRotate() { // 创建一个新结点，值等于当前结点的值 AVLNode node = new AVLNode(value); // 把新结点的右子树设置为当前结点的右子树 node.right = right; // 把新结点的左子树设置为当前结点的左子树的右子树 node.left = le; // 把当前结点的值换为左子结点的值 value = le; // 把当前结点的左子树设置为左子树的左子树 left = le; // 把当前结点的右子树设置为新结点 right = node; } /** * 查找结点 * @param value 目标结点的值 * @return 目标结点 */ public AVLNode search(int value) { if ( == value) { return this; } else if (value < ) { if (left == null) { return null; } return le(value); } else { if (right == null) { return null; } return rig(value); } } /** * 查找父结点 * @param value 目标父结点的子结点的值 * @return 目标父结点 */ public AVLNode searchParent(int value) { if ( != null && .value == value) || != null && .value == value)) { return this; } else { if != null && > value) { return .searchParent(value); } else if != null && < value) { return .searchParent(value); } else { return null; } } } } public class AVLTree { private AVLNode root; /** * 向二叉排序树添加结点 * @param node */ public void add(AVLNode node) { if (root == null) { root = node; } else { root.add(node); } } /** * 查找结点 * @param value 目标结点的值 * @return 目标结点 */ public AVLNode search(int value) { if (root == null) { return null; } else { return root.search(value); } } /** * 删除结点 * @param value 要删除结点的值 */ public void delete(int value) { if (root != null) { // 找到目标结点 AVLNode target = search(value); if (target != null) { // 找到目标结点的父结点 AVLNode parent = searchParent(value); // 要删除的结点是叶子结点 if == null && == null) { // 要删除的结点是父结点的左子结点 if == value) { = null; // 要删除的结点是父结点的右子结点 } else { = null; } // 要删除的结点有两个子结点 } else if != null && != null) { // 删除右子树中值最小的结点，并获取该结点的值 int min = deleteMin(); // 替换目标结点的值 = min; // 要删除的结点只有一个子结点 } else { // 有左子结点 if != null) { // 要删除的结点是父结点的左子结点 if == value) { // 父结点的左子结点指向目标结点的左子结点 = ; // 要删除的结点是父结点的右子结点 } else { // 父结点的右子结点指向目标结点的左子结点 = ; } // 有右子结点 } else { // 要删除的结点是父结点的左子结点 if == value) { // 父结点的左子结点指向目标结点的左子结点 = ; // 要删除的结点是父结点的右子结点 } else { = ; } } } } } } /** * 删除最小值结点 * @param node 目标二叉树的根结点 * @return */ public int deleteMin(AVLNode node) { AVLNode target = node; while != null) { target = ; } delete(); return ; } /** * 查找父结点 * @param value 目标父结点的子结点的值 * @return 目标父结点 */ public AVLNode searchParent(int value) { if (root == null) { return null; } else { return root.searchParent(value); } } }如果觉得本文对你有帮助，可以转发关注支持一下