Einfügen und Drehen von AVL-Bäumen

Ein AVL-Baum ist eine verbesserte Version des binären Suchbaums (BST), der sich selbst ausgleicht. Es wurde nach seinen Erfindern A delson- V elsky und L andis benannt und 1962, nur zwei Jahre nach dem Entwurf des binären Suchbaums 1960, erstmals eingeführt. Der AVL-Baum gilt als die erste Datenstruktur dieser Art .

Eine BST ist eine Datenstruktur, die aus Knoten besteht. Es hat folgende Garantien:

  1. Jeder Baum hat einen Wurzelknoten (oben).
  2. Der Wurzelknoten hat null oder mehr untergeordnete Knoten.
  3. Jeder untergeordnete Knoten hat null oder mehr untergeordnete Knoten usw.
  4. Jeder Knoten hat bis zu zwei Kinder.
  5. Für jeden Knoten sind seine linken Nachkommen kleiner als der aktuelle Knoten, was weniger als die rechten Nachkommen ist.

AVL-Bäume haben eine zusätzliche Garantie:

  1. Der Unterschied zwischen der Tiefe der rechten und linken Teilbäume kann nicht mehr als eins betragen.

Um diese Garantie aufrechtzuerhalten, enthalten Implementierungen von AVL-Bäumen einen Algorithmus zum Neuausgleichen des Baums, wenn ein zusätzliches Element hinzugefügt wird, wodurch der Tiefenunterschied zwischen dem rechten und dem linken Baum größer als eins wird.

AVL-Bäume haben eine Worst-Case-Such-, Einfüge- und Löschzeit von O (log n).

Rechtsdrehung

Linksdrehung

AVL-Einfügungsprozess

Dies funktioniert ähnlich wie beim normalen Einfügen eines binären Suchbaums. Nach dem Einfügen korrigieren Sie die AVL-Eigenschaft mithilfe von Links- oder Rechtsdrehungen.

  • Wenn das linke Kind des rechten Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Rotation von links nach rechts durch.
  • Wenn das linke Kind des linken Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Rechtsdrehung durch.
  • Wenn das rechte Kind des rechten Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Linksdrehung durch.
  • Wenn das rechte Kind des linken Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Rotation von rechts nach links durch.

Beispiel

Hier ist ein Beispiel für einen AVL-Baum in 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

Weitere Informationen zur binären Suche:

  • Grundlagen der binären Suche
  • Mit Beispielen erläuterte binäre Suchbäume
  • Binäre Datenstrukturen: Einführung in Bäume (und Haufen)