āĻĒā§āĻ°āĻ¸ā§āĻ¤āĻžāĻŦāĻ¨āĻž
āĻāĻ āĻ¨āĻŋāĻŦāĻ¨ā§āĻ§āĻāĻŋ āĻŦāĻžāĻāĻ¨āĻžāĻ°āĻŋ āĻ
āĻ¨ā§āĻ¸āĻ¨ā§āĻ§āĻžāĻ¨ āĻāĻžāĻ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§. āĻāĻŽāĻŋ āĻ¸āĻŽā§āĻĒā§āĻ°āĻ¤āĻŋ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻāĻāĻŋ āĻ¨āĻŋāĻŦāĻ¨ā§āĻ§ āĻ˛āĻŋāĻā§āĻāĻŋāĻ˛āĻžāĻŽ
āĻāĻāĻāĻŋ āĻā§āĻ°āĻŋ āĻšāĻ˛ āĻāĻāĻāĻŋ āĻĄāĻžāĻāĻž āĻ¸ā§āĻā§āĻ°āĻžāĻāĻāĻžāĻ° āĻ¯āĻž āĻāĻŋāĻ¨āĻžāĻ°āĻž āĻĻā§āĻŦāĻžāĻ°āĻž āĻ¸āĻāĻ¯ā§āĻā§āĻ¤ āĻ¨ā§āĻĄ āĻ¨āĻŋāĻ¯āĻŧā§ āĻāĻ āĻŋāĻ¤āĨ¤ āĻāĻŽāĻ°āĻž āĻŦāĻ˛āĻ¤ā§ āĻĒāĻžāĻ°āĻŋ āĻ¯ā§ āĻāĻāĻāĻŋ āĻāĻžāĻ āĻāĻāĻāĻŋ āĻā§āĻ°āĻžāĻĢā§āĻ° āĻāĻāĻāĻŋ āĻŦāĻŋāĻļā§āĻˇ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§āĨ¤ āĻāĻāĻžāĻ¨ā§ āĻāĻāĻāĻŋ āĻāĻĻāĻžāĻšāĻ°āĻŖ āĻāĻžāĻ āĻāĻā§:
āĻāĻāĻŋ āĻāĻāĻāĻŋ āĻŦāĻžāĻāĻ¨āĻžāĻ°āĻŋ āĻ
āĻ¨ā§āĻ¸āĻ¨ā§āĻ§āĻžāĻ¨ āĻāĻžāĻ āĻ¨āĻ¯āĻŧ! āĻ¸āĻŦāĻ āĻ¤ā§ āĻāĻžāĻāĻžāĻ° āĻ¨āĻŋāĻā§!
āĻĒāĻ°āĻŋāĻāĻžāĻˇāĻž
āĻŽā§āĻ˛
āĻāĻžāĻā§āĻ° āĻŽā§āĻ˛ āĻļā§āĻ°ā§āĻˇāĻ¸ā§āĻĨāĻžāĻ¨ā§āĻ¯āĻŧ āĻ¨ā§āĻĄāĨ¤ āĻāĻĻāĻžāĻšāĻ°āĻŖā§, āĻāĻāĻŋ āĻāĻāĻāĻŋ āĻ¨ā§āĻĄāĨ¤ āĻāĻ¸āĻ˛ā§, āĻ¯ā§āĻā§āĻ¨ā§ āĻ¨ā§āĻĄāĻā§ āĻāĻ āĻ¨ā§āĻĄā§āĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻāĻŋāĻ¤ āĻ¸āĻžāĻŦāĻā§āĻ°āĻŋāĻ° āĻŽā§āĻ˛ āĻšāĻŋāĻ¸āĻžāĻŦā§ āĻŦāĻŋāĻŦā§āĻāĻ¨āĻž āĻāĻ°āĻž āĻ¯ā§āĻ¤ā§ āĻĒāĻžāĻ°ā§āĨ¤
āĻĒāĻŋāĻ¤āĻžāĻŽāĻžāĻ¤āĻž/āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨
āĻ°ā§āĻ āĻŦā§āĻ¯āĻ¤ā§āĻ¤ āĻ¸āĻŽāĻ¸ā§āĻ¤ āĻ¨ā§āĻĄā§āĻ° āĻ āĻŋāĻ āĻāĻ āĻĒā§āĻ°āĻžāĻ¨ā§āĻ¤ āĻĨāĻžāĻā§ āĻ¯āĻž āĻ āĻ¨ā§āĻ¯ āĻ¨ā§āĻĄ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻ¯āĻžāĻ¯āĻŧāĨ¤ āĻŦāĻ°ā§āĻ¤āĻŽāĻžāĻ¨ āĻ¨ā§āĻĄā§āĻ° āĻāĻĒāĻ°ā§āĻ° āĻ¨ā§āĻĄāĻā§ āĻŦāĻ˛āĻž āĻšāĻ¯āĻŧ āĻ āĻāĻŋāĻāĻžāĻŦāĻ āĻāĻ āĻ¨ā§āĻĄ āĻŦāĻ°ā§āĻ¤āĻŽāĻžāĻ¨ā§āĻ° āĻ¨ā§āĻā§ āĻ āĻŦāĻ¸ā§āĻĨāĻŋāĻ¤ āĻāĻŦāĻ āĻāĻāĻŋāĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻāĻ¯ā§āĻā§āĻ¤ āĻāĻāĻāĻŋ āĻ¨ā§āĻĄāĻā§ āĻŦāĻ˛āĻž āĻšāĻ¯āĻŧ āĻŦāĻāĻļāĻ§āĻ° āĻāĻ āĻ¨ā§āĻĄ āĻāĻāĻāĻž āĻāĻĻāĻžāĻšāĻ°āĻŖ āĻ¨ā§āĻāĻ¯āĻŧāĻž āĻ¯āĻžāĻāĨ¤ āĻ¨ā§āĻĄ 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 āĻļāĻŋāĻļā§āĻ°āĻž āĻļā§āĻ¨ā§āĻ¯ āĻšāĻŦā§)āĨ¤ āĻāĻĒāĻ¨āĻŋ āĻ¸āĻŽā§āĻāĻŦāĻ¤ āĻŦā§āĻāĻ¤ā§ āĻĒā§āĻ°ā§āĻā§āĻ¨ āĻ¯ā§ āĻāĻ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§ āĻ¸āĻāĻā§āĻ¯āĻž āĻĄā§āĻāĻž āĻšāĻ˛ āĻ¨ā§āĻĄā§ āĻ¸āĻāĻ°āĻā§āĻˇāĻŋāĻ¤ āĻĄā§āĻāĻž; āĻā§ - āĻ¨ā§āĻĄ āĻā§āĨ¤
āĻāĻŽāĻ°āĻž āĻāĻŋāĻāĻāĻāĻŋ āĻŦā§āĻ° āĻāĻ°ā§āĻāĻŋ, āĻāĻāĻ¨ āĻāĻžāĻā§āĻ° āĻāĻžāĻĒā§āĻ° āĻ¸āĻŽāĻ¸ā§āĻ¯āĻž āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻĨāĻž āĻŦāĻ˛āĻž āĻ¯āĻžāĻāĨ¤ āĻāĻāĻžāĻ¨ā§ āĻāĻŦāĻ āĻ¨ā§āĻā§, "āĻŦā§āĻā§āĻˇ" āĻļāĻŦā§āĻĻā§āĻ° āĻ āĻ°ā§āĻĨ āĻšāĻŦā§ āĻāĻāĻāĻŋ āĻŦāĻžāĻāĻ¨āĻžāĻ°āĻŋ āĻ āĻ¨ā§āĻ¸āĻ¨ā§āĻ§āĻžāĻ¨ āĻāĻžāĻā§āĻ° āĻ§āĻžāĻ°āĻŖāĻžāĨ¤ āĻŦāĻžāĻāĻ¨āĻžāĻ°āĻŋ āĻāĻžāĻā§āĻ° āĻāĻ āĻ¨:
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;
}
}
}
}
}
āĻāĻ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§, āĻŦāĻ°ā§āĻ¤āĻŽāĻžāĻ¨ āĻ¨ā§āĻĄ āĻāĻžāĻĄāĻŧāĻžāĻ, āĻŦāĻ°ā§āĻ¤āĻŽāĻžāĻ¨ āĻ¨ā§āĻĄā§āĻ° āĻĒā§āĻ¯āĻžāĻ°ā§āĻ¨ā§āĻ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻ¤āĻĨā§āĻ¯ āĻ¸āĻāĻ°āĻā§āĻˇāĻŖ āĻāĻ°āĻž āĻĒā§āĻ°āĻ¯āĻŧā§āĻāĻ¨āĨ¤ āĻāĻžāĻ°ā§āĻ¨ā§āĻ āĻ¨āĻžāĻ˛ āĻšāĻ¯āĻŧā§ āĻā§āĻ˛ā§, āĻĒā§āĻ¯āĻžāĻ°ā§āĻ¨ā§āĻ āĻā§āĻ°āĻŋāĻ¯āĻŧā§āĻŦāĻ˛ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻĒā§āĻ°āĻ¯āĻŧā§āĻāĻ¨ā§āĻ¯āĻŧ āĻļā§āĻ āĻĨāĻžāĻāĻŦā§āĨ¤
āĻ¸āĻ¨ā§āĻ¨āĻŋāĻŦā§āĻļ āĻāĻžāĻ°ā§āĻ¯āĻāĻžāĻ°āĻŋāĻ¤āĻž āĻ¸ā§āĻĒāĻˇā§āĻāĻ¤āĻ āĻ
āĻ¨ā§āĻ¸āĻ¨ā§āĻ§āĻžāĻ¨ā§āĻ° āĻŽāĻ¤ā§āĻ āĻšāĻŦā§ - O(log(n))ā§ˇ
āĻ āĻĒāĻ¸āĻžāĻ°āĻŖ
āĻŽā§āĻā§ āĻĢā§āĻ˛āĻž āĻšāĻ˛ āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻāĻāĻŋāĻ˛ āĻ āĻĒāĻžāĻ°ā§āĻļāĻ¨ āĻ¯āĻž āĻāĻāĻāĻŋ āĻāĻžāĻ āĻĻāĻŋāĻ¯āĻŧā§ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻāĻž āĻ¸ā§āĻĒāĻˇā§āĻ āĻ¯ā§ āĻĒā§āĻ°āĻĨāĻŽā§ āĻāĻŽāĻ°āĻž āĻ¯ā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋ āĻ¸āĻ°āĻžāĻ¤ā§ āĻ¯āĻžāĻā§āĻāĻŋ āĻ¤āĻž āĻā§āĻāĻā§ āĻŦā§āĻ° āĻāĻ°āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻ¤āĻžāĻ°āĻĒāĻ° āĻāĻŋ? āĻ¯āĻĻāĻŋ āĻāĻŽāĻ°āĻž āĻāĻ° āĻ°ā§āĻĢāĻžāĻ°ā§āĻ¨ā§āĻ¸āĻāĻŋ null āĻ āĻ¸ā§āĻ āĻāĻ°āĻŋ, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻŽāĻ°āĻž āĻ¯ā§ āĻ¸āĻžāĻŦāĻā§āĻ°āĻŋāĻ° āĻŽā§āĻ˛ āĻāĻ āĻ¨ā§āĻĄāĻāĻŋ āĻ¸ā§ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻ¤āĻĨā§āĻ¯ āĻšāĻžāĻ°āĻžāĻŦā§āĨ¤ āĻāĻžāĻ āĻ āĻĒāĻ¸āĻžāĻ°āĻŖ āĻĒāĻĻā§āĻ§āĻ¤āĻŋ āĻ¤āĻŋāĻ¨āĻāĻŋ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§ āĻŦāĻŋāĻāĻā§āĻ¤ āĻāĻ°āĻž āĻšāĻ¯āĻŧ.
āĻĒā§āĻ°āĻĨāĻŽ āĻŽāĻžāĻŽāĻ˛āĻžāĨ¤ āĻ¯ā§ āĻ¨ā§āĻĄāĻāĻŋ āĻ¸āĻ°āĻžāĻ¨ā§ āĻšāĻŦā§ āĻ¤āĻžāĻ° āĻā§āĻ¨ āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨ āĻ¨ā§āĻāĨ¤
āĻ¯āĻĻāĻŋ āĻŽā§āĻā§ āĻĢā§āĻ˛āĻž āĻ¨ā§āĻĄā§āĻ° āĻā§āĻ¨ āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨ āĻ¨āĻž āĻĨāĻžāĻā§, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻ° āĻŽāĻžāĻ¨ā§ āĻšāĻ˛ āĻāĻāĻŋ āĻāĻāĻāĻŋ āĻĒāĻžāĻ¤āĻžāĨ¤ āĻ āĻ¤āĻāĻŦ, āĻāĻĒāĻ¨āĻŋ āĻā§āĻŦāĻ˛āĻŽāĻžāĻ¤ā§āĻ° āĻāĻ° āĻĒāĻŋāĻ¤āĻžāĻŽāĻžāĻ¤āĻžāĻ° leftChild āĻŦāĻž rightChild āĻā§āĻˇā§āĻ¤ā§āĻ°āĻā§āĻ˛āĻŋāĻā§ āĻ¨āĻžāĻ˛ āĻ¸ā§āĻ āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§āĻ¨āĨ¤
āĻĻā§āĻŦāĻŋāĻ¤ā§āĻ¯āĻŧ āĻŽāĻžāĻŽāĻ˛āĻžāĨ¤ āĻ¯ā§ āĻ¨ā§āĻĄāĻāĻŋ āĻ āĻĒāĻ¸āĻžāĻ°āĻŖ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§ āĻ¤āĻžāĻ° āĻāĻāĻāĻŋ āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨ āĻāĻā§
āĻāĻ āĻŽāĻžāĻŽāĻ˛āĻžāĻāĻŋāĻ āĻā§āĻŦ āĻāĻ āĻŋāĻ¨ āĻ¨āĻ¯āĻŧāĨ¤ āĻāĻ¸ā§āĻ¨ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻĻāĻžāĻšāĻ°āĻŖā§ āĻĢāĻŋāĻ°ā§ āĻ¯āĻžāĻāĨ¤ āĻ§āĻ°ā§āĻ¨ āĻāĻŽāĻžāĻĻā§āĻ° āĻā§ 14 āĻĻāĻŋāĻ¯āĻŧā§ āĻāĻāĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻŽā§āĻā§ āĻĢā§āĻ˛āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻ¸āĻŽā§āĻŽāĻ¤ āĻšāĻ¨ āĻ¯ā§ āĻ¯ā§āĻšā§āĻ¤ā§ āĻāĻāĻŋ āĻā§ 10-āĻāĻ° āĻ¸āĻžāĻĨā§ āĻāĻāĻāĻŋ āĻ¨ā§āĻĄā§āĻ° āĻ¸āĻ āĻŋāĻ āĻāĻžāĻāĻ˛ā§āĻĄ, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻ° āĻ¯ā§āĻā§āĻ¨ā§ āĻāĻ¤ā§āĻ¤āĻ°āĻ¸ā§āĻ°āĻŋāĻ° (āĻāĻ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§, āĻĄāĻžāĻ¨āĻāĻŋāĻ°) 10-āĻāĻ° āĻā§āĻ¯āĻŧā§ āĻŦāĻĄāĻŧ āĻāĻāĻāĻŋ āĻā§ āĻĨāĻžāĻāĻŦā§, āĻ¤āĻžāĻ āĻāĻĒāĻ¨āĻŋ āĻāĻāĻŋāĻā§ āĻ¸āĻšāĻā§āĻ āĻāĻžāĻ āĻĨā§āĻā§ "āĻāĻžāĻ" āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§ āĻāĻŦāĻ āĻ¨ā§āĻĄā§āĻ° āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨ā§āĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻ°āĻžāĻ¸āĻ°āĻŋ āĻ āĻāĻŋāĻāĻžāĻŦāĻāĻā§ āĻ¸āĻāĻ¯ā§āĻ āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§, āĻ¯ā§āĻŽāĻ¨ āĻ¨ā§āĻĄāĻā§ 10 āĻā§ āĻĻāĻŋāĻ¯āĻŧā§ āĻ¨ā§āĻĄ 13-āĻāĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻāĻ¯ā§āĻā§āĻ¤ āĻāĻ°ā§āĻ¨āĨ¤ āĻĒāĻ°āĻŋāĻ¸ā§āĻĨāĻŋāĻ¤āĻŋ āĻāĻāĻ āĻ°āĻāĻŽ āĻšāĻŦā§ āĻ¯āĻĻāĻŋ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻāĻāĻŋ āĻ¨ā§āĻĄ āĻŽā§āĻā§ āĻĢā§āĻ˛āĻ¤ā§ āĻšāĻ¯āĻŧ āĻ¯āĻž āĻ¤āĻžāĻ° āĻĒāĻŋāĻ¤āĻžāĻŽāĻžāĻ¤āĻžāĻ° āĻŦāĻžāĻŽ āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨āĨ¤ āĻ¨āĻŋāĻā§āĻ° āĻāĻ¨ā§āĻ¯ āĻāĻāĻŋ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻŋāĻ¨ā§āĻ¤āĻž āĻāĻ°ā§āĻ¨ - āĻāĻāĻāĻŋ āĻ¸āĻ āĻŋāĻ āĻāĻĒāĻŽāĻžāĨ¤
āĻ¤ā§āĻ¤ā§āĻ¯āĻŧ āĻŽāĻžāĻŽāĻ˛āĻžāĨ¤ āĻ¨ā§āĻĄā§āĻ° āĻĻā§āĻāĻŋ āĻ¸āĻ¨ā§āĻ¤āĻžāĻ¨ āĻ°āĻ¯āĻŧā§āĻā§
āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻāĻ āĻŋāĻ¨ āĻā§āĻ¸āĨ¤ āĻāĻ° āĻāĻāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻāĻĻāĻžāĻšāĻ°āĻŖ āĻāĻāĻžāĻā§āĻˇāĻĒāĻžāĻ¤ āĻāĻ°āĻž āĻ¯āĻžāĻ.
āĻāĻāĻāĻ¨ āĻāĻ¤ā§āĻ¤āĻ°āĻ¸ā§āĻ°āĻŋ āĻā§āĻāĻā§āĻ¨
āĻ§āĻ°āĻž āĻ¯āĻžāĻ āĻāĻŽāĻžāĻĻā§āĻ° āĻā§ āĻĻāĻŋāĻ¯āĻŧā§ āĻ¨ā§āĻĄāĻāĻŋ āĻ āĻĒāĻ¸āĻžāĻ°āĻŖ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§ 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)āĨ¤ āĻāĻāĻŋ āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻā§āĻ°ā§āĻ¤ā§āĻŦāĻĒā§āĻ°ā§āĻŖ āĻāĻ, āĻāĻŽāĻžāĻ° āĻŽāĻ¤ā§, āĻŦāĻžāĻāĻ¨āĻžāĻ°āĻŋ āĻāĻžāĻā§āĻ° āĻ āĻ¸ā§āĻŦāĻŋāĻ§āĻžāĨ¤
āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° āĻ¨āĻŋāĻŦāĻ¨ā§āĻ§āĻŋāĻ¤ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ°āĻāĻžāĻ°ā§āĻ°āĻž āĻāĻ°āĻŋāĻĒā§ āĻ
āĻāĻļāĻā§āĻ°āĻšāĻŖ āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°āĻŦā§āĻ¨āĨ¤
āĻāĻŽāĻŋ āĻ āĻ¨ā§āĻ āĻĻāĻŋāĻ¨ āĻ§āĻ°ā§ āĻšā§āĻ¯āĻžāĻŦā§āĻ°ā§ āĻāĻŋāĻ˛āĻžāĻŽ āĻ¨āĻž, āĻāĻŦāĻ āĻāĻŽāĻŋ āĻāĻžāĻ¨āĻ¤ā§ āĻāĻžāĻ āĻ¯ā§ āĻāĻĒāĻ¨āĻŋ āĻā§āĻ¨ āĻŦāĻŋāĻˇāĻ¯āĻŧā§ āĻāĻ°āĻ āĻĻā§āĻāĻ¤ā§ āĻāĻžāĻ¨?
-
āĻāĻĒāĻžāĻ¤ā§āĻ¤ āĻāĻžāĻ āĻžāĻŽā§
-
āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ (DP, recursion, data āĻāĻŽā§āĻĒā§āĻ°ā§āĻļāĻ¨, āĻāĻ¤ā§āĻ¯āĻžāĻĻāĻŋ)
-
āĻŦāĻžāĻ¸ā§āĻ¤āĻŦ āĻā§āĻŦāĻ¨ā§ āĻĄā§āĻāĻž āĻ¸ā§āĻā§āĻ°āĻžāĻāĻāĻžāĻ° āĻāĻŦāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻĒā§āĻ°āĻ¯āĻŧā§āĻ
-
āĻāĻžāĻāĻžāĻ¤ā§ āĻ ā§āĻ¯āĻžāĻ¨ā§āĻĄā§āĻ°āĻ¯āĻŧā§āĻĄ āĻ ā§āĻ¯āĻžāĻĒā§āĻ˛āĻŋāĻā§āĻļāĻ¨ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻŋāĻ
-
āĻāĻžāĻāĻž āĻāĻ¯āĻŧā§āĻŦ āĻ ā§āĻ¯āĻžāĻĒā§āĻ˛āĻŋāĻā§āĻļāĻ¨ āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻŋāĻ
2 āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ°āĻāĻžāĻ°ā§ āĻā§āĻ āĻĻāĻŋāĻ¯āĻŧā§āĻā§āĻ¨āĨ¤ ā§§ āĻāĻ¨ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ°āĻāĻžāĻ°ā§ āĻŦāĻŋāĻ°āĻ¤ āĻāĻŋāĻ˛ā§āĻ¨āĨ¤
āĻ¸ā§āĻ¤ā§āĻ°: www.habr.com