写在前面
前面讲了树的基本概念，这篇文章主要讲常见的树的基本操作，如查找，新增，删除等。其中通过动图的方式使得更加容易理解。
二叉查找树
二叉查找树（BST，Binary Sort Tree）,也称二叉排序树，或二叉搜索树。一棵二叉查找树满足以下条件：
左子树的所有值均小于根节点的值
右子树的所有值均大于根节点的值
左右子树同时也满足以上两点
通俗来说就是一棵二叉树，节点左小右大。
BST 插入操作
一棵二叉查找树的插入操作，如果插入的值 x 从根节点开始：
x 值小于该节点值，在左子树中继续
x 值大于该节点值，在右子树中继续
如果节点是叶节点，X 值小于该节点值则插入左子节点，否则插入右节点
在上面的二叉排序树中，如果我们插入节点的值为 80，具体操作如下：
BST 查找操作
一棵二叉查找树的查找操作，如果查找的值 x 从根节点开始：
如果 x 小于根节点，则在左子树中继续查找
如果 x 大于根节点，则在右子树中继续查找
如果 x 的值等于根节点，则返回该节点
如果都查找不到，则返回 null
在上面的二叉排序树中，如果我们需要查找节点的值为 10 的节点，具体操作如下：
BST 删除操作
一棵二叉查找树的删除操作，如果删除的值 x 从根节点开始：
如果节点的值等于 x，则删除
x 值小于该节点值，在左子树中继续
x 值大于该节点值，在右子树中继续
如果我们删除节点的值为 80，具体操作如下：
代码实现
public class BSTTree {
/** * 节点 */ public static class Node { //数据，为简化代码，本程序默认节点里存储一个int变量，实际程序里可以存储自定义类型变量 int data; //左子节点 Node leftChild; //右子节点 Node rightChild;
public Node(int data) { this.data = data; } }
/** * 新增节点 采用递归的方式 * * @param root 根节点 * @param data 插入的数据 * @return */ public static Node insert(Node root, int data) { if (root == null) { root = new Node(data); return root; } //若插入的数据小于根节点，插入到其左子树 if (data <= root.data) { root.leftChild = insert(root.leftChild, data); } else { //插入到其右子树 root.rightChild = insert(root.rightChild, data); } return root; }
/** * 查找数据 * * @param data * @return */ public static Node find(Node root, int data) { //若查找的数据小于根节点，则向左查找（也可以采用递归的方式查找） Node current = root; while (current != null) { if (data < current.data) { current = current.leftChild; } else if (data > current.data) { //向右查找 current = current.rightChild; } else { return current; } } return null; }
/** * 删除节点 * 1.该节点是叶子节点，即没有子节点 * 2.该节点有一个子节点 * 3.该节点有两个子节点（通过该节点的中续后继节点来代替删除的节点） * 中续后继节点：比该节点值次高的节点为中续后继节点，如节点4的后继节点为5 * 3 * / \ * 2 4 * / / \ * 1 5 6 * * @param root * @param data 要删除的节点 * @return 删除后的节点 */ public static Node delete(Node root, int data) { //用来表示要删除节点的父节点 Node parent = root; //是否为左子节点 boolean ifLeftChild = true; Node current = root; //定位删除节点的位置及其父节点 while (current != null) { //父节点 parent = current; if (data < current.data) { ifLeftChild = true; current = current.leftChild; } else if (data > current.data) { ifLeftChild = false; current = current.rightChild; } else { return current; } } //1.该节点是叶子节点 if (current.leftChild == null && current.rightChild == null) { //若为根节点,删除整棵树 if (current == root) { root = null; //GC } //若为左子节点 if (ifLeftChild) { parent.leftChild = null; } else { parent.rightChild = null; } } //2.该节点有一个子节点 if (current.leftChild != null && current.rightChild == null) {//若删除节点的左子节点不为null if (current == root) { root = current.leftChild; } if (ifLeftChild) { //若为左子节点 parent.leftChild = current.leftChild; } else { parent.rightChild = current.leftChild; } } else if (current.leftChild == null && current.rightChild != null) { if (current == root) { root = current.rightChild; } if (ifLeftChild) { //若为左子节点 parent.leftChild = current.rightChild; } else { parent.rightChild = current.rightChild; } } //3.该节点有两个子节点， if (current.leftChild != null && current.rightChild != null) { //获取删除节点的后继结点 Node successor = getSuccessor(current); if (root == current) { root = successor; } else if (ifLeftChild) { parent.leftChild = successor; } else { parent.rightChild = successor; } } return parent; }
/** * @param node 要删除的节点(假设此时该节点存在左右子节点) * @return 删除节点的后继节点 */ public static Node getSuccessor(Node node) { Node successorParent = node; Node successor = node; Node current = node.rightChild; while (current != null) { successorParent = successor; successor = current; current = current.leftChild; } if (successor != node.rightChild) { successorParent.leftChild = successor.rightChild; successor.rightChild = node.rightChild; } return successor; }
public static void main(String[] args) { /* * 新增操作 * 3 * / \ * 2 4 * / / \ * 1 5 6 */ Node root = null; root = insert(root, 3); root = insert(root, 2); root = insert(root, 1); root = insert(root, 4); root = insert(root, 6); root = insert(root, 5); printTree(root); System.out.println("---------"); //查找操作 4 Node node = find(root, 4); printTree(node); System.out.println("---------"); //删除操作 Node delete = delete(root, 2); printTree(delete); }
/** * 打印 * * @param root */ public static void printTree(Node root) { System.out.println("根节点" + root.data); if (root.leftChild != null) { System.out.print("左子节点:"); printTree(root.leftChild); } if (root.rightChild != null) { System.out.print("右子节点:"); printTree(root.rightChild); } }}
复制代码
平衡二叉树（AVL）
平衡二叉树（AVL），是一个二叉排序树，同时任意节点左右两个子树的高度差（或平衡因子，简称 BF）的绝对值不超过 1，并且左右两个子树也满足。
为什么使用平衡二叉树
通过二叉查找树的查找操作可以发现，一棵二叉查找树的查找效率取决于树的高度，如果使树的高度最低，那么树的查找效率也会变高。
如下面一个二叉树，全部由右子树构成
这个时候的二叉树其实就类似于链表，此时的查找时间复杂度为 O(n)，而 AVL 树的查找时间复杂度为 O(logn)。之前讲过 O(logn)耗时是小于 O(n)的，如下：
可参考：常见数据结构的时间复杂度
平衡二叉树的调整
一棵平衡二叉树的插入操作会有 2 个结果：
如果平衡没有被打破，即任意节点的 BF=1，则不需要调整
如果平衡被打破，则需要通过旋转调整，且该节点为失衡节点
一棵失衡的二叉树通过以下调整可以重新达到平衡：
左旋：旧根节点为新根节点的左子树，新根节点的左子树（如果存在）为旧根节点的右子树
右旋：旧根节点为新根节点的右子树，新根节点的右子树（如果存在）为旧根节点的左子树
通过旋转最小失衡子树来实现失衡调整：
在一棵平衡二叉树新增节点，在新增的节点向上查找，第一个平衡因子的绝对值超过 1（BF>1）的节点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，有可能多棵子树同时失衡，这时只需要调整最小的不平衡子树即可。
看完下面的旋转方式之后再回来看最小失衡子树旋转就很清晰了
LL 旋转
向左子树（L）的左孩子（L）插入新节点
插入节点在失衡节点的左子树的左边，经过一次右旋即可达到平衡，如下
旋转过程
RR 旋转
插入节点在失衡节点的右子树的右边，经过一次左旋即可达到平衡，如下
旋转过程
LR 旋转
插入节点在失衡节点的左子树的右边，先左旋，再右旋，如下
旋转过程
RL 旋转
插入节点在失衡节点的右子树的左边，先右旋，再左旋，如下
旋转过程
代码实现
public class AVLTree { //节点 public static class Node { int data; //数据 Node leftChild; //左子节点 Node rightChild;//右子节点 int height; // 记录该节点所在的高度
public Node(int data) { this.data = data; } } //获取节点的高度 public static int getHeight(Node p){ return p == null ? -1 : p.height; // 空树的高度为-1 } public static void main(String[] args) { Node root = null; root = insert(root,40); root = insert(root,20); root = insert(root,50); root = insert(root,10); root = insert(root,30); //插入节点在失衡结点的左子树的左边 root = insert(root,5); //打印树，按照先打印左子树，再打印右子树的方式 printTree(root);
}
public static void printTree(Node root) { System.out.println(root.data); if(root.leftChild !=null){ System.out.print("left:"); printTree(root.leftChild); } if(root.rightChild !=null){ System.out.print("right:"); printTree(root.rightChild); } } // AVL树的插入方法 public static Node insert(Node root, int data) { if (root == null) { root = new Node(data); return root; } if (data <= root.data) { // 插入到其左子树上 root.leftChild = insert(root.leftChild, data); //平衡调整 if (getHeight(root.leftChild) - getHeight(root.rightChild) > 1) { if (data <= root.leftChild.data) { // 插入节点在失衡结点的左子树的左边 System.out.println("LL旋转"); root = LLRotate(root); // LL旋转调整 }else{ // 插入节点在失衡结点的左子树的右边 System.out.println("LR旋转"); root = LRRotate(root); } } }else{ // 插入到其右子树上 root.rightChild = insert(root.rightChild, data); //平衡调整 if(getHeight(root.rightChild) - getHeight(root.leftChild) > 1){ if(data <= root.rightChild.data){//插入节点在失衡结点的右子树的左边 System.out.println("RL旋转"); root = RLRotate(root); }else{ System.out.println("RR旋转");//插入节点在失衡结点的右子树的右边 root = RRRotate(root); } } } //重新调整root节点的高度值 root.height = Math.max(getHeight(root.leftChild), getHeight(root.rightChild)) + 1; return root; }
/** * LR旋转 */ public static Node LRRotate(Node p){ p.leftChild = RRRotate(p.leftChild); // 先将失衡点p的左子树进行RR旋转 return LLRotate(p); // 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
}
/** * RL旋转 */ public static Node RLRotate(Node p){ p.rightChild = LLRotate(p.rightChild); // 先将失衡点p的右子树进行LL平衡旋转 return RRRotate(p); // 再将失衡点p进行RR平衡旋转并返回新节点代替原失衡点p }
/* * LL旋转 * 右旋示意图(对结点20进行右旋) * 40 20 * / \ / \ * 20 50 10 40 * / \ LL旋转 / / \ * 10 30 5 30 50 * / * 5 */ public static Node LLRotate(Node p){ // 40为失衡点 Node lsubtree = p.leftChild; //失衡点的左子树的根结点20作为新的结点 p.leftChild = lsubtree.rightChild; //将新节点的右子树30成为失衡点40的左子树 lsubtree.rightChild = p; // 将失衡点40作为新结点的右子树 // 重新设置失衡点40和新节点20的高度 p.height = Math.max(getHeight(p.leftChild), getHeight(p.rightChild)) + 1; lsubtree.height = Math.max(getHeight(lsubtree.leftChild), p.height) + 1; return lsubtree; // 新的根节点取代原失衡点的位置 } /* * RR旋转 * 左旋示意图(对结点20进行左旋) * 20 40 * / \ / \ * 10 40 20 50 * / \ RR旋转 / \ \ * 30 50 10 30 60 * \ * 60 */ public static Node RRRotate(Node p){ // 20为失衡点 Node rsubtree = p.rightChild; //失衡点的右子树的根结点40作为新的结点 p.rightChild = rsubtree.leftChild; //将新节点的左子树30成为失衡点20的右子树 rsubtree.leftChild = p; // 将失衡点20作为新结点的左子树 // 重新设置失衡点20和新节点40的高度 p.height = Math.max(getHeight(p.leftChild), getHeight(p.rightChild)) + 1; rsubtree.height = Math.max(getHeight(rsubtree.leftChild), getHeight(rsubtree.rightChild)) + 1; return rsubtree; // 新的根节点取代原失衡点的位置 }}
复制代码
总结
能看到这的，都是狠人。其实并不难，主要理解左旋和右旋的概念，我觉得就很清晰了。这篇也花了我一整天时间，基本我也是从 0 到 1 去接触的，如果感兴趣可以多研究研究。
评论