Red Black Tree (Python)
From LiteratePrograms
- Other implementations: Java | Python
This program is a code dump.
Code dumps are articles with little or no documentation or rearrangement of code. Please help to turn it into a literate program. Also make sure that the source of this code does consent to release it under the MIT or public domain license.
class Node(): def __init__(self, arg0, Parent=None, Left=None, Right=None): self.red=True self.value=arg0 self.parent=Parent self.left=Left self.right=Right def isred(self): return self.red def getParent(self): return self.parent def getGrandParent(self): if self.parent is None: return None return self.parent.parent def __eq__(self,Node2): if Node2 is None: return False return self.value == Node2.value def getUncle(self): if self.getGrandParent() is not None: if self.getParent() == self.getGrandParent().left: return self.getGrandParent().right return self.getGrandParent().left return None def isredstr(self): if self.red: return "red" return "black" def sb(self): self.red=False def sr(self): self.red=True def isLeft(self): if self.parent is None: return None if self.parent.left is not None: return self.parent.left.value == self.value return False class RBTree(): def __init__(self): self.root=None def add(self, value): if self.root is None: self.root=Node(value) self.root.sb() return self._add(value, self.root) def _add(self, value, Node2=None): if Node2.value > value: # add to the left if Node2.left is None: tmp = Node(value, Parent=Node2) Node2.left=tmp self.rebalance(tmp) else: self._add( value, Node2.left) elif Node2.value < value: # add to the right if Node2.right is None: tmp = Node(value, Parent=Node2) Node2.right=tmp self.rebalance(tmp) else: self._add( value, Node2.right) else: print( "Duplicate value found") def rebalance(self, Node2): if Node2.parent is None: Node2.sb() return if not Node2.parent.isred(): return if Node2.getUncle() is not None and Node2.getUncle().isred(): Node2.getUncle().red=False Node2.parent.red=False self.rebalance( Node2.getGrandParent()) return self.pivotandrebalance(Node2) def pivotandrebalance(self, arg0): if arg0.isLeft(): if arg0.parent.isLeft(): # left left -> False pivot around parent self.pivotRight(arg0.parent, False) else: self.pivotLeft(arg0, True) else: # right if arg0.parent.isLeft(): self.pivotRight(arg0, True) else: # right right -> False pivot around parent self.pivotLeft(arg0.parent, False) def pivotLeft(self, arg0, Pivot=False): M=arg0 G=M.parent if Pivot: N=M.parent G=N.parent G.right=M M.parent=G N.left=M.right if M.right is not None: M.right.parent=N M.right=N N.parent=M K=G.parent X=G.isLeft() G.right=M.left if G.right is not None: G.right.parent=G M.left=G G.parent=M G.sr() M.sb() if K is None: M.parent=None self.root=M elif K is not None and X: M.parent=K K.left=M K.sr() self.rebalance(K) else: M.parent=K K.right=M K.sr() self.rebalance(K) def pivotRight(self, arg0, Pivot=False): M=arg0 G=M.parent if Pivot: N=M.parent G=N.parent N.right=M.left if M.left is not None: N.right.parent=N G.left=M M.parent=G M.left=N N.parent=M K=G.parent X=G.isLeft() G.left=M.right if M.right is not None: M.right.parent=G M.right=G G.parent=M G.sr() M.sb() if K is None: M.parent=None self.root=M elif K is not None and X: M.parent=K K.left=M K.sr() self.rebalance(K) else: M.parent=K K.right=M K.sr() self.rebalance(K) def printtree(self, arg0=None): node=arg0 if arg0 is None: node=self.root if node.left is not None: self.printtree(node.left) print "%s (%s) -> " % ( node.value, node.isredstr()) if node.right is not None: self.printtree(node.right) rbtree=RBTree() rbtree.add(10) rbtree.add(20) rbtree.add(30) rbtree.add(40) rbtree.add(10) rbtree.add(50) rbtree.add(60) rbtree.add(70) rbtree.add(80) rbtree.add(90) rbtree.printtree()
| Download code |