#!/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