用一小段代码写出平衡二叉树
时间: 2023-10-13 13:12:12 浏览: 32
当然,非常乐意为您解答。以下是一个简单的平衡二叉树的例子,采用 Python 语言实现:
```
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
class AVLTree:
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 rightRotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = max(self.getHeight(y.left), self.getHeight(y.right)) + 1
x.height = max(self.getHeight(x.left), self.getHeight(x.right)) + 1
return x
def leftRotate(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = max(self.getHeight(x.left), self.getHeight(x.right)) + 1
y.height = max(self.getHeight(y.left), self.getHeight(y.right)) + 1
return y
def insert(self, root, val):
if not root:
return Node(val)
elif val < root.val:
root.left = self.insert(root.left, val)
else:
root.right = self.insert(root.right, val)
root.height = max(self.getHeight(root.left), self.getHeight(root.right)) + 1
balance = self.getBalance(root)
if balance > 1 and val < root.left.val:
return self.rightRotate(root)
if balance < -1 and val > root.right.val:
return self.leftRotate(root)
if balance > 1 and val > root.left.val:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balance < -1 and val < root.right.val:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
```
该代码实现了一个平衡二叉树,使用了 AVL 算法来平衡树的结构。可以通过调用 `insert` 方法来插入新节点,并自动维护平衡二叉树的性质。