vlambda博客
学习文章列表

/*  * 将结点插入到AVL树中，并返回根节点 * * 参数说明:  * tree AVL树的根结点 * key 插入的结点的键值 * 返回值:  * 根节点 */private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) { if (tree == null) { // 新建节点 tree = new AVLTreeNode<T>(key, null, null); if (tree==null) { System.out.println("ERROR: create avltree node failed!"); return null; } } else { int cmp = key.compareTo(tree.key);
 if (cmp < 0) { // 应该将key插入到"tree的左子树"的情况 tree.left = insert(tree.left, key); // 插入节点后，若AVL树失去平衡，则进行相应的调节。 if (height(tree.left) - height(tree.right) == 2) { if (key.compareTo(tree.left.key) < 0) tree = leftLeftRotation(tree); else tree = leftRightRotation(tree); } } else if (cmp > 0) { // 应该将key插入到"tree的右子树"的情况 tree.right = insert(tree.right, key); // 插入节点后，若AVL树失去平衡，则进行相应的调节。 if (height(tree.right) - height(tree.left) == 2) { if (key.compareTo(tree.right.key) > 0) tree = rightRightRotation(tree); else tree = rightLeftRotation(tree); } } else { // cmp==0 System.out.println("添加失败: 不允许添加相同的节点！"); } }
 tree.height = max( height(tree.left), height(tree.right)) + 1;
 return tree;}
public void insert(T key) { mRoot = insert(mRoot, key);}

/*  * 删除结点(z)，返回根节点 * * 参数说明:  * tree AVL树的根结点 * z 待删除的结点 * 返回值:  * 根节点 */private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) { // 根为空 或者 没有要删除的节点，直接返回null。 if (tree==null || z==null) return null;
 int cmp = z.key.compareTo(tree.key); if (cmp < 0) { // 待删除的节点在"tree的左子树"中 tree.left = remove(tree.left, z); // 删除节点后，若AVL树失去平衡，则进行相应的调节。 if (height(tree.right) - height(tree.left) == 2) { AVLTreeNode<T> r = tree.right; if (height(r.left) > height(r.right)) tree = rightLeftRotation(tree); else tree = rightRightRotation(tree); } } else if (cmp > 0) { // 待删除的节点在"tree的右子树"中 tree.right = remove(tree.right, z); // 删除节点后，若AVL树失去平衡，则进行相应的调节。 if (height(tree.left) - height(tree.right) == 2) { AVLTreeNode<T> l = tree.left; if (height(l.right) > height(l.left)) tree = leftRightRotation(tree); else tree = leftLeftRotation(tree); } } else { // tree是对应要删除的节点。 // tree的左右孩子都非空 if ((tree.left!=null) && (tree.right!=null)) { if (height(tree.left) > height(tree.right)) { // 如果tree的左子树比右子树高； // 则(01)找出tree的左子树中的最大节点 // (02)将该最大节点的值赋值给tree。 // (03)删除该最大节点。 // 这类似于用"tree的左子树中最大节点"做"tree"的替身； // 采用这种方式的好处是: 删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。 AVLTreeNode<T> max = maximum(tree.left); tree.key = max.key; tree.left = remove(tree.left, max); } else { // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1) // 则(01)找出tree的右子树中的最小节点 // (02)将该最小节点的值赋值给tree。 // (03)删除该最小节点。 // 这类似于用"tree的右子树中最小节点"做"tree"的替身； // 采用这种方式的好处是: 删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。 AVLTreeNode<T> min = maximum(tree.right); tree.key = min.key; tree.right = remove(tree.right, min); } } else { AVLTreeNode<T> tmp = tree; tree = (tree.left!=null) ? tree.left : tree.right; tmp = null; } }
 return tree;}
public void remove(T key) { AVLTreeNode<T> z; 
 if ((z = search(mRoot, key)) != null) mRoot = remove(mRoot, z);}

前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 高度: 5最小值: 1最大值: 16

高度: 5中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16