...
def insert(self, val):
if val < self.val:
if self.lchild is None:
self.lchild = TreeNode(val)
else:
self.lchild.insert(val)
if val > self.val:
if self.rchild is None:
self.rchild = TreeNode(val)
else:
self.rchild.insert(val)
...
def depth_traversal(self, order="pre"):
if order == "pre":
yield self.val
if self.lchild is not None:
for v in self.lchild.depth_traversal(order=order):
yield v
if order == "in":
yield self.val
if self.rchild is not None:
for v in self.rchild.depth_traversal(order=order):
yield v
if order == "post":
yield self.val
def _rot_right(self):
pivot = self.lchild
self.lchild.rchild, self.lchild = self, self.lchild.rchild
return pivot
def _rot_left(self):
pivot = self.rchild
self.rchild.lchild, self.rchild = self, self.rchild.lchild
return pivot
>>> node.lchild = node.lchild._rot_right()
...
def rebalance(self, head):
if self.lchild is not None:
self.lchild.rebalance(head=head)
if self.rchild is not None:
self.rchild.rebalance(head=head)
balance = self.balance()
if balance > 1:
lbalance = self.lchild.balance()
if lbalance > 1:
self.lchild = self.lchild._rot_right()
elif lbalance < -1:
self.lchild = self.lchild._rot_left()
elif balance < -1:
rbalance = self.rchild.balance()
if rbalance > 1:
self.rchild = self.rchild._rot_right()
elif rbalance < -1:
self.rchild = self.rchild._rot_left()
...
if head is self:
if balance > 1:
head = self._rot_right()
head = head.rebalance(head)
return head
elif balance < -1:
head = self._rot_left()
head = head.rebalance(head)
return head
return self
 |
| "That's Donner. Of all [the reindeer], he may be the cruelest, and definitely the most conniving..." -Pinocchio |
 |
This photo of Piscientum was taken about 12 billion years ago,
before he was impaled through his back by a flagpole.
|
