python - Rotation of AVL tree nodes does not work -


i trying write avl tree in python rotation doesnt work becase cannot swap "self" node other. there way fix it? think doing in java or c way not correct...

class sentinel(object):      value = left = right = none      height = -1  sentinel = sentinel() #singleton of sentinel node  class node:     def __init__(self, data, left=sentinel, right=sentinel, height=0):     self.data = data     self.left = left     self.right = right     self.height = height  def addnode(self, data):     if self.data == data:         #return when node duplicated         return     isleft = self.data > data     child = self.left if isleft else self.right      if child sentinel:         if isleft:             self.left = node(data)         else:             self.right = node(data)     else:         child.addnode(data)         if abs(child.right.height - child.left.height) == 2:             print("rebalancing after inserting", data)             ''' need balance subtree'''             if data < child.data:                 rotation = self.rotateleft if isleft else self.rotateright             else:                 rotation = self.doublerotateleft if isleft else self.doublerotateright             rotation()             self.left.setheight() if isleft else self.right.setheight()         self.setheight()  def printnodes(self):     if self.left not sentinel:         self.left.printnodes()     print(self)     if self.right not sentinel:         self.right.printnodes()   def setheight(self):     self.height = max(self.left.height, self.right.height) + 1  def rotateright(self):     new_root = self.left     new_left_sub = new_root.right     old_root = self     self = new_root     old_root.left = new_left_sub     new_root.right = old_root  def rotateleft(self):     new_root = self.right     new_left_sub = new_root.left     old_root = self     self = new_root     old_root.right = new_left_sub     new_root.left = old_root  def doublerotateright(self):     return  def doublerotateleft(self):     return  def __str__(self):     return str(self.data)  class binarytree:  def __init__(self):     self.root = sentinel  def add(self, data):     print("before adding", data)     self.printall()     if self.root sentinel:         self.root = node(data)     else:         self.root.addnode(data)   def printall(self):     if self.root sentinel:         print("empty tree")     else:         self.root.printnodes()  if __name__ == '__main__': b = binarytree() b.add(1) b.add(22) b.add(4) b.add(26) b.add(13) b.add(3) b.add(14) b.add(6) b.add(13) b.add(5) b.add(36) b.add(43) b.add(5) in range(1, 20):     b.add(i) b.printall()

i suggest nodes contain link parent (the root having parent). easy:

def rotateleft(self):     new_root = self.right     new_left_sub = new_root.left     old_root = self      self.parent.right = new_root #assuming self right child     old_root.right = new_left_sub     new_root.left = old_root

my code may not correct, can't test right now, idea is: have nodes keep reference parent.

some reference: http://interactivepython.org/runestone/static/pythonds/trees/avltreeimplementation.html


Comments

Post a Comment

Popular posts from this blog

javascript - jQuery: Add class depending on URL in the best way -

i have html progress meter: <div class="col-md-3" style="margin-left: -20px;"> <div class="progress-pos active" id="progess-1"> <div class="progress-pos-inner"> login </div> </div> </div> <div class="col-md-3 progress-pos-container"> <div class="progress-pos" id="progess-2"> <div class="progress-pos-inner"> scan items </div> </div> </div> <div class="col-md-3 progress-pos-container"> <div class="progress-pos" id="progess-3"> <div class="progress-pos-inner"> confirm address </div> </div> </div> <div class="col-md-3 progress-pos-container"> <div class="progress-pos" id="progess-4"> <div class="progress-pos-in...
Read more

caching - How to check if a url path exists in the service worker cache -

i need check if particular url path exists in service worker cache. example, suppose url is: /myserviceworker/service?a=110&b=70 this url exists in cache, there many of them different values of , b. now, suppose want refresh of these urls, how can that? i want know how access key values service worker cache. if know key, plan follows: var url = new url(key); if(url.pathname === "\/myserviceworker/service") refetch key but not sure how cache key , in format is. mean, string or url? cache api has match() method returns promise resolving in response object if match or undefined if no match exists. second parameter object can specify ignoresearch not take account url parameters. the ignoresearch option supported firefox ( chrome status here ). in other hand, retrieve cache entries, can use keys() method.
Read more

Redirect to a HTTPS version using .htaccess -

i need modify .htaccess file redirect urls https version without "www". http://example.com --> https://example.com http://www.example.com --> https://example.com https://www.example.com --> https://example.com this how .htaccess file looks like: rewriteengine on rewritecond %{request_filename} !-d rewritecond %{request_filename} !-f rewriterule ^(.*)$ redirect.php?id=$1&page=$2 [qsa,l] what modifications need make .htaccess in order forward https without "www"? it depends on doing current code. looks file called redirect trying display php page seo friendly url. think might confusing people. anyway, need , force https without www, need 1 more rule above. also second rule needs two capture groups in rewriterule test string because wanting 2 different values using $1 , $2 references. rewriteengine on #rediect www non www and/or http https --- combinations. rewritecond %{http_host} !^example\.com [nc,or] rewritecond %{https} !^...
Read more