节点大小平衡树（Size Balanced Tree c++和python源码

我自己写的SBTree的实现 参考了http://www.nocow.cn/index.php/Size_Balanced_Tree的算法 声明：此源码可以用于商业用途，但请注明来源于random

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
#===============================================================================
# Size Balanced Tree
# 节点大小平衡二叉树
# Author: Random
#===============================================================================
import random
		
class NoType（object）:
	def __init__（self）:
		pass
	def __str__（self）:
		return “-“
	
noType = NoType（）

class SBTNode（object）:
	def __init__（self key value）:
		self.size = 0
		self.key = key
		self.value = value
		self.left = None
		self.right = None
		
	def __str__（self）:
		return “%s %s“%（self.key self.size）

# ------------------------------
# 模拟c++中的引用		
class LeftRef（object）:
	def __init__（self parent）:
		self.parent = parent
		
	def Get（self）:
		return self.parent.left
	
	def Set（self node）:
		self.parent.left = node
		
class RightRef（object）:
	def __init__（self parent）:
		self.parent = parent
		
	def Get（self）:
		return self.parent.right
	
	def Set（self node）:
		self.parent.right = node
		
class RootRef（object）:
	def __init__（self t）:
		self.t = t
		
	def Get（self）:
		return self.t.root
	
	def Set（self node）:
		self.t.root = node

# --------------------------------

class SBTTree（object）:
	def __init__（self）:
		self.root = None
			
	def __S（self node）:
		if node:
			return node.size
		return 0
	
	def Print（self）:
		self.sbt_print（self.root 0）
	
	def sbt_print（self node uHeight = 0）:
		if not node:
			return
		self.sbt_print（node.left uHeight + 1）
		print “	“*uHeight node
		self.sbt_print（node.right uHeight + 1）
	
	def __LeftRotate（self refNode）:
		‘‘‘
		左旋右节点一定存在
		  A             C
		    C  ->     A
		   D           D
		‘‘‘
		A = refNode.Get（）
		C = A.right
		A.right = C.left
		C.left = A
		C.size = A.size
		A.size = self.__S（A.left） + self.__S（A.right） + 1
		refNode.Set（C）
		
	def __RightRotate（self refNode）:
		‘‘‘
		右旋
		    A         B
		  B      ->     A
		   D           D
		@param node:
		‘‘‘
		A = refNode.Get（）
		B = A.left
		A.left = B.right
		B.right = A
		B.size = A.size
		A.size = self.__S（A.left） + self.__S（A.right） + 1
		refNode.Set（B）
		
	def MainTain（self refNode isRightDeeper）:
		‘‘‘
		主要的逻辑处理
		@param node:
		‘‘‘
		node = refNode.Get（）
		if not node:
			return
		# 节点判断是否平衡
		if not isRightDeeper:
			# step1 左节点是否是空的
			if not node.left:
				return
			rs = self.__S（node.right）
			if self.__S（node.left.left） > rs:
				# step2 如果是左左>右，则右旋
				self.__RightRotate（refNode）
			elif self.__S（node.left.right） > rs:
				# step3 如果是左右>右，则左子节点左旋，节点右旋
				self.__LeftRotate（LeftRef（node））
				self.__RightRotate（refNode）
			else:
				return
		else:
			# step1 右节点是否位空的
			if not node.right:
				return
			ls = self.__S（node.left）
			if self.__S（node.right.right） > ls:
				self.__LeftRotate（refNode）
			elif self.__S（node.right.left） > ls:
				self.__RightRotate（RightRef（node））
				self.__LeftRotate（refNode）
	

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-02-26 15:26  SBTree\
     文件       13830  2014-02-26 14:58  SBTree\SBTree.h
     文件        8257  2014-02-26 15:11  SBTree\SBTree.py