search
HomeBackend DevelopmentPython TutorialHow to implement avl tree operations in Python

How to implement avl tree operations in Python

Python执行avl树,代码详情:

import sys
#创建树节点
class TreeNode(object):
def __init__(self,key):
self.key=key
self.left=None
self.right=None
self.height=1

class AVLTree(object):
#插入节点
def insert_node(self,root,key):
#找到位置并插入节点
if not root:
return TreeNode(key)
elif key<root.key:
root.left=self.insert_node(root.left,key)
else:
root.right=self.insert_node(root.right,key)
root.height=1+max(self.getHeight(root.left),
self.getHeight(root.right))
#更新节点
balanceFactor=self.getBalance(root)
if balanceFactor>1:
if key<root.left.key:
return self.rightRotate(root)
else:
root.left=self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor<-1:
if key>root.right.key:
return self.leftRotate(root)
else:
root.right=self.rightRotate(root.right)
return self.leftRotate(root)
return root
#删除节点
def delete_node(self,root,key):
#找到要删除的节点并删除
if not root:
return root
elif key<root.key:
root.left=self.delete_node(root.left,key)
elif key>root.key:
root.right=self.delete_node(root.right,key)
else:
if root.left is None:
temp=root.right
root=None
return temp
elif root.right is None:
temp=root.left
root=None
return temp
temp=self.getMinValueNode(root.right)
root.key=temp.key
root.right=self.delete_node(root.right,
temp.key)
if root is None:
return root
#更新节点
root.height=1+max(self.getHeight(root.left),
self.getHeight(root.right))
balanceFactor=self.getBalance(root)
#平衡树
if balanceFactor>1:
if self.getBalance(root.left)>=0:
return self.rightRotate(root)
else:
root.left=self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor<-1:
if self.getBalance(root.right)<=0:
return self.leftRotate(root)
else:
root.right=self.rightRotate(root.right)
return self.leftRotate(root)
return root
#左旋转
def leftRotate(self,z):
y=z.right
T2=y.left
y.left=z
z.right=T2
z.height=1+max(self.getHeight(z.left),
self.getHeight(z.right))
y.height=1+max(self.getHeight(y.left),
self.getHeight(y.right))
return y
#右旋转
def rightRotate(self,z):
y=z.left
T3=y.right
y.right=z
z.left=T3
z.height=1+max(self.getHeight(z.left),
self.getHeight(z.right))
y.height=1+max(self.getHeight(y.left),
self.getHeight(y.right))
return y
#获取节点高度
def getHeight(self,root):
if not root:
return 0
return root.height
#平衡节点
def getBalance(self,root):
if not root:
return 0
return self.getHeight(root.left)-self.getHeight(root.right)
def getMinValueNode(self,root):
if root is None or root.left is None:
return root
return self.getMinValueNode(root.left)
def preOrder(self,root):
if not root:
return
print("{0}".format(root.key),end="")
self.preOrder(root.left)
self.preOrder(root.right)
#输出avl树
def printHelper(self,currPtr,indent,last):
if currPtr!=None:
sys.stdout.write(indent)
if last:
sys.stdout.write("R----")
indent+=""
else:
sys.stdout.write("L----")
indent+="|"
print(currPtr.key)
self.printHelper(currPtr.left,indent,False)
self.printHelper(currPtr.right,indent,True)
myTree=AVLTree()
root=None
nums=[33,13,52,9,21,61,8,11]
for num in nums:
root=myTree.insert_node(root,num)
myTree.printHelper(root,"",True)
key=13
root=myTree.delete_node(root,key)
print("After Deletion:")
myTree.printHelper(root,"",True)

The above is the detailed content of How to implement avl tree operations in Python. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:网易伏羲. If there is any infringement, please contact admin@php.cn delete
Python vs. C  : Understanding the Key DifferencesPython vs. C : Understanding the Key DifferencesApr 21, 2025 am 12:18 AM

Python and C each have their own advantages, and the choice should be based on project requirements. 1) Python is suitable for rapid development and data processing due to its concise syntax and dynamic typing. 2)C is suitable for high performance and system programming due to its static typing and manual memory management.

Python vs. C  : Which Language to Choose for Your Project?Python vs. C : Which Language to Choose for Your Project?Apr 21, 2025 am 12:17 AM

Choosing Python or C depends on project requirements: 1) If you need rapid development, data processing and prototype design, choose Python; 2) If you need high performance, low latency and close hardware control, choose C.

Reaching Your Python Goals: The Power of 2 Hours DailyReaching Your Python Goals: The Power of 2 Hours DailyApr 20, 2025 am 12:21 AM

By investing 2 hours of Python learning every day, you can effectively improve your programming skills. 1. Learn new knowledge: read documents or watch tutorials. 2. Practice: Write code and complete exercises. 3. Review: Consolidate the content you have learned. 4. Project practice: Apply what you have learned in actual projects. Such a structured learning plan can help you systematically master Python and achieve career goals.

Maximizing 2 Hours: Effective Python Learning StrategiesMaximizing 2 Hours: Effective Python Learning StrategiesApr 20, 2025 am 12:20 AM

Methods to learn Python efficiently within two hours include: 1. Review the basic knowledge and ensure that you are familiar with Python installation and basic syntax; 2. Understand the core concepts of Python, such as variables, lists, functions, etc.; 3. Master basic and advanced usage by using examples; 4. Learn common errors and debugging techniques; 5. Apply performance optimization and best practices, such as using list comprehensions and following the PEP8 style guide.

Choosing Between Python and C  : The Right Language for YouChoosing Between Python and C : The Right Language for YouApr 20, 2025 am 12:20 AM

Python is suitable for beginners and data science, and C is suitable for system programming and game development. 1. Python is simple and easy to use, suitable for data science and web development. 2.C provides high performance and control, suitable for game development and system programming. The choice should be based on project needs and personal interests.

Python vs. C  : A Comparative Analysis of Programming LanguagesPython vs. C : A Comparative Analysis of Programming LanguagesApr 20, 2025 am 12:14 AM

Python is more suitable for data science and rapid development, while C is more suitable for high performance and system programming. 1. Python syntax is concise and easy to learn, suitable for data processing and scientific computing. 2.C has complex syntax but excellent performance and is often used in game development and system programming.

2 Hours a Day: The Potential of Python Learning2 Hours a Day: The Potential of Python LearningApr 20, 2025 am 12:14 AM

It is feasible to invest two hours a day to learn Python. 1. Learn new knowledge: Learn new concepts in one hour, such as lists and dictionaries. 2. Practice and exercises: Use one hour to perform programming exercises, such as writing small programs. Through reasonable planning and perseverance, you can master the core concepts of Python in a short time.

Python vs. C  : Learning Curves and Ease of UsePython vs. C : Learning Curves and Ease of UseApr 19, 2025 am 12:20 AM

Python is easier to learn and use, while C is more powerful but complex. 1. Python syntax is concise and suitable for beginners. Dynamic typing and automatic memory management make it easy to use, but may cause runtime errors. 2.C provides low-level control and advanced features, suitable for high-performance applications, but has a high learning threshold and requires manual memory and type safety management.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!