Вмъкване и завъртане на дърво AVL

Дървото на AVL е подобрена версия на бинарното дърво за търсене (BST), която се самобалансира. Той е кръстен на изобретателите си A delson- V elsky и L andis и е представен за първи път през 1962 г., само две години след проектирането на бинарното дърво за търсене през 1960 г. AVL дървото се счита за първата структура от данни от този тип .

BST е структура от данни, съставена от възли. Той има следните гаранции:

  1. Всяко дърво има корен възел (в горната част).
  2. Коренният възел има нула или повече дъщерни възли.
  3. Всеки дъщерен възел има нула или повече дъщерни възли и т.н.
  4. Всеки възел има до две деца.
  5. За всеки възел неговите леви потомци са по-малко от текущия възел, което е по-малко от десните потомци.

AVL дърветата имат допълнителна гаранция:

  1. Разликата между дълбочината на дясно и ляво поддървета не може да бъде повече от една.

За да се поддържа тази гаранция, внедряванията на AVL дървета включват алгоритъм за ребалансиране на дървото, когато добавянето на допълнителен елемент би довело до разликата в дълбочината между дясното и лявото дървета да бъде по-голяма от една.

AVL дърветата имат най-лошия случай на търсене, вмъкване и изтриване на времето на O (log n).

Право въртене

Ляво завъртане

Процес на въвеждане на AVL

Това работи подобно на нормалното вмъкване на бинарно дърво за търсене. След вмъкването коригирате свойството AVL, като използвате ляво или дясно завъртане.

  • Ако има дисбаланс в лявото дете на дясно поддърво, тогава извършвате въртене наляво-надясно.
  • Ако има дисбаланс в лявото дете на лявото поддърво, тогава правите дясно завъртане.
  • Ако има дисбаланс в дясното дете на дясно поддърво, тогава извършвате ляво завъртане.
  • Ако има дисбаланс в дясното дете на лявото поддърво, тогава извършвате въртене надясно-наляво.

Пример

Ето пример за AVL дърво в Python:

class node: def __init__(self,value=None): self.value=value self.left_child=None self.right_child=None self.parent=None # pointer to parent node in tree self.height=1 # height of node in tree (max dist. to leaf) NEW FOR AVL class AVLTree: def __init__(self): self.root=None def __repr__(self): if self.root==None: return '' # to hold final string cur_nodes=[self.root] # all nodes at current level cur_height=self.root.height # height of nodes at current level*(2**(cur_height-1)) # variable sized separator between elements while True: cur_height+=-1 # decrement current height if len(cur_nodes)==0: break next_nodes=[] if all(n is None for n in cur_nodes): break for n in cur_nodes: if n==None: cur_row+=' '+sep next_row+=' '+sep next_nodes.extend([None,None]) continue if n.value!=None:*int((5-len(str(n.value)))/2) cur_row+='%s%s%s'%(buf,str(n.value),buf)+sep else: cur_row+=' '*5+sep if n.left_child!=None: next_nodes.append(n.left_child) next_row+=' /'+sep else: next_row+=' '+sep next_nodes.append(None) if n.right_child!=None: next_nodes.append(n.right_child) next_row+='\ '+sep else: next_row+=' '+sep next_nodes.append(None) content+=(cur_height*' '+cur_row+'\n'+cur_height*' '+next_row+'\n') cur_nodes=next_nodes*int(len(sep)/2) # cut separator size in half return content def insert(self,value): if self.root==None: self.root=node(value) else: self._insert(value,self.root) def _insert(self,value,cur_node): if valuecur_node.value: if cur_node.right_child==None: cur_node.right_child=node(value) cur_node.right_child.parent=cur_node # set parent self._inspect_insertion(cur_node.right_child) else: self._insert(value,cur_node.right_child) else: print("Value already in tree!") def print_tree(self): if self.root!=None: self._print_tree(self.root) def _print_tree(self,cur_node): if cur_node!=None: self._print_tree(cur_node.left_child) print ('%s, h=%d'%(str(cur_node.value),cur_node.height)) self._print_tree(cur_node.right_child) def height(self): if self.root!=None: return self._height(self.root,0) else: return 0 def _height(self,cur_node,cur_height): if cur_node==None: return cur_height left_height=self._height(cur_node.left_child,cur_height+1) right_height=self._height(cur_node.right_child,cur_height+1) return max(left_height,right_height) def find(self,value): if self.root!=None: return self._find(value,self.root) else: return None def _find(self,value,cur_node): if value==cur_node.value: return cur_node elif valuecur_node.value and cur_node.right_child!=None: return self._find(value,cur_node.right_child) def delete_value(self,value): return self.delete_node(self.find(value)) def delete_node(self,node): ## ----- # Improvements since prior lesson # Protect against deleting a node not found in the tree if node==None or self.find(node.value)==None: print("Node to be deleted not found in the tree!") return None ## ----- # returns the node with min value in tree rooted at input node def min_value_node(n): current=n while current.left_child!=None: current=current.left_child return current # returns the number of children for the specified node def num_children(n): num_children=0 if n.left_child!=None: num_children+=1 if n.right_child!=None: num_children+=1 return num_children # get the parent of the node to be deleted node_parent=node.parent # get the number of children of the node to be deleted node_children=num_children(node) # break operation into different cases based on the # structure of the tree & node to be deleted # CASE 1 (node has no children) if node_children==0: if node_parent!=None: # remove reference to the node from the parent if node_parent.left_child==node: node_parent.left_child=None else: node_parent.right_child=None else: self.root=None # CASE 2 (node has a single child) if node_children==1: # get the single child node if node.left_child!=None: child=node.left_child else: child=node.right_child if node_parent!=None: # replace the node to be deleted with its child if node_parent.left_child==node: node_parent.left_child=child else: node_parent.right_child=child else: self.root=child # correct the parent pointer in node child.parent=node_parent # CASE 3 (node has two children) if node_children==2: # get the inorder successor of the deleted node successor=min_value_node(node.right_child) # copy the inorder successor's value to the node formerly # holding the value we wished to delete node.value=successor.value # delete the inorder successor now that it's value was # copied into the other node self.delete_node(successor) # exit function so we don't call the _inspect_deletion twice return if node_parent!=None: # fix the height of the parent of current node node_parent.height=1+max(self.get_height(node_parent.left_child),self.get_height(node_parent.right_child)) # begin to traverse back up the tree checking if there are # any sections which now invalidate the AVL balance rules self._inspect_deletion(node_parent) def search(self,value): if self.root!=None: return self._search(value,self.root) else: return False def _search(self,value,cur_node): if value==cur_node.value: return True elif valuecur_node.value and cur_node.right_child!=None: return self._search(value,cur_node.right_child) return False # Functions added for AVL... def _inspect_insertion(self,cur_node,path=[]): if cur_node.parent==None: return path=[cur_node]+path left_height =self.get_height(cur_node.parent.left_child) right_height=self.get_height(cur_node.parent.right_child) if abs(left_height-right_height)>1: path=[cur_node.parent]+path self._rebalance_node(path[0],path[1],path[2]) return new_height=1+cur_node.height if new_height>cur_node.parent.height: cur_node.parent.height=new_height self._inspect_insertion(cur_node.parent,path) def _inspect_deletion(self,cur_node): if cur_node==None: return left_height =self.get_height(cur_node.left_child) right_height=self.get_height(cur_node.right_child) if abs(left_height-right_height)>1: y=self.taller_child(cur_node) x=self.taller_child(y) self._rebalance_node(cur_node,y,x) self._inspect_deletion(cur_node.parent) def _rebalance_node(self,z,y,x): if y==z.left_child and x==y.left_child: self._right_rotate(z) elif y==z.left_child and x==y.right_child: self._left_rotate(y) self._right_rotate(z) elif y==z.right_child and x==y.right_child: self._left_rotate(z) elif y==z.right_child and x==y.left_child: self._right_rotate(y) self._left_rotate(z) else: raise Exception('_rebalance_node: z,y,x node configuration not recognized!') def _right_rotate(self,z): sub_root=z.parent y=z.left_child t3=y.right_child y.right_child=z z.parent=y z.left_child=t3 if t3!=None: t3.parent=z y.parent=sub_root if y.parent==None: self.root=y else: if y.parent.left_child==z: y.parent.left_child=y else: y.parent.right_child=y z.height=1+max(self.get_height(z.left_child), self.get_height(z.right_child)) y.height=1+max(self.get_height(y.left_child), self.get_height(y.right_child)) def _left_rotate(self,z): sub_root=z.parent y=z.right_child t2=y.left_child y.left_child=z z.parent=y z.right_child=t2 if t2!=None: t2.parent=z y.parent=sub_root if y.parent==None: self.root=y else: if y.parent.left_child==z: y.parent.left_child=y else: y.parent.right_child=y z.height=1+max(self.get_height(z.left_child), self.get_height(z.right_child)) y.height=1+max(self.get_height(y.left_child), self.get_height(y.right_child)) def get_height(self,cur_node): if cur_node==None: return 0 return cur_node.height def taller_child(self,cur_node): left=self.get_height(cur_node.left_child) right=self.get_height(cur_node.right_child) return cur_node.left_child if left>=right else cur_node.right_child

Повече информация за двоично търсене:

  • Основи на бинарното търсене
  • Бинарни дървета за търсене, обяснени с примери
  • Бинарни структури от данни: въведение в дървета (и купчини)