📄 avltreeremove.java
字号:
import java.util.*;
public class AVLTree extends AbstractSet {
protected Entry root;
protected int size;
public boolean remove (Object elem) {
Entry e = getEntry (elem);
if (e == null)
return false;
deleteEntry (e);
return true;
} // method remove
// Postcondition: the Entry p has been removed from this
// BinSearchTree.
private void deleteEntry (Entry p) {
size--;
if (p.left != null && p.right != null) {
Entry s = successor (p);
p.element = s.element;
p = s;
// swapPositions (s, p);
} // p has two children
Entry replacement;
if (p.left != null)
replacement = p.left;
else
replacement = p.right;
// If p has at least one child, link replacement to p.parent.
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
} // p has at least one child
else if (p.parent == null)
root = null;
else {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
} // p has a parent but no children
fixAfterDeletion(p.element, p.parent);
} // method deleteEntry
// Postcondition: if there is an Entry whose element is elem, such an
// Entry has been returned. Otherwise, null has been
// returned.
private Entry getEntry (Object elem) {
int comp;
Entry e = root;
while (e != null) {
comp = ((Comparable)elem).compareTo (e.element);
if (comp == 0)
return e;
else if (comp < 0)
e = e.left;
else
e = e.right;
} // while
return null;
} // method getEntry
protected void fixAfterDeletion (Object elem, Entry ancestor) {
boolean heightHasDecreased = true;
while (ancestor!=null && heightHasDecreased) {
int comp = ((Comparable)elem).compareTo (ancestor.element);
if (comp >= 0) {
if (ancestor.balanceFactor == '=') {
ancestor.balanceFactor = 'L';
heightHasDecreased = false;
} // ancestor's balance factor is '='
else if (ancestor.balanceFactor == 'R') {
ancestor.balanceFactor = '=';
ancestor=ancestor.parent;
} // ancestor's balance factor is 'R'
else if (ancestor.balanceFactor == 'L') {
if (ancestor.left.balanceFactor == '=') {
ancestor.left.balanceFactor = 'R';
ancestor.balanceFactor = 'L';
rotateRight (ancestor);
heightHasDecreased = false;
} // ancestor.left's balance factor is '='
else if (ancestor.left.balanceFactor == 'L') {
Entry p=ancestor.parent;
ancestor.balanceFactor = '=';
ancestor.left.balanceFactor = '=';
rotateRight (ancestor);
ancestor=p;
} // ancestor.left's balance is 'L'
else if (ancestor.left.balanceFactor == 'R') {
Entry p=ancestor.parent;
if (ancestor.left.right.balanceFactor == 'L') {
ancestor.balanceFactor='R';
ancestor.left.balanceFactor = '=';
}
else if (ancestor.left.right.balanceFactor == 'R') {
ancestor.balanceFactor = '=';
ancestor.left.balanceFactor = 'L';
}
else {
ancestor.balanceFactor = '=';
ancestor.left.balanceFactor='=';
}
ancestor.left.right.balanceFactor='=';
rotateLeft(ancestor.left);
rotateRight(ancestor);
ancestor=p;
}
}
}//removed From the right subtree
else if (comp < 0) {
if (ancestor.balanceFactor=='=') {
ancestor.balanceFactor='R';
heightHasDecreased = false;
}
else if (ancestor.balanceFactor=='L') {
ancestor.balanceFactor='=';
ancestor=ancestor.parent;
}
else if (ancestor.balanceFactor=='R') {
if (ancestor.right.balanceFactor=='=') {
ancestor.balanceFactor='R';
ancestor.right.balanceFactor='L';
rotateLeft(ancestor);
heightHasDecreased =false;
}
else if (ancestor.right.balanceFactor=='R') {
Entry p=ancestor.parent;
ancestor.balanceFactor = '=';
ancestor.right.balanceFactor='=';
rotateLeft(ancestor);
ancestor=p;
}
else if (ancestor.right.balanceFactor=='L') {
Entry p=ancestor.parent;
if (ancestor.right.left.balanceFactor == 'R') {
ancestor.balanceFactor='L';
ancestor.right.balanceFactor = '=';
}
else if (ancestor.right.left.balanceFactor == 'L') {
ancestor.balanceFactor = '=';
ancestor.right.balanceFactor = 'R';
}
else {
ancestor.balanceFactor = '=';
ancestor.right.balanceFactor='=';
}
ancestor.right.left.balanceFactor='=';
rotateRight(ancestor.right);
rotateLeft(ancestor);
ancestor=p;
}
}
}//removed From the left subtree
}
} // method fixAfterDeletion
// Postcondition: The height of this AVL tree has been returned. The
// worstTime (n) is O (log n).
public int heightIter() {
int height = -1;
for (Entry temp = root; temp != null; height++)
if (temp.balanceFactor == 'L')
temp = temp.left;
else
temp = temp.right;
return height;
} // method heightIter
// Postcondition: the number of elements in this AVLTree has been
// returned.
public int size() {
return size;
} // method size()
protected static int h (Entry p) {
if (p == null)
return -1;
return 1 + Math.max (h (p.left), h (p.right));
} // method h
public int height() {
return h (root);
} // method height
public boolean isAVL () {
return checkAVL (root);
} // method isAVL
public static boolean checkAVL (Entry p) {
if (p == null)
return true;
return (Math.abs (h (p.left) - h (p.right)) <= 1 &&
checkAVL (p.left) && checkAVL (p.right));
} // method checkAVL
// Postcondition: an iterator positioned at the first entry in
// this AVLTree has been returned.
public Iterator iterator() {
return new TreeIterator();
} // method iterator
// Postcondition: true has been returned if there is an element e in this
// AVLTree such that o.equals (e). Otherwise, false
// has been returned.
public boolean contains (Object o) {
Entry e = root;
int comp;
while (e != null) {
comp = ((Comparable)o).compareTo (e.element);
if (comp == 0)
return true;
else if (comp < 0)
e = e.left;
else
e = e.right;
} // while
return false;
} // contains
// Postcondition: if this AVLTree contains an element equal to o,
// then false has been returned. Otherwise, o has been
// inserted where it belongs in this AVLTree and
// true has been returned.
public boolean add (Object o) {
if (root == null) {
root = new Entry (o, null);
size++;
return true;
} // empty tree
else {
Entry temp = root,
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -