企业网站 更新 seo,淄博seo网站推广,wordpress首页按钮,青岛商网站建设各种各样的大树 平衡二叉树 (AVL树)
普通二叉树存在的问题 左子树全部为空#xff0c;从形式上看#xff0c;更像一个单链表 插入速度没有影响 查询速度明显降低#xff08;因为需要依次比较#xff09;#xff0c;不能发挥BST的优势#xff0c;因为每次还需要比较左子… 各种各样的大树 平衡二叉树 (AVL树)
普通二叉树存在的问题 左子树全部为空从形式上看更像一个单链表 插入速度没有影响 查询速度明显降低因为需要依次比较不能发挥BST的优势因为每次还需要比较左子树其查询速度比单链表还慢 解决方案-平衡二叉树(AVL)
基本介绍
平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树可以保证查询效率较高。具有以下特点它是一棵空树或它的左右两个子树的高度差的绝对值不超过1 并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、 AVL、替罪羊树、Treap、伸展树等
应用案例
判断树的高度
// 返回左子树的高度
public int leftHeight() {if (left null) {return 0;}return left.height();
}// 返回右子树的高度
public int rightHeight() {if (right null) {return 0;}return right.height();
}// 返回当前结点的高度以该结点为根结点的树的高度
public int height() {return Math.max(left null ? 0 : left.height(), right null ? 0 : right.height()) 1;
}单旋转左旋转
左旋转步骤
前提条件 r i g h t H e i g h t ( ) − l e f t H e i g h t ( ) 1 rightHeight() - leftHeight() 1 rightHeight()−leftHeight()1
创建一个新的节点newNode(以root 这个值创建)创建一个新的节点值等于当前根节点的值把新节点的左子树设置了当前节点的左子树 // newNode.left left把新节点的右子树设置为当前节点的右子树的左子树 // newNode.right right.left;把当前节点的值换为右子节点的值 // valueright.value;把当前节点的右子树设置成当前结点的右子树的右子树 // rightright.right;把当前节点的左子树设置为新节点 // leftnewLeft;
// 左旋转
private void leftRotate() {// 1. 创建一个新的节点newNode(以root 这个值创建)// 创建一个新的节点值等于当前根节点的值把新节点的左子树设置了当前节点的左子树Node newNode new Node(value);newNode.left left;// 2.把新节点的右子树设置为当前节点的右子树的左子树newNode.right right.left;// 3.把当前节点的值换为右子节点的值value right.value;// 4.把当前节点的右子树设置成当前结点的右子树的右子树right right.right;// 5.把当前节点的左子树设置为新节点left newNode;
}单旋转右旋转
步骤
创建一个新的节点newNode(以root 这个值创建创健一个新的节点值等于当前根节点的值把新节点的右子树设置了当前节点的右子树 // newNode.right right把新节点的左子树设置为当前节点的左子树的右子树 // newNode.left left.right;把当前节点的值换为左子节点的值 // valueleft.value;把当前节点的左子树设置成左子树的左子树 // leftleft.left;把当前节点的右子树设置为新节点 // rightnewLeft;
// 右旋转
public void rightRotate() {// 1.创建一个新的节点newNode(以root 这个值创建// 创健一个新的节点值等于当前根节点的值Node newNode new Node(value);// 2.把新节点的右子树设置了当前节点的右子树newNode.right right;// 3.把新节点的左子树设置为当前节点的左子树的右子树newNode.left left.right;// 4.把当前节点的值换为左子节点的值value left.value;// 5.把当前节点的左子树设置成左子树的左子树left left.left;// 6.把当前节点的右子树设置为新节点right newNode;
}双旋转 在单旋转中 (即一次旋转) 就可以将非平衡二叉树转成平衡二叉树但是在某些情况下单旋转不能完成平衡二叉树的转换 情况1️⃣ 实现步骤 当右旋转的条件时 如果它的左子树的右子树高度大于它的左子树的右子树的高度先对当前这个结点的左节点进行左旋转再对当前结点进行右旋转 当左旋转时 如果它的右子树的左子树高度大于它的右子树的右子树的高度先对当前这个结点的右结点进行右旋转再对当前结点进行左旋转
/*** 添加在Node类的添加结点的方法里边* 每添加一个结点就判断一次
*/
// 单旋转
// 当添加完一个结点后如果(右子树的高度-左子树的高度) 1左旋转
if (rightHeight() - leftHeight() 1) {// 如果它的右子树的左子树高度大于它的右子树的右子树的高度if (right ! null right.rightHeight() right.leftHeight()) {// 先对当前这个结点的右结点进行右旋转rightRotate();}leftRotate(); // 左旋转return; // 一定要返回否则会出现其他问题提高VM处理速度
}
// 当添加完一个结点后如果(左子树的高度-右子树的高度) 1右旋转
if (leftHeight() - rightHeight() 1) {// 如果它的左子树的右子树高度大于它的左子树的右子树的高度if (left ! null left.rightHeight() left.leftHeight()) {// 先对当前这个结点的左节点进行左旋转left.leftRotate();}rightRotate(); // 右旋转
}总代码
package com.xiaolu.avl;/*** author 林小鹿* version 1.0*/
public class AvlTreeDemo {public static void main(String[] args) {
// int[] arr {4, 3, 6, 5, 7, 8};
// int[] arr {10, 12, 8, 9, 7, 6};int[] arr {10, 11, 7, 6, 8, 9};AVLTree avlTree new AVLTree();// 添加结点for (int i 0; i arr.length; i) {avlTree.add(new Node(arr[i]));}// 中序遍历avlTree.infixOrder();System.out.println(平衡处理 (左旋转)~~~);System.out.println(树的高度: avlTree.getRoot().height()); // 4System.out.println(树的左子树高度: avlTree.getRoot().leftHeight()); // 1System.out.println(树的右子树高度: avlTree.getRoot().rightHeight()); // 3System.out.println(当前根结点 avlTree.getRoot());}
}// 创建AVLTree
class AVLTree {private Node root;public Node getRoot() {return root;}// 查找要删除的结点public Node search(int value) {if (root null) {return null;} else {return root.search(value);}}// 查找要删除的父结点public Node searchParent(int value) {if (root null) {return null;} else {return root.searchParent(value);}}/*** 删除node 为根结点的二叉排序树的最小结点的值的同时返回以node 为根结点的二叉排序树的最小结点** param node 传入的结点 (当做二叉排序树的根结点)* return 返回以node 为根结点的二叉排序树的最小结点的值*/public int delRightTreeMin(Node node) {Node target node;// 循环的查找左结点就会找到最小值while (target.left ! null) {target target.left;}// 这是target就指向了最小结点// 删除最小结点delNode(target.value);return target.value;}// 删除结点public void delNode(int value) {if (root null) {return;} else {// 找到需要删除的结点 targetNodeNode targetNode search(value);// 如果没有找到要删除的结点if (targetNode null) {return;}// 如果这颗二叉排序树只有一个结点 (即本身就是父节点)if (root.left null root.right null) {root null;return;}// 查询父节点Node parent searchParent(value);// 如果待删除的结点是叶子结点if (targetNode.left null targetNode.right null) {// 删除叶子结点// 判断 targetNode 是父节点的左子结点还是右子节点if (parent.left ! null parent.left.value value) {parent.left null;} else if (parent.right ! null parent.right.value value) {parent.right null;}} else if (targetNode.left ! null targetNode.right ! null) {// 删除有两颗子树的结点int minVal delRightTreeMin(targetNode.right);targetNode.value minVal;} else {// 删除只有一颗子树的结点// 如果要删除的结点有左子结点if (targetNode.left ! null) {if (parent ! null) {// 如果targetNode 是parent 的左子结点if (parent.left.value value) {parent.left targetNode.left;} else {// 如果targetNode 是parent 的右子结点parent.right targetNode.left;}} else {root targetNode.left;}} else {if (parent ! null) {// 如果要删除的结点有右子结点if (parent.left.value value) {// 如果targetNode 是parent 的左子结点parent.left targetNode.right;} else {// 如果targetNode 是parent 的右子结点parent.right targetNode.right;}} else {root targetNode.right;}}}}}// 添加结点public void add(Node node) {if (root null) {// 如果root为空则直接让root指向noderoot node;} else {root.add(node);}}// 中序遍历public void infixOrder() {if (root null) {System.out.println(二叉树为空无法遍历);} else {root.infixOrder();}}
}// 创建Node结点
class Node {int value;Node left;Node right;public Node(int value) {this.value value;}// 返回左子树的高度public int leftHeight() {if (left null) {return 0;}return left.height();}// 返回右子树的高度public int rightHeight() {if (right null) {return 0;}return right.height();}// 返回当前结点的高度以该结点为根结点的树的高度public int height() {return Math.max(left null ? 0 : left.height(), right null ? 0 : right.height()) 1;}// 左旋转private void leftRotate() {// 1. 创建一个新的节点newNode(以root 这个值创建)// 创建一个新的节点值等于当前根节点的值把新节点的左子树设置了当前节点的左子树Node newNode new Node(value);newNode.left left;// 2.把新节点的右子树设置为当前节点的右子树的左子树newNode.right right.left;// 3.把当前节点的值换为右子节点的值value right.value;// 4.把当前节点的右子树设置成当前结点的右子树的右子树right right.right;// 5.把当前节点的左子树设置为新节点left newNode;}// 右旋转public void rightRotate() {// 1.创建一个新的节点newNode(以root 这个值创建// 创健一个新的节点值等于当前根节点的值Node newNode new Node(value);// 2.把新节点的右子树设置了当前节点的右子树newNode.right right;// 3.把新节点的左子树设置为当前节点的左子树的右子树newNode.left left.right;// 4.把当前节点的值换为左子节点的值value left.value;// 5.把当前节点的左子树设置成左子树的左子树left left.left;// 6.把当前节点的右子树设置为新节点right newNode;}/*** 查找要删除的结点** param value 待删除的结点的值* return 如果找到则返回该结点否则返回空*/public Node search(int value) {if (value this.value) {return this;} else if (value this.value) {// 如果查找的值小于当前结点就向左子树递归查找if (this.left null) {// 如果左子树为空return null;}return this.left.search(value);} else {// 如果查找的值不小于当前结点向右子树递归查找if (this.right null) {// 如果右子树为空return null;}return this.right.search(value);}}/*** 查找要删除结点的父结点** param value 要找到的结点的值* return 返回的是要删除的结点的父结点如果没有就返回null*/public Node searchParent(int value) {// 如果当前结点就是要删除的结点的父节点就返回if ((this.left ! null this.left.value value)|| (this.right ! null this.right.value value)) {return this;} else {// 如果查找的值小于或大于当前结点的值并且当前结点的左子节点不为空if (value this.value this.left ! null) {return this.left.searchParent(value); // 向左子树递归查找} else if (value this.value this.right ! null) {return this.right.searchParent(value); // 向右子树递归查找} else {return null; // 没有找到父节点}}}// 按二叉排序树的形式递归添加结点public void add(Node node) {if (node null) {return;}// 判断传入的结点的值与当前子树的根结点的值关系if (node.value this.value) {if (this.left null) {this.left node;} else {// 递归得向左子树添加 nodethis.left.add(node);}} else { // 添加的结点的值大于当前结点的值if (this.right null) {this.right node;} else {// 递归得向右子树添加 nodethis.right.add(node);}}// 单旋转// 当添加完一个结点后如果(右子树的高度-左子树的高度) 1左旋转if (rightHeight() - leftHeight() 1) {// 如果它的右子树的左子树高度大于它的右子树的右子树的高度if (right ! null right.leftHeight() right.rightHeight()) {// 先对当前这个结点的右结点进行右旋转rightRotate();}leftRotate(); // 左旋转return; // 一定要返回否则会出现其他问题提高VM处理速度}// 当添加完一个结点后如果(左子树的高度-右子树的高度) 1右旋转if (leftHeight() - rightHeight() 1) {// 如果它的左子树的右子树高度大于它的左子树的右子树的高度if (left ! null left.rightHeight() left.leftHeight()) {// 先对当前这个结点的左节点进行左旋转left.leftRotate();}rightRotate(); // 右旋转}}// 中序遍历public void infixOrder() {if (this.left ! null) {this.left.infixOrder();}System.out.println(this);if (this.right ! null) {this.right.infixOrder();}}Overridepublic String toString() {return Node[ value value ];}
} 多路查找树 二叉树存在的问题 二叉树需要加载到内存的如果二叉树的节点少没有什么问题但是如果二叉树的节点很多比如1亿)就存在如下问题 问题1在构建二叉树时需要多次进行 I / O I/O I/O 操作海量数据存在数据库或文件中)节点海量构建二叉树时速度有影响 问题2节点海量也会造成二叉树的高度很大会降低操作速度
多叉树 在二叉树中每个节点有数据项最多有两个子节点如果允许每个节点可以有更多的数据项和更多的子节点就是多叉树multiway tree 多叉树通过重新组织节点减少树的高度能对二叉树进行优化
2-3树 2-3树是最简单的B-树结构其他像2-3-4树同理 特点
2-3树的所有叶子节点都在同一层.只要是B树都满足这个条件有两个子节点的节点叫二节点二节点要么没有子节点要么有两个子节点有三个子节点的节点叫三节点三节点要么没有子节点要么有三个子节点.2-3树是由二节点和三节点构成的树。
插入规则
12-3树的所有叶子节点都在同一层.只要是B树都满足这个条件) 2有两个子节点的节点叫二节点二节点要么没有子节点要么有两个子节点
3有三个子节点的节点叫三节点三节点要么没有子节点要么有三个子节点 4)当按照规则插入一个数到某个节点时不能满足上面三个要求就需要拆先向上拆如果上层满则拆本层拆后仍然需要满足上面3个条件。 5)对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则 B树 B-treeB即Balanced 基本介绍
B树的阶节点的最多子节点个数。比如2-3树的阶是32-3-4树的阶是4B树的搜索从根结点开始对结点内的关键字有序序列进行二分查找如果命中侧结束否测进入查询关键字所属范围的儿子结点重复直到所对应的儿子指针为空或已经是叶子结点关键字集合分布在整颗树中即叶子节点和非叶子节点都存放数据搜索有可能在非叶子结点结束其搜索性能等价于在关键字全集内做一次二分查找 B树 B树是B树的变体也是一种多路搜索树 基本介绍
B树的搜索与B树也基本相同区别是B树只有达到叶子结点才命中B树可以在非叶子结点命中其性能也等价于在关键字全集做一次二分查找所有关键字都出现在叶子结点的链表中即数据只能在叶子节点【也叫稠密索引】)且链表中的关键字数据恰好是有序的。不可能在非叶子结点命中非叶子结点相当于是叶子结点的索引稀疏索引叶子结点相当于是存储关键字数据的数据层更适合文件索引系统B树和B时各有自己的应用场景不能说B完全比B树好反之亦然 B*树 B*树是B树的变体在B树的非根和非叶子结点再增加指向兄弟的指正 基本说明
B*树定义了非叶子结点关键字个数至少为(2/3)*M即块的最低使用率为2/3而B树的块的最低使用率为B树的1/2。从第1个特点我们可以看出B*树分配新结点的概率比B树要低空间使用率更高
