Вставка та обертання дерева AVL

Дерево AVL - це вдосконалена версія бінарного дерева пошуку (BST), що самобалансується. Він був названий в честь його винахідників A delson- V elsky і L Andis, і був вперше введений в 1962 році, всього через два роки після того, як дизайн двійкового дерева пошуку в 1960. Авла дерево вважаються першою структурою даних його типу .

BST - це структура даних, що складається з вузлів. Він має такі гарантії:

  1. Кожне дерево має кореневий вузол (вгорі).
  2. Кореневий вузол має нуль або більше дочірніх вузлів.
  3. Кожен дочірній вузол має нуль або більше дочірніх вузлів тощо.
  4. Кожен вузол має до двох дітей.
  5. Для кожного вузла його ліві нащадки менше, ніж поточний вузол, що менше, ніж праві нащадки.

Дерева AVL мають додаткову гарантію:

  1. Різниця між глибиною правого та лівого піддерев не може бути більше одного.

Для того, щоб зберегти цю гарантію, реалізації дерев AVL включають алгоритм для збалансування дерева, коли додавання додаткового елемента призведе до того, що різниця в глибині між правим і лівим деревами буде більшою за одиницю.

Дерева AVL мають найгірший варіант пошуку, вставки та видалення часу O (журнал 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

Більше інформації про двійковий пошук:

  • Основи двійкового пошуку
  • Бінарні дерева пошуку пояснені на прикладах
  • Бінарні структури даних: вступ до дерев (і купи)