Splay Trees的代码
时间: 2024-05-03 10:18:21 浏览: 77
数据结构与程序设计28splaytrees.ppt
下面是一个示例的Splay Tree的Python代码实现:
```python
class SplayTree:
class Node:
def __init__(self, key):
self.key = key
self.parent = None
self.left = None
self.right = None
def __init__(self):
self.root = None
def _splay(self, x):
while x.parent:
p = x.parent
g = p.parent
if g:
if (x == p.left) == (p == g.left):
self._rotate(p)
else:
self._rotate(x)
self._rotate(x)
else:
self._rotate(x)
def _rotate(self, x):
p = x.parent
if not p:
return
g = p.parent
if p.left == x:
b = x.right
x.right = p
p.left = b
else:
b = x.left
x.left = p
p.right = b
if b:
b.parent = p
x.parent = g
if not g:
self.root = x
elif g.left == p:
g.left = x
else:
g.right = x
p.parent = x
def find(self, key):
x = self.root
while x:
if key < x.key:
x = x.left
elif key > x.key:
x = x.right
else:
self._splay(x)
return x
return None
def insert(self, key):
if not self.root:
self.root = self.Node(key)
return
x = self.root
while True:
if key < x.key:
if x.left:
x = x.left
else:
x.left = self.Node(key)
x.left.parent = x
self._splay(x.left)
return
elif key > x.key:
if x.right:
x = x.right
else:
x.right = self.Node(key)
x.right.parent = x
self._splay(x.right)
return
else:
self._splay(x)
return
def delete(self, key):
x = self.find(key)
if not x:
return
if not x.left:
b = x.right
self._transplant(x, x.right)
elif not x.right:
b = x.left
self._transplant(x, x.left)
else:
y = x.right
while y.left:
y = y.left
if y.parent != x:
self._transplant(y, y.right)
y.right = x.right
y.right.parent = y
self._transplant(x, y)
y.left = x.left
y.left.parent = y
b = y
del x
if b:
self._splay(b)
def _transplant(self, u, v):
if not u.parent:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
if v:
v.parent = u.parent
```
这份代码实现了Splay Tree的基本操作,包括查找、插入和删除。其中,查找操作会将查找到的节点通过splay操作旋转到根节点,以提高查找效率。
阅读全文