AVL树的Java实现
程序员文章站
2022-06-10 08:49:22
AVL树:平衡的二叉搜索树,其子树也是AVL树。 以下是我实现AVL树的源码(使用了泛型): ......
avl树:平衡的二叉搜索树,其子树也是avl树。
以下是我实现avl树的源码(使用了泛型):
import java.util.comparator; public class avltree<t extends comparable<t>> { /* avl树: 左右子树高度绝对值最多差1的二叉搜索树 子树也是avl树 */ private node<t> root; class node<t extends comparable<t>>{ t key; int height; node<t> left; node<t> right; public node(t key, int height, node<t> left, node<t> right) { this.key = key; this.height = height; this.left = left; this.right = right; } public node(t key){ this.key = key; this.height = 0; } } public int getheight(node<t> node){ return node == null ? 0 : node.height; } public node<t> ll(node<t> node){ //左子树插入节点在左导致不平衡,需要旋转,以下不再赘述 node<t> leftnode = node.left; node.left = leftnode.right; leftnode.right = node; node.height = math.max(node.left.height,node.right.height) + 1; leftnode.height = math.max(leftnode.left.height, leftnode.right.height) + 1; return leftnode; } public node<t> rr(node<t> node) { node<t> rightnode; rightnode = node.right; node.right = rightnode.left; rightnode.left = node; node.height = math.max( node.left.height, node.right.height) + 1; rightnode.height = math.max( rightnode.left.height, rightnode.right.height) + 1; return rightnode; } public node<t> lr(node<t> node){ //lr先对左子树rr再对本树ll node.left = rr(node.left); return ll(node); } public node<t> rl(node<t> node){ node.right = ll(node.right); return rr(node); } public node<t> insert(node<t> root,t key){ /* 插入:先判断插入点,再判断是否需要翻转 */ if(root == null){ return new node<t>(key); } else{ if(key.compareto(root.key)<0) //t是实现了comparable接口的,所以这里可以比较,但不能用大小于号 { root.left = insert(root.left,key); if(root.left.height - root.right.height == 2){ if (key.compareto(root.left.key) < 0) root = ll(root); else root = lr(root); } }else if(key.compareto(root.key)>0){ root.right = insert(root.right,key); if(root.left.height - root.right.height == -2){ if (key.compareto(root.right.key) < 0) root = rl(root); else root = rr(root); } }else{ return root;//相同的节点不添加 } } return root; } public node<t> delete(node<t> root,t key){ /* 删除:找到删除点,判断是否需要翻转 */ if(root == null || key == null){ return root; } else{ if(key.compareto(root.key)<0) //t是实现了comparable接口的,所以这里可以比较,但不能用大小于号 { root.left = delete(root.left,key); if(root.left.height - root.right.height == -2){ node<t> rightnode = root.right; if (rightnode.right.height>root.left.height) root = rl(root); else root = rr(root); } }else if(key.compareto(root.key)>0){ root.right = delete(root.right,key); if(root.left.height - root.right.height == 2){ node<t> leftnode = root.left; if (leftnode.left.height>leftnode.right.height) root = ll(root); else root = lr(root); } }else { //找到了要删除的节点 if (root.left == null) root = root.right; else if (root.right == null) root = root.left; else { if (root.left.height < root.right.height) { node<t> tempnode = root.right; while (tempnode.left != null) { tempnode = tempnode.left; }//为保证二叉树的平衡性、搜索性 //这里选择了高度较高的子树,选取中序遍历与root相邻的节点作为root,这样不会破坏搜索性 root.key = tempnode.key; delete(tempnode, key); } else { node<t> tempnode = root.left; while (tempnode.right != null) { tempnode = tempnode.right; }//为保证二叉树的平衡性、搜索性 //这里选择了高度较高的子树,选取中序遍历与root相邻的节点作为root root.key = tempnode.key; delete(tempnode, key); } } } } return root; } }
上一篇: Meta闪崩,并不稀奇
下一篇: 闲鱼app如何举报商品 闲鱼举报商品教程