Я пытаюсь реализовать Skiplist с использованием Python. Вы можете мне помочь? Очень просто

Question

Это просто очень простой код, и моя ссылка отсюда: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html

Я думаю, что функция вставки в порядке, но когда я пытаюсь использовать get() функция, она ничего не возвращает, вместо этого она бесконечно зацикливается внутри searchEntry() часть. Я не знаю что не так. в insert() функция, searchEntry() работает хорошо. Возвращает ссылку на floorEntry(k) запись, содержащая ключ, который меньше ключа, который необходимо вставить в список пропусков. Пожалуйста, помогите мне выяснить источник ошибки в searchEntry() функция. Извините, я не очень хорош в этом. Спасибо!

from QuadLinkedList import QLLNode
import random
class Skippy:


    def __init__(self):

        self._p1 = QLLNode("MINUS_INF")
        self._p2 = QLLNode("PLUS_INF")

        self._head = self._p1
        self._tail = self._p2

        self._p1.setNext(self._p2)
        self._p2.setPrev(self._p1)

        self._height = 0
        self._n = 0

    def insert(self, key, value):

        p = self.searchEntry(key)
        print "p = " + str(p.getKey())
        q = QLLNode(key, value)
        q.setPrev(p)
        q.setNext(p.getNext())
        p.getNext().setPrev(q)
        p.setNext(q)

        i = 0

        while random.randint(0,1) != 0:

            if i >= self._height:
                self._height += 1

                newHead = QLLNode("MINUS_INF")
                newTail = QLLNode("PLUS_INF")

                newHead.setNext(newTail)
                newHead.setDown(self._head)

                newTail.setPrev(newHead)
                newTail.setDown(self._tail)

                self._head.setUp(newHead)
                self._tail.setUp(newTail)

                self._head = newHead
                self._tail = newTail

            while p.getUp() == None:
                p = p.getPrev()

            p = p.getUp()

            e = QLLNode(key,None)

            e.setPrev(p)
            e.setNext(p.getNext())
            e.setDown(q)

            p.getNext().setPrev(e)
            p.setNext(e)
            q.setUp(e)

            q = e

            i += 1

        self._n += 1
        return None

    def get(self, key):
        p = self.searchEntry(key)

        if key == p.getKey():
            return p.getElement()
        else:
            return "There's None!"

    def searchEntry(self, key):
        p = self._head

        while True:
            while p.getNext().getKey() != "PLUS_INF" and p.getNext().getKey() <= key:
                p = p.getNext()
            if p.getDown() != None:
                p = p.getDown()
            else:
                break
        return p

Answer 1

Проблема не в коде для searchEntry, который, кажется, имеет правильную логику. Проблема в том, что структура списка испортилась. Я считаю, что проблема заключается в коде, который у вас есть для добавления нового уровня в список в insert, Конкретно этот бит:

       if i >= self._height:    #make an empty level

            self._height += 1

            self._minus.setNext(self._plus)
            self._minus.setDown(self._head)

            self._plus.setPrev(self._minus)
            self._plus.setDown(self._tail)

            self._head.setUp(self._minus)
            self._tail.setUp(self._plus)

            self._head = self._minus
            self._tail = self._plus

Что выделяет меня в этом коде, так это то, что вы не создаете какие-либо новые узлы, просто модифицируете существующие, что нарушает структуру вашего списка. Вам нужно создать новый head а также tail узлы, я думаю, и связать их в верхней части структуры. (minus а также plus не являются частью алгоритма, как описано в вашей ссылке, поэтому я не уверен, что вы делаете с ними.) Вероятно, вы хотите что-то вроде этого:

       if i >= self._height:    #make an empty level

            self._height += 1

            newHead = QLLNode("MINUS_INF")
            newTail = QLLNode("PLUS_INF")

            newHead.setNext(newTail)
            newHead.setDown(self._head)

            newTail.setPrev(newHead)
            newTail.setDown(self._tail)

            self._head.setUp(newHead)
            self._head = newHead

            self._tail.setUp(newTail)
            self._tail = newTail