写一个跳表的代码
时间: 2023-12-01 13:06:31 浏览: 36
以下是一个简单的跳表实现,包含插入、删除和查询功能:
```python
import random
class SkipListNode:
def __init__(self, val=None, right=None, down=None):
self.val = val
self.right = right
self.down = down
class SkipList:
def __init__(self):
self.head = SkipListNode()
self.levels = 0
def __str__(self):
res = []
node = self.head
while node:
curr = node.right
row = []
while curr:
row.append(str(curr.val))
curr = curr.right
res.append(" -> ".join(row))
node = node.down
return "\n".join(res)
def insert(self, val):
node = self.head
stack = []
while node:
while node.right and node.right.val < val:
node = node.right
stack.append(node)
node = node.down
prev = None
while stack:
node = stack.pop()
new_node = SkipListNode(val)
new_node.right = node.right
node.right = new_node
if prev:
new_node.down = prev
prev = new_node
if random.random() < 0.5:
break
if prev.down:
return
new_head = SkipListNode()
new_head.right = prev
new_head.down = self.head
self.head = new_head
self.levels += 1
def delete(self, val):
node = self.head
while node:
while node.right and node.right.val < val:
node = node.right
if node.right and node.right.val == val:
node.right = node.right.right
node = node.down
def search(self, val):
node = self.head
while node:
while node.right and node.right.val < val:
node = node.right
if node.right and node.right.val == val:
return True
node = node.down
return False
```
在上面的代码中,我们使用了一个 `SkipListNode` 类来表示跳表的节点,其中包含一个值属性 `val`,和两个指针属性 `right` 和 `down`,分别表示右侧节点和下方节点。
跳表本身是一个由多层节点构成的数据结构,因此我们还需要一个 `SkipList` 类来管理整个跳表。在 `SkipList` 的构造函数中,我们初始化了一个空的 `head` 节点,并将 `levels` 属性设为 0。
插入元素时,我们先从头节点开始向下查找,直到找到最底层的合适位置。这个过程中,我们记录下每层的节点栈,以便后续更新节点指针。然后从栈中弹出每个节点,插入新节点,并将它与前一个新节点连接起来。同时,我们还有一定的概率(这里是 50%)向上添加新节点,以保持跳表的平衡。如果最终新节点被添加到了更高的一层,则需要创建一个新的头节点,并将其指向原来的头节点。
删除元素时,我们也是从头节点开始向下查找,找到目标元素所在的位置,然后将其右侧节点删除即可。
查询元素时,同样是从头节点开始向下查找,找到目标元素所在的位置,如果找到了则返回 True,否则返回 False。
以上就是跳表的简单实现,希望对你有所帮助!