Реализация разреженной матрицы с использованием двоичного дерева поиска

Question

Я должен реализовать разреженную матрицу (матрицу с преобладанием нулей, поэтому вы записываете только значения, отличные от 0), но я должен реализовать ее с помощью двоичного дерева поиска.

EDIT:

Так что теперь я имею в виду ее реализации, используя строку/столбец в качестве ключа, но то, что я использую в качестве корня этого дерева?

/EDIT

Я надеялся, что когда-то я исследовал бинарные деревья поиска Я бы понять, как эта реализация будет полезным, или, по крайней мере, возможно, но я за жизнь меня не может понять это ,

Я пробовал google безрезультатно, и я сам не могу себе представить, как это сделать.

Я еще не решил, на каком языке я буду это реализовывать, поэтому мне не нужны примеры кода, моя проблема - логика. Мне нужно посмотреть, как это будет работать.

P.S. Я понятия не имею, какие теги использовать, если кто-то может редактировать их, было бы очень благодарно.

Answer 1

Чтобы использовать двоичное дерево, вам необходимо иметь ключ, который отличается для каждой (возможной) записи в матрице. Поэтому, если вы хотите искать (2, 4) в матрице [100, 100], тогда ключ может быть чем-то вроде «002004». С помощью этого ключа вы можете вставить значение в дерево.

Для каждого измерения ключ будет длиннее, поэтому вы также можете считать хеш-функцию хэш-координатами ячейки, а внутри дерева у вас есть список записей для этой хэш-клавиши. Дерево - это только индекс в правом списке. Внутри списка вам необходимо выполнить последовательный поиск. Или, если вы закажете список, который вы можете улучшить, используя двоичный поиск.