AVL Tree
| EN | CN |
Tree
In computer science, trees (English: Tree ) is an abstract data type (ADT) or implement this abstract data types of data structures , to simulate having a structure in tree-like nature of the data set. It is composed of n (n> 0) finite nodes having a hierarchical relationship set . It is called a “tree” because it looks like an upside down tree, that is, it has its roots facing up and leaves facing down. It has the following characteristics:
Each node has only a limited number of child nodes or no child nodes; Nodes without parent nodes are called root nodes; Each non-root node has only one parent node; In addition to the root node, each child node can be divided into multiple disjoint subtrees; There is no cycle in the tree
- Node degree : the number of subtrees contained in a node is called the node degree;
- The degree of the tree: in a tree, the largest node degree is called the degree of the tree;
- Leaf node or terminal node : a node with a degree of zero;
- Non-terminal nodes or branch nodes : nodes whose degree is not zero;
- Father node or parent node : If a node contains child nodes, this node is called the parent node of its child nodes;
- Child node or child node : the root node of the subtree contained in a node is called the child node of the node;
- Brother nodes : Nodes with the same parent node are called brother nodes;
- Node level : starting from the root, the root is the first layer, the children of the root are the second layer, and so on;
- Depth : For any node n, the depth of n is the only path length from root to n, and the depth of root is 0;
- Height : For any node n, the height of n is the longest path from n to a leaf, and the height of all leaves is 0;
- Cousin node : the nodes whose parent nodes are on the same layer are cousins of each other;
- The ancestor of a node : from the root to all the nodes on the branch that the node passes through;
- Sons : a node in the subtree rooted at a node referred to in any of the descendant node.
- Forest : a collection of m (m> = 0) disjoint trees is called a forest;
Clasify
- Unordered tree: There is no order relationship between the children of any node in the tree. This kind of tree is called an unordered tree, also known as a free tree ;
- Ordered tree: There is an order relationship between the child nodes of any node in the tree. This kind of tree is called an ordered tree;
- Binary tree : a tree with up to two subtrees per node is called a binary tree;
- Complete binary tree : For a binary tree, assume its depth is d (d> 1). Except for layer d, the number of nodes in other layers has reached the maximum value, and all nodes in layer d are closely arranged continuously from left to right. Such a binary tree is called a complete binary tree;
- Full binary tree : a complete binary tree with all leaf nodes at the bottom;
- Sorted binary tree ( binary search tree (English: Binary Search Tree)): also known as binary search tree, ordered binary tree;
- Huffman tree : The binary tree with the shortest weighted path is called Huffman tree or optimal binary tree;
- B-tree : A self-balancing binary search tree optimized for read and write operations, capable of keeping data in order and having more than two subtrees.
- Balanced binary tree ( AVL tree ): a binary tree if and only if the height difference between the two subtrees of any node is not greater than 1;
AVL Tree
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented.In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper “An algorithm for the organization of information”.
AVL trees are often compared with red–black trees because both support the same set of operations and take O(log n) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced.Similar to red–black trees, AVL trees are height-balanced. Both are, in general, neither weight-balanced nor \mu -balanced for any {\displaystyle \mu \leq {\tfrac {1}{2}}}; that is, sibling nodes can have hugely differing numbers of descendants.
TreeNode and minTree
class TreeNode():
def __init__(self, x):
self.value = x
self.left = None #left node
self.right = None #right node
self.parent = None #parent node
self.height = 1 #default height = 1
class of AVL Tree
class AVLTree():
def __init__(self):
self.root = None#root node
Tree Height
def __height(self, root):
if not root:
return 0#这里默认空节点高度为0
return root.height
def get_height(self):
return __height(self.root)#return height tree
Balance
def __balance(self, root):
'''return the height of right subtree and left subtree'''
if not root:
return 0
else:
return self.__height(root.left) - self.__height(root.right)
def get_balance(self):
'''return the balance'''
return self.__balance(self.root)
Minnode and Maxnode
def __minNode(self, root):
'''return minnode'''
if root.left:
return __minNode(root.left)
else:
return root
def get_minNode(self):
if not self.root:
return None
return self.__minNode(self.root)
def __maxNode(self, root):
'''return max node'''
if root.right:
return __maxNode(root.right)
else:
return root
def get_maxNode(self):
if not self.root:
return None
else:
return self.__maxNode(self.root)
Rotate case
rotate the subtree to reach balance < 2
a) Left Left Case
z y
/ \ / \
y T4 right_rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
============================================================================
b) Left Right Case
z z x
/ \ / \ / \
y T4 left_rotate (y) x T4 right_rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
============================================================================
c) Right Right Case
z y
/ \ / \
T1 y left_rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
============================================================================
d) Right Left Case
z z x
/ \ / \ / \
T1 y right_rotate (y) T1 x left_rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
A: LL
a) Left Left Case
z y
/ \ / \
y T4 right_rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
def right_rotate(self, root):
'''LL'''
y = root.left
T3 = y.right
#rotate
y.right = root
root.left = T3
#update height
y.height = max(self.__height(y.left) - self.__height(y.right)) + 1
root.height = max(self.__height(root.left) - self.__height(root.right)) + 1
#update parent
y.parent = None
T3.parent = root
#return root of tree
return y
C: RR
c) Right Right Case
z y
/ \ / \
T1 y left_rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
def left_rotate(self, root):
'''RR'''
y = root.right
T2 = y.left
#rotate
y.right = root
root.left = T2
#update height
y.height = max(self.__height(y.left) - self.__height(y.right)) + 1
root.height = max(self.__height(root.left) - self.__height(root.right)) + 1
#update parent
y.parent = None
T2.parent = root
#return root of tree
return y
D: RL
d) Right Left Case
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
LL,RR
def RL(self, root):
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
B: LR
b) Left Right Case
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
RR, LL
def RL(self, root):
root.left = self.right_rotate(root.left)
return self.left_rotate(root)
Start Balance
def balance_Tree(self, root, x):
'''rotate tree according to compare x with node's value'''
balance = self.__balance(root)
if balance > 1:
#如果大于1 说明左子树高度大于右子树
if x < root.left.value:
#LL
return self.right_rotate(root)
else:
return self.LR(root)
if balance < -1:
#说明右子树高度大于左子树高度,右子树节点过多
if x > root.right.value:
return self.left_rotate(root)
else:
return self.RL(root)
Add/Update/Delete/Search
add()
def add(self, root, x):
'''value of left less than right'''
if not self.root:
self.root = TreeNode(x)
else:
node = self.root
while node:
#update height
node.height = max(self.__height(node.left) - self.__height(node.right)) + 1
if node.value > x:
if not node.left:
#if node.left is none, insert x
node.left = TreeNode(x)
node.left.parent = node
else:
node = node.left
else:
if not node.right:
#if node.right is none, insert x
node.right = TreeNode(x)
node.right.parent = node
balance_x = abs(self.get_balance(self.root))
if balance_x >= 2:
root = self.balance_Tree(self.root, x)
return root
update()
def __upate(self, root, x0, x):
if not root:
print("We have not searched this node, so we can't update it")
else:
if x0 < root.value:
root.left = self.__update(root.left, x0, x)
elif x0 > root.value:
root.right = self.__update(root.right, x0, x)
else:
root.value = x
return root
def update(self, x0, x):
'''
x0: Original value
x: New value
'''
if not self.root:
return None
return __update(self.root, x0, x)
delete()
def __delete(self, root, x):
'''Recursively find and then delete and keep the tree balanced'''
if not root:
print("We have not searched this node, so we can't delete it")
else:
if x < root.value:
root.left = self.__delete(root.left, x)
elif x > root.value:
root.right = self.__delete(root.right, x)
else:
print("The deleted value is {}, its height is {}, its parent is {}".format(root.value, root.height, root.parent.value))
if not root.left or not root.right:
#only one or none node
if not root.left:
#have right node
root = root.right
elif not root.right:
root = root.left
else:
root = None
else:
#two chrild nodes
minNode = self.__minNode(root.right)
root.value = minNode.value
#delete the minNode
root.right = self.__delete(root.right, root.value)
print("Delete success!")
if root:
print("The replaced value is {}".format(root.value))
else:
print None
balance_x = abs(self.get_balance(self.root))
if balance_x >= 2:
self.balance_Tree(self.root)
return root
def delete(self, x):
return self.__delete(self.root, x)
search()
def search(self, x):
if not self.root:
return None
else:
node = self.root
while node != None:
if x < node.value:
node = node.left
elif x > node.value:
node = node.right
else:
print("The node's value is {}\nThe height is {}\nIts parent is {}".format(node.value, node,height, node.parent.value))
return node
AVL Tree Traversal
Deep-first search
def DFS(self):
'''stack'''
if not self.root:
return None
else:
stack = []
stack.append(self.root)
while len(stack) > 0:
node = stack.pop()
print node.value,
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
Breadth-first search
def BFS(self):
'''use queue'''
if not self.root:
return None
else:
queue = []
queue.append(self.root)
while len(queue) > 0:
node = queue.pop(0)
print node.value,
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
Preorder Traversal
def Preorder_tree(self, root):
if root:
print(root.value)
Preorder_tree(root.left)
Preorder_tree(root.right)
Inorder Traversal
def Inorder_tree(self, root):
if root:
Inorder_tree(root.left)
print(root.value)
Inorder_tree(root.right)
Postorder Traversal
def Postorder_tree(self, root):
if root:
Postorder_tree(root.left)
Postorder_tree(root.right)
print(root.value)
Source code
平衡二叉树
什么是树
在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点都只有有限个子节点或无子节点； 没有父节点的节点称为根节点； 每一个非根节点有且只有一个父节点； 除了根节点外，每个子节点可以分为多个不相交的子树； 树里面没有环路(cycle)
树的关键词
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
- 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0或1；
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m>=0）棵互不相交的树的集合称为森林；
树的种类
- 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
- 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
- 二叉树：每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
- 满二叉树：所有叶节点都在最底层的完全二叉树；
- 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
- 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；
- 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
- B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。
- 红黑树
树的表示
列表式
递归式
平衡二叉树
在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log {n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
步骤
假设平衡因子是左子树的高度减去右子树的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行的规律可归纳为下列四种情况：
- 单向右旋平衡处理LL：由于在a的左子树根节点的左子树上插入节点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行一次右旋转操作；
- 单向左旋平衡处理RR：由于在a的右子树根节点的右子树上插入节点，a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
- 双向旋转（先左后右）平衡处理LR：由于在a的左子树根节点的右子树上插入节点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
- 双向旋转（先右后左）平衡处理RL：由于在a的右子树根节点的左子树上插入节点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。
在平衡的二叉排序树BBST (Balancing Binary Search Tree)上插入一个新的数据元素e的递归算法可描述如下：
- 若BBST为空树，则插入一个数据元素为e的新节点作为BBST的根节点，树的深度增1；
- 若e的关键字和BBST的根节点的关键字相等，则不进行；
- 若e的关键字小于BBST的根节点的关键字，而且在BBST的左子树中不存在和e有相同关键字的节点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：
- BBST的根节点的平衡因子为-1（右子树的深度大于左子树的深度，则将根节点的平衡因子更改为0，BBST的深度不变；
- BBST的根节点的平衡因子为0（左、右子树的深度相等）：则将根节点的平衡因子更改为1，BBST的深度增1；
- BBST的根节点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根节点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；
- 若e的关键字大于BBST的根节点的关键字，而且在BBST的右子树中不存在和e有相同关键字的节点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之
定义子节点(最小树)
class TreeNode():
def __init__(self, x):
self.value = x
self.left = None #左节点
self.right = None #右节点
self.parent = None #父节点
self.height = 1 #高度默认为1
定义一个AVLtree类
class AVLTree():
def __init__(self):
self.root = None#根节点
获取节点和树高度
def __height(self, root):
if not root:
return 0#这里默认空节点高度为0
return root.height
def get_height(self):
return __height(self.root)#从根节点开始获取整个树的高度
获取平衡二叉树的平衡因子
def __balance(self, root):
'''返回左节点高度和右节点高度的差值'''
if not root:
return 0
else:
return self.__height(root.left) - self.__height(root.right)
def get_balance(self):
'''返回整棵树的平衡性'''
return self.__balance(self.root)
查找最小左节点和最大右节点
def __minNode(self, root):
'''返回最左边的节点'''
if root.left:
return __minNode(root.left)
else:
return root
def get_minNode(self):
if not self.root:
return None
return self.__minNode(self.root)
def __maxNode(self, root):
'''返回最右边的节点'''
if root.right:
return __maxNode(root.right)
else:
return root
def get_maxNode(self):
if not self.root:
return None
else:
return self.__maxNode(self.root)
平衡二叉树的调整
调整情况
调整二叉树使它们达到整棵树的平衡
a) Left Left Case
z y
/ \ / \
y T4 right_rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
============================================================================
b) Left Right Case
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
============================================================================
c) Right Right Case
z y
/ \ / \
T1 y left_rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
============================================================================
d) Right Left Case
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
案例a: LL
a) Left Left Case
z y
/ \ / \
y T4 right_rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
只需要把根节点z向右旋转,把左节点y变成根节点,把叶节点T3放在z的左节点上达到平衡
def right_rotate(self, root):
'''LL'''
y = root.left
T3 = y.right
#开始旋转
y.right = root
root.left = T3
#更新节点高度
y.height = max(self.__height(y.left) - self.__height(y.right)) + 1
root.height = max(self.__height(root.left) - self.__height(root.right)) + 1
#更新节点所属的父节点
y.parent = None
T3.parent = root
#返回新的根节点
return y
案例c: RR
c) Right Right Case
z y
/ \ / \
T1 y left_rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
只需要把根节点z往左旋转,y成为根节点,T2放在z的右节点上
def left_rotate(self, root):
'''RR'''
y = root.right
T2 = y.left
#开始旋转
y.right = root
root.left = T2
#更新高度
y.height = max(self.__height(y.left) - self.__height(y.right)) + 1
root.height = max(self.__height(root.left) - self.__height(root.right)) + 1
#更新节点所属的父节点
y.parent = None
T2.parent = root
#返回新的根节点
return y
案例d: RL
d) Right Left Case
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
先向右旋转在向左旋转
def RL(self, root):
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
案例b: LR
b) Left Right Case
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
先向左旋转RR后向右旋转LL
def RL(self, root):
root.left = self.right_rotate(root.left)
return self.left_rotate(root)
开始调整
def balance_Tree(self, root, x):
'''根据插入的x值判断它插入的是左子树还是右子树进行调整'''
balance = self.__balance(root)
if balance > 1:
#如果大于1 说明左子树高度大于右子树
if x < root.left.value:
#LL
return self.right_rotate(root)
else:
return self.LR(root)
if balance < -1:
#说明右子树高度大于左子树高度,右子树节点过多
if x > root.right.value:
return self.left_rotate(root)
else:
return self.RL(root)
ALV树的增改删查询
增加add()
def add(self, root, x):
'''左节点值小于右节点值'''
if not self.root:
self.root = TreeNode(x)
else:
node = self.root
while node:
#返回节点高度
node.height = max(self.__height(node.left) - self.__height(node.right)) + 1
if node.value > x:
if not node.left:
#如果左节点为空,插入x
node.left = TreeNode(x)
node.left.parent = node
else:
node = node.left
else:
if not node.right:
#如果右节点为空,插入x
node.right = TreeNode(x)
node.right.parent = node
balance_x = abs(self.get_balance(self.root))
if balance_x >= 2:
#破坏了树的平衡
root = self.balance_Tree(self.root, x)
return root
修改update()
def __upate(self, root, x0, x):
if not root:
print("We have not searched this node, so we can't update it")
else:
if x0 < root.value:
root.left = self.__update(root.left, x0, x)
elif x0 > root.value:
root.right = self.__update(root.right, x0, x)
else:
root.value = x
return root
def update(self, x0, x):
'''
x0: 查找值
x: 修改x0为x的值
'''
if not self.root:
return None
return __update(self.root, x0, x)
删除delete()
def __delete(self, root, x):
'''递归查找然后删除并保持树的平衡性'''
if not root:
print("We have not searched this node, so we can't delete it")
else:
if x < root.value:
root.left = self.__delete(root.left, x)
elif x > root.value:
root.right = self.__delete(root.right, x)
else:
print("The deleted value is {}, its height is {}, its parent is {}".format(root.value, root.height, root.parent.value))
if not root.left or not root.right:
#如果待删除节点只有一个或没有子节点
if not root.left:
#有一个右节点
root = root.right
elif not root.right:
root = root.left
else:
root = None
else:
#有双子节点,查找最小右节点
minNode = self.__minNode(root.right)
root.value = minNode.value
#删除去替换x的节点
root.right = self.__delete(root.right, root.value)
print("Delete success!")
if root:
print("The replaced value is {}".format(root.value))
else:
print None
balance_x = abs(self.get_balance(self.root))
if balance_x >= 2:
self.balance_Tree(self.root)
return root
def delete(self, x):
return self.__delete(self.root, x)
查询search()
def search(self, x):
if not self.root:
return None
else:
node = self.root
while node != None:
if x < node.value:
node = node.left
elif x > node.value:
node = node.right
else:
print("The node's value is {}\nThe height is {}\nIts parent is {}".format(node.value, node,height, node.parent.value))
return node
AVL树的遍历
深度优先遍历
def DFS(self):
'''通过栈的方式遍历整棵树'''
if not self.root:
return None
else:
stack = []
stack.append(self.root)
while len(stack) > 0:
node = stack.pop()
print node.value,
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
广度优先(层次)遍历
def BFS(self):
'''通过队列遍历树'''
if not self.root:
return None
else:
queue = []
queue.append(self.root)
while len(queue) > 0:
node = queue.pop(0)
print node.value,
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
前序遍历
def Preorder_tree(self, root):
if root:
print(root.value)
Preorder_tree(root.left)
Preorder_tree(root.right)
中序遍历
def Inorder_tree(self, root):
if root:
Inorder_tree(root.left)
print(root.value)
Inorder_tree(root.right)
后序遍历
def Postorder_tree(self, root):
if root:
Postorder_tree(root.left)
Postorder_tree(root.right)
print(root.value)