Lines Matching full:self
32 def __init__(self, key, value):
33 self.key = key
34 self.value = value
35 self.left = None
36 self.right = None
42 def __init__(self, key):
43 self.key = key
49 def __init__(self):
51 self.root = None
53 def IsEmpty(self):
55 return not self.root
57 def Insert(self, key, value):
60 if self.IsEmpty():
61 self.root = Node(key, value)
65 self.Splay(key)
67 if self.root.key == key:
71 if key > self.root.key:
72 node.left = self.root
73 node.right = self.root.right
74 self.root.right = None
76 node.right = self.root
77 node.left = self.root.left
78 self.root.left = None
79 self.root = node
81 def Remove(self, key):
84 if self.IsEmpty():
87 self.Splay(key)
89 if self.root.key != key:
91 removed = self.root
93 if not self.root.left:
95 self.root = self.root.right
98 right = self.root.right
100 self.root = self.root.left
102 self.Splay(key)
105 self.root.right = right
108 def Find(self, key):
110 if self.IsEmpty():
112 self.Splay(key)
113 if self.root.key == key:
114 return self.root
117 def FindMax(self):
119 if self.IsEmpty():
121 current = self.root
127 def FindMin(self):
128 if self.IsEmpty():
130 current = self.root
135 def FindGreatestsLessThan(self, key):
137 if self.IsEmpty():
141 self.Splay(key)
144 if self.root.key <= key:
145 return self.root
147 tmp = self.root
148 self.root = self.root.left
149 result = self.FindMax()
150 self.root = tmp
153 def ExportValueList(self):
156 nodes_to_visit = [self.root]
166 def Splay(self, key):
176 "Self-adjusting Binary Search Trees" by Sleator and Tarjan
179 if self.IsEmpty():
187 current = self.root
226 self.root = current
