LINUX.ORG.RU
Форум — Development  

метод удаления из бинарного дерева не работает

 


0

1

Помогите кто-нибудь найти ошибку в коде, не могу понять почему он не работает. Точнее, после удаления нескольких элементов дерево линкуется неправильно и потом выкидывает NullPointerException(), потому что не может найти элемент (который в дереве точно есть).

// в коде: .next - право, .prev - лево

Алгоритм:

Если дерево T пусто, остановиться;
Иначе сравнить K с ключом X корневого узла n.
Если K>X, рекурсивно удалить K из правого поддерева Т;
Если K<X, рекурсивно удалить K из левого поддерева Т;
Если K=X, то необходимо рассмотреть три случая.
Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
Если оба ребёнка присутствуют, то найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
скопируем данные (кроме ссылок на дочерние элементы) из m в n; рекурсивно удалим узел m.

сам код:


	public void remove(T t) {
		Node<T> curr, replacement;
		Node<T> newItem = new Node<T>(t);
		
		lock.lock();
		curr = tree;
		
		try {
			
			if (curr.item != null) {
				
				while (curr.compareTo(newItem) != 0) {
					if (curr.compareTo(newItem) == 1) {
						curr = curr.next;
					} 
					else {
						curr = curr.prev;
					}
				}
				
				if (curr.next == null && curr.prev == null) {
					curr = null;
				} 
				else if (curr.next == null) {
					curr.item = curr.prev.item;
					curr.prev = null;
				} 
				else if (curr.prev == null) {
					curr.item = curr.next.item;
					curr.next = null;
				} 
				else {
					replacement = curr.next;					
					
					if (replacement.prev != null && replacement.next != null) {
						replacement = replacement.prev;
						Node<T> link = curr.next;

						while (replacement.prev != null) {
							link = replacement;
							replacement = replacement.prev;
						}
                                          
                                                curr.item = replacement.item;
						
						if (replacement.next != null) {
							link.prev = replacement.next;
						} else {
							replacement = null;
						}
						
					} 
					else if (replacement.next != null) {
						curr.item = replacement.item;
						curr.next = curr.next.next;
					} else {
						curr.item = replacement.item;
						curr.next = null;
					}
					
				}
			
			
		} catch (UnsupportedOperationException e) {
			throw new UnsupportedOperationException();
		} finally {
			lock.unlock();
		}
	}
☆

Последнее исправление: Sonsee (всего исправлений: 2)
← Kubuntu 12.04 Установил родную java, но Eclipse всё равно при установке тянет OpenJDK
Python & pygame: Не устанавливается частота дискретизации для воспроизведения звука →

Как все сложно. Мне всегда казалось, что такое пишется рекурсией. 

while (curr.compareTo(newItem) != 0) {
    if (curr.compareTo(newItem) == 1) {
        curr = curr.next;
    } 
    else {
        curr = curr.prev;
    }
}
Вот это например выглядит странным, но я не знаю, как там данные у тебя устроены.

anonymous
()
Ответ на: комментарий от anonymous

ну да понятно рекурсией пишется в пять строк, надо без.

какие данные? класс Node<T> показать? В каждом элементе типа Node<T> есть два указателя .next и .prev того же типа, и .item, куда я кладу обычный int. Все. Запускаю с одним ядром, да и все дерево каждый раз лочится же..

Sonsee ☆
() автор топика
Ответ на: комментарий от TheKnight

http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Comparable.html

все абсолютно безобидно :)

package data_structures;

import java.util.concurrent.locks.ReentrantLock;


public class Node<T extends Comparable<T>> {
	
	Node<T> next, prev;
	T item;
	
	private ReentrantLock lock;
	
	public Node(T t) {
		item = t;
		next = null;
		prev = null;
		lock = new ReentrantLock();
	}
	
	public int compareTo(Object obj) {
		final int BEFORE = -1;
	    final int EQUAL = 0;
	    final int AFTER = 1;
	    
	    Node<T> node = new Node<T>(null);
	    
	    if (obj instanceof Node<?>) {
	    	node = (Node<T>)obj;
	    	
	    	if (this.item instanceof Integer) {
		    	Integer o = (Integer)node.item;
		    	Integer a = (Integer)item;
		    	
		    	if (a > o) {
		    		return BEFORE;
		    	}
		    	else if (a < o) {
		    		return AFTER;
		    	}
		    }
	    }
	    
	    return EQUAL;
	}

	public void lock() {
		lock.lock();
	}
	
	public void unlock() {
		if (lock.isHeldByCurrentThread()) {
			lock.unlock();
		}
	}
}
Sonsee ☆
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Kubuntu 12.04 Установил родную java, но Eclipse всё равно при установке тянет OpenJDK
Development
Python & pygame: Не устанавливается частота дискретизации для воспроизведения звука →