ืคืจืืื
ืืืืจ ืื ืขืืกืง ืืขืฆื ืืืคืืฉ ืืื ืืจืืื. ืืืืจืื ื ืืชืืชื ืืืืจ ืขื
ืขืฅ ืืื ืืื ื ื ืชืื ืื ืืืืจืื ืืฆืืชืื ืืืืืืจืื ืืงืฆืืืช. ืื ื ืืืืืื ืืืืจ ืฉืขืฅ ืืื ืืงืจื ืืืืื ืฉื ืืจืฃ. ืื ื ืขืฅ ืืืืืื:
ืื ืื ืขืฅ ืืืคืืฉ ืืื ืืจื! ืืื ืชืืช ืืชื!
ืืจืืื ืืืืืื
ืฉืืจืฉ
ืฉืืจืฉ ืขืฅ ืืื ืืฆืืืช ืืขืืืื. ืืืืืื, ืืื ืฆืืืช A. ืืขืฅ, ืจืง ื ืชืื ืืื ืืืื ืืืืืื ืืืฉืืจืฉ ืืื ืฆืืืช ืืืจ! ืืืขืฉื, ืื ืฆืืืช ืืืื ืืืืืฉื ืืฉืืจืฉ ืชืช-ืืขืฅ ืืืชืืื ืืฆืืืช ืื.
ืืืจืื/ืฆืืฆืืื
ืืื ืืฆืืชืื ืืืื ืืฉืืจืฉ ืืฉ ืงืฆื ืืื ืืืืืง ืืืืืื ืืฆืืืช ืืืจ. ืืฆืืืช ืฉืืขื ืืฆืืืช ืื ืืืื ื ืงืจื ืืึนืจึถื ืืฆืืืช ืืื. ืฆืืืช ืฉื ืืฆื ืืชืืช ืืื ืื ืืืื ืืืืืืจ ืืืื ื ืงืจื ืฆืึฑืฆื ืืฆืืืช ืืื. ืืืื ื ืืงื ืืืืื. ืงื ืืช ืฆืืืช B, ืืื ืืื ืฉืื ืืืื ืฆืืืช A, ืืืืืืื ืฉืื ืืืื ืฆืืชืื D, E ื-F.
ืืืืืื
ืฆืืืช ืฉืืื ืื ืืืืื ื ืงืจื ืขืื ืฉื ืืขืฅ. ืืืืืื, ืืฆืืชืื D, E, F, G, I, J, K ืืืื ืขืืื.
ืืื ืืืื ืื ืืืกืืกื. ืืืฉืืื ืืืจืื ืืืืื ื ืืืืฉื. ืื, ืขืฅ ืืื ืืจื ืืื ืขืฅ ืฉืื ืืื ืฆืืืช ืืืื ืื ืืืชืจ ืืฉื ื ืืืืื. ืืคื ืฉื ืืืฉืชื, ืืขืฅ ืืืืืืื ืื ืืืื ืืื ืืจื, ืื ืืฆืืชืื B ื-H ืืฉ ืืืชืจ ืืฉื ื ืืืืื. ืื ื ืืืืื ืืขืฅ ืืื ืืจื:
ืืฆืืชืื ืฉื ืืขืฅ ืืืืืื ืืืืื ืื ืืืืข. ืขืฅ ืืืคืืฉ ืืื ืืจื ืืื ืขืฅ ืืื ืืจื ืืขื ืืืืคืืื ืื ืืืืื:
- ืชืชื ืขืฅ ืฉืืืื ืืืืื ืื ืขืฆื ืืืคืืฉ ืืื ืืจืืื.
- ืืื ืืฆืืชืื ืฉื ืชืช-ืืขืฅ ืืฉืืืื ืฉื ืฆืืืช X ืฉืจืืจืืชื ืืฉ ืขืจืื ืืคืชื ื ืชืื ืื ืคืืืชืื ืืขืจื ืืคืชื ืื ืชืื ืื ืฉื ืฆืืืช X ืขืฆืื.
- ืืื ืืฆืืชืื ืฉื ืชืช-ืืขืฅ ืืืื ื ืฉื ืฆืืืช ืฉืจืืจืืชื X ืืฉ ืขืจืื ืืคืชื ื ืชืื ืื ืืืืืื ืื ืฉืืืื ืืขืจื ืฉื ืืคืชื ืื ืชืื ืื ืฉื ืฆืืืช X ืขืฆืื.
ืืคืชื - ืืืคืืื ืืืฉืื ืฉื ืืฆืืืช (ืืืืืื, ืืกืคืจ). ืืืคืชื ื ืืืฅ ืืื ืืืืืช ืืกืืื ืืืฆืื ืืช ืืืื ื ืืขืฅ ืฉืืืื ืืงืฉ ืื ืืชืืื. ืืืืื ืืขืฅ ืืืคืืฉ ืืื ืืจื:
ื ืืฃ ืขืฅ
ืืื ืฉืืืฉืื, ืืืืื ืืื ืคืืกืืช ืงืื (ืืืื ืื ืฉืืืืช) ืืื ืืฉืคืจ ืืช ืืืื ื ืฉืื. ืืงืื ืืืื ืืืื ืืกืืฃ ืืืืืจ.
ืืขืฅ ืืืจืื ืืฆืืชืื. ืืื ื ืืฆืืืช:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...ะพััะฐะปัะฝัะต ะผะตัะพะดั ัะทะปะฐ
}
ืืื ืฆืืืช ืืฉ ืฉื ื ืืืืื (ืืืชืื ืืืืื ืฉืืืืืื leftChild ื/ืื rightChild ืืืื null). ืืื ืืื ืชื ืฉืืืงืจื ืืื ื ืชืื ื ืืืกืคืจ ืื ืื ืชืื ืื ืืืืืืกื ืื ืืฆืืืช; ืืคืชื - ืืคืชื ืฆืืืช.
ืืื ื ืืช ืืงืฉืจ, ืขืืฉืื ืืืื ื ืืืจ ืขื ืืืขืืืช ืืืืืงืืช ืืืื ืขืฆืื. ืืืื, ืืฉืืขืืช ืืืืื "ืขืฅ" ืืื ืืืืฉื ืฉื ืขืฅ ืืืคืืฉ ืืื ืืจื. ืืื ื ืขืฅ ืืื ืืจื:
public class BinaryTree<T> {
private Node<T> root;
//ะผะตัะพะดั ะดะตัะตะฒะฐ
}
ืืชืืจ ืฉืื ืืืืงื, ืื ืื ื ืฆืจืืืื ืจืง ืืช ืืฉืืจืฉ ืฉื ืืขืฅ, ืื ืืืฉืืจืฉ, ืืืืฆืขืืช ืืืชืืืืช getLeftChild() ื-getRightChild(), ืืชื ืืืื ืืืืืข ืืื ืฆืืืช ืฉื ืืขืฅ.
ืืืืืจืืชืืื ืฉื ืขืฆืื
ืืืคืืฉ
ื ื ืื ืฉืืฉ ืื ืขืฅ ืื ืื. ืืื ืืืฆืื ืืืื ื ืขื ืืคืชื ืืคืชื? ืืชื ืฆืจืื ืืขืืืจ ืืจืฆืฃ ืืืฉืืจืฉ ืืืืจื ืืขืฅ ืืืืฉืืืช ืืช ืืขืจื ืฉื ืืืคืชื ืขื ืืืคืชื ืฉื ืืฆืืืช ืืื: ืื ืืืคืชื ืงืื ืืืืคืชื ืฉื ืืฆืืืช ืืื, ืขืืืจ ืื ืืฆืืฆื ืืฉืืืื ืฉื ืืฆืืืช, ืื ืืืชืจ - ืืืืื, ืื ืืืคืชืืืช ืฉืืืื - ื ืืฆื ืืฆืืืช ืืจืฆืื! ืงืื ืจืืืื ืื:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
ืื ืืืจื ืืืคื ืืืื, ืื ืืืืืจืฆืื ืืืืขื ืืงืฆื ืืขืฅ (ืืจืื ืจืขืืื ืืช, ืืชื ื ืืฆื ืืืงืื ืื ืงืืื ืืขืฅ - ืืื ืฉื ืขืื).
ืฉืงืื ืืช ืืืขืืืืช ืฉื ืืืืืจืืชื ืืืืคืืฉ ืขื ืขืฅ ืืืืื (ืขืฅ ืฉืื ืฆืืชืื ืืคืืืจืื ืคืืืช ืื ืืืชืจ ืืืืคื ืฉืืื). ืื ืืขืืืืช ืืืืคืืฉ ืชืืื O(log(n)), ืืืืืืจืืชื ืืกืืก 2. ืจืื: ืื ืืฉ n ืืืื ืืื ืืขืฅ ืืืืื, ืื ืื ืืืืจ ืฉืืืื ืจืืืช log(n) ืืกืืก 2 ืฉื ืืขืฅ. ืืืืืคืืฉ, ืืืจื ืฉืื ืืื ืืืืืืจ, ืืชื ืืืจื ืจืื ืืืช.
ืืื ืก
ืื ืืื ืช ืืช ืืืืช ืืืืคืืฉ, ืื ืื ืืืื ืื ืงืฉื ืืืืื ืืช ืืืื ืกื. ืืชื ืจืง ืฆืจืื ืืจืืช ืืขืื ืฉื ืืขืฅ (ืืคื ืืืื ืืืจืืื ืืืชืืืจืื ืืืืคืืฉ) ืืืืคืื ืืฆืืฆืื ืฉืื - ืฉืืืื ืื ืืืื ื, ืชืืื ืืืคืชื. ืืืฉืื:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
ืืืงืจื ืื, ืื ืืกืฃ ืืฆืืืช ืื ืืืื, ืืฉ ืฆืืจื ืืืืกื ืืืืข ืขื ืืื ืฉื ืืฆืืืช ืื ืืืื. ืืืฉืจ ืื ืืืื ืืืคื ื-null, ืืฉืชื ื ืืื ืืืื ืืช ืืืืืืื ืฉืื ื ืฆืจืืืื.
ืืจืืจ ืฉืืขืืืืช ืืืืืจื ืชืืื ืืื ืืื ืฉื ืืืืคืืฉ - O(log(n)).
ืืืืงื
ืืืืงื ืืื ืืคืขืืื ืืืืจืืืช ืืืืชืจ ืฉืชืฆืืจื ืืืืขืฉืืช ืขื ืขืฅ. ืืจืืจ ืฉืชืืืื ืืืื ืฆืืจื ืืืฆืื ืืช ืืืืื ื ืฉืื ื ืืืืืื ืืืกืืจ. ืืื ืื ืื? ืื ืคืฉืื ื ืืืืจ ืืช ืืืชืืืืกืืช ืฉืื ื- null, ืื ื ืืื ืืืืข ืขื ืชืช-ืืขืฅ ืฉืืฉืืจืฉ ืฉืื ืืื ืืฆืืืช ืืื. ืฉืืืืช ืืกืจืช ืขืฆืื ืืืืืงืืช ืืฉืืืฉื ืืงืจืื.
ืืงืจื ืจืืฉืื. ืืฆืืืช ืฉืืฉ ืืืกืืจ ืืื ืืืืื.
ืื ืืฆืืืช ืฉืืืืืง ืืื ืืืืื, ืื ืืืืจ ืฉืืื ืขืื. ืืื, ืืชื ืืืื ืคืฉืื ืืืืืืจ ืืช ืืฉืืืช leftChild ืื rightChild ืฉื ืืื ืฉืื ื-null.
ืืงืจื ืฉื ื. ืืฆืืืช ืฉืืฉ ืืืกืืจ ืืฉ ืืื ืืื
ืื ืืืงืจื ืืื ืื ืงืฉื ืืืืืื. ื ืืืืจ ืืืืืื ืฉืื ื. ื ื ืื ืฉืขืืื ื ืืืืืง ืืืื ื ืขื ืืคืชื 14. ืืกืืื ืฉืืืืืื ืฉืืื ืืืื ืืืื ื ืฉื ืฆืืืช ืขื ืืคืชื 10, ืื ืืื ืืื ืืืฆืืฆืืื ืฉืื (ืืืงืจื ืื, ืืืื ื) ืืืื ืืคืชื ืืืื ื-10, ืื ืืชื ืืืื ืืงืืืช "ืืืชืื" ืืืชื ืืืขืฅ, ืืืืืจ ืืช ืืืืจื ืืฉืืจืืช ืืืื ืฉื ืืฆืืืช ืฉื ืืืง, ืืืืืจ. ืืืืจ ืืช ืืฆืืืช ืขื ืืงืฉ 10 ืืฆืืืช 13. ืืืฆื ืืื ืืืื ืื ื ืฆืืจื ืืืืืง ืฆืืืช ืฉืืื ืืืื ืืฉืืืื ืฉื ืืืืจื ืฉืื. ืชืืฉืื ืขื ืื ืืขืฆืื - ืื ืืืืื ืืืืืงืช.
ืืงืจื ืฉืืืฉื. ื-Node ืืฉ ืฉื ื ืืืืื
ืืืงืจื ืืื ืงืฉื. ืืืื ื ืกืชืื ืขื ืืืืื ืืืฉื.
ืืคืฉ ืืืจืฉ
ื ื ืื ืฉืฆืจืื ืืืกืืจ ืืช ืืฆืืืช ืขื ืืคืชื 25. ืืช ืื ื ืื ืืก ืืืงืืื? ืืื ืืืกืืืื (ืฆืืฆืืื ืื ืฆืืฆืืื ืฉื ืฆืืฆืืื) ืืืื ืืืืืช ืืึนืจึตืฉื(ืื ืฉืืชืคืืก ืืช ืืงืืื ืฉื ืืฆืืืช ืฉืืืกืจ).
ืืื ืืืืขืื ืื ืฆืจืื ืืืืืช ืืืืจืฉ? ืืืืคื ืืื ืืืืืืืื, ืืื ืืฆืืืช ืืขืฅ ืฉืืืคืชื ืฉืื ืืื ืืื ืืืืืื ืืืฆืืืช ืฉืืืกืจ. ืืืืืืจืืชื ืืื ืืืืงืื. ืืชื ืฆืจืื ืืืืช ืืืื ืืืื ื ืฉืื (ืชืืื ืืืืื, ืื ืืืจ ื ืืืจ ืฉืืืคืชื ืฉื ืืืืจืฉ ืืืื ืืืืคืชื ืฉื ืืฆืืืช ืฉื ืืืง), ืืื ืืขืืืจ ืืช ืฉืจืฉืจืช ืืืืืื ืืฉืืืื ืฉื ืืืืื ืืื ืึถืึถื. ืืืืืื, ืขืืื ื ืืืืช ืืฆืืืช ืขื ืืงืฉ 35, ืืืืืจ ืืื ืืจืืช ืืฉืจืฉืจืช ืฉื ืืืืื ืืฉืืืืืื ืืขืื - ืืืงืจื ืื, ืืฉืจืฉืจืช ืืื ืืืจืืืช ืจืง ืืืฆืืืช ืขื ืืคืชื 30. ืืืืืจืื, ืื ื ืืืคืฉืื ืืฆืืืช ืืงืื ืืืืชืจ ืืงืืืฆืช ืืฆืืชืื ืืืืื ืืืฆืืืช ืืจืฆืื.
ืงืื ืฉืืืช ืืืคืืฉ ืืืจืฉ:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//ัะพะดะธัะตะปั ะฟัะตะตะผะฝะธะบะฐ
Node<T> successor = deleteNode;//ะฟัะตะตะผะฝะธะบ
Node<T> current = successor.getRightChild();//ะฟัะพััะพ "ะฟัะพะฑะตะณะฐััะธะน" ัะทะตะป
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//ะฝะฐ ะฒัั
ะพะดะต ะธะท ัะธะบะปะฐ ะธะผะตะตะผ ะฟัะตะตะผะฝะธะบะฐ ะธ ัะพะดะธัะตะปั ะฟัะตะตะผะฝะธะบะฐ
if (successor != deleteNode.getRightChild()) {//ะตัะปะธ ะฟัะตะตะผะฝะธะบ ะฝะต ัะพะฒะฟะฐะดะฐะตั ั ะฟัะฐะฒัะผ ะฟะพัะพะผะบะพะผ ัะดะฐะปัะตะผะพะณะพ ัะทะปะฐ
parentSuccessor.setLeftChild(successor.getRightChild());//ัะพ ะตะณะพ ัะพะดะธัะตะปั ะทะฐะฑะธัะฐะตั ัะตะฑะต ะฟะพัะพะผะบะฐ ะฟัะตะตะผะฝะธะบะฐ, ััะพะฑั ะฝะต ะฟะพัะตัััั ะตะณะพ
successor.setRightChild(deleteNode.getRightChild());//ัะฒัะทัะฒะฐะตะผ ะฟัะตะตะผะฝะธะบะฐ ั ะฟัะฐะฒัะผ ะฟะพัะพะผะบะพะผ ัะดะฐะปัะตะผะพะณะพ ัะทะปะฐ
}
return successor;
}
ืืงืื ืืืื ืฉื ืฉืืืช ืืืืืงื:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//ะ ะทะฐะฒะธัะธะผะพััะธ ะพั ัะพะณะพ, ัะฒะปัะตััั ะปะธ ัะดะฐะปัะตะผัะน ัะทะตะป ะปะตะฒัะผ ะธะปะธ ะฟัะฐะฒัะผ ะฟะพัะพะผะบะพะผ ัะฒะพะตะณะพ ัะพะดะธัะตะปั, ะฑัะปะตะฒัะบะฐั ะฟะตัะตะผะตะฝะฝะฐั isLeftChild ะฑัะดะตั ะฟัะธะฝะธะผะฐัั ะทะฝะฐัะตะฝะธะต true ะธะปะธ false ัะพะพัะฒะตัััะฒะตะฝะฝะพ.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//ะฟะตัะฒัะน ัะปััะฐะน
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//ะฒัะพัะพะน ัะปััะฐะน
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//ััะตัะธะน ัะปััะฐะน
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
ื ืืชื ืืืขืจืื ืืช ืืืืจืืืืช ื-O(log(n)).
ืืฆืืืช ืืืงืกืืืื/ืืื ืืืื ืืขืฅ
ืืจืืจ, ืืื ืืืฆืื ืืช ืืขืจื ืืืื ืืืื / ืืืงืกืืืื ืืขืฅ - ืืชื ืฆืจืื ืืขืืืจ ืืจืฆืฃ ืืช ืฉืจืฉืจืช ืืืืื ืืื ืืฉืืืื / ืืืื ืฉื ืืขืฅ, ืืืชืืื; ืืฉืชืืืขื ืืขืื, ืื ืืืื ืืืืื ื ืืืื ืืืื/ืืงืกืืืื.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
ืืืจืืืืช - O(log(n))
ืืขืงืฃ ืกืืืืจื
ืืฆืื ืืื ืืืงืืจ ืืื ืฆืืืช ืฉื ืืขืฅ ืืื ืืขืฉืืช ืืืชื ืืฉืื.
ืืืืืจืืชื ืืขืืจ ืกืืืืจื ืจืงืืจืกืืื:
- ืืฆืข ืคืขืืื ืขื ืืืื ืืฉืืืื
- ืขืฉื ืคืขืืื ืขื ืขืฆืื
- ืืฆืข ืคืขืืื ืขื ืืืื ืื ืืื
ืงืื:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//ะะดะตัั ะผะพะถะตั ะฑััั ะฒัะต, ััะพ ัะณะพะดะฝะพ
inOrder(current.getRightChild());
}
}
ืืกืงื ื
ืกืืฃ ืื ืกืืฃ! ืื ืื ืืกืืจืชื ืืฉืื ืื ืฉืืฉ ืื ืืขืจืืช, ืื ืื ื ืืืื ืืชืืืืืช. ืืคื ืฉืืืืื, ืื ื ืืงืื ืืืื.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
ื .ื.
ื ืืืื ื-O(n)
ืจืืื ืืื ืืืื ืฉืื ืื: ืื ืื ืชืืจืื ืืขืฅ ืืืืืช ืื ืืืืื? ืืืืืื, ืฉืื ืฆืืชืื ืืขืฅ ืขื ืืคืชืืืช ืืืืืื ืืืืืื: 1,2,3,4,5,6... ืืื ืืขืฅ ืืืืืจ ืงืฆืช ืจืฉืืื ืืงืืฉืจืช. ืืื, ืืขืฅ ืืืื ืืช ืืื ื ืืขืฅ ืฉืื, ืืืืื ืืช ืืขืืืืช ืืืืฉื ืื ืชืื ืื. ืืืืจืืืืช ืฉื ืคืขืืืืช ืืืคืืฉ, ืืื ืกื ืืืืืงื ืชืืคืื ืืืืืช ืืื ืืื ืฉื ืจืฉืืื ืืงืืฉืจืช: O(n). ืืื ืืื ืืืกืจืื ืืช ืืืฉืืืื ืืืืชืจ, ืืืขืชื, ืฉื ืขืฆืื ืืื ืืจืืื.
ืจืง ืืฉืชืืฉืื ืจืฉืืืื ืืืืืื ืืืฉืชืชืฃ ืืกืงืจ.
ืื ืืืืชื ื-Habrรฉ ืื ืืจืื ืืื, ืืืืืชื ืจืืฆื ืืืขืช ืืืื ืืืืจืื ืืืืื ื ืืฉืืื ืืืืช ืจืืฆื ืืจืืืช ืืืชืจ?
-
ืืื ื ืืืืข
-
ืืืืืจืืชืืื (DP, ืจืงืืจืกืื, ืืืืกืช ื ืชืื ืื ืืื')
-
ืืืฉืื ืืื ื ื ืชืื ืื ืืืืืืจืืชืืื ืืืืื ืืืืืชืืื
-
ืชืื ืืช ืืคืืืงืฆืืืช ืื ืืจืืืื ื-Java
-
ืชืื ืืช ืืืฉืืื ืืื ืืจื ื Java
2 ืืฉืชืืฉืื ืืฆืืืขื. 1 ืืฉืชืืฉืื ื ืื ืขื.
ืืงืืจ: www.habr.com