Pengenalan pokok AVL
Mencari pokok binari mempunyai kecekapan carian yang sangat tinggi, tetapi mencari pokok binari akan mengakibatkan situasi melampau berikut:
Seperti ini Kecekapan carian pokok binari adalah lebih rendah daripada senarai terpaut. Pokok binari seimbang (pokok AVL) yang muncul berdasarkan pokok binari carian menyelesaikan masalah ini. Apabila nilai mutlak perbezaan ketinggian antara subpokok kiri dan kanan nod dalam pokok binari seimbang (pokok AVL) lebih besar daripada 1, perbezaan ketinggian mereka akan dikurangkan melalui operasi putaran.
Konsep asas
Pokok AVL pada asasnya ialah pepohon carian binari ialah:
itu sendiri adalah yang pertama
二叉搜索树
.高度之差的绝对值(平衡因子)最多为1
subpokok kiri dan kanan setiap nod. Dalam erti kata lain, pokok AVL pada dasarnya ialah pokok carian binari dengan平衡功能
(pokok pengisihan binari, pokok carian binari).Apabila memasukkan nod atau memadamkan nod, menyebabkan nilai mutlak perbezaan ketinggian antara subpokok kiri dan kanan nod menjadi lebih besar daripada 1, anda perlu melepasi
左旋
dan右旋
Operasi membawa pokok binari kepada keseimbangan semula.
Faktor Imbangan (balanceFactor)
Subpokok kiri dan subpokok kanan nod
高度之差
.BF mana-mana nod dalam pepohon AVL hanya boleh
-1,0和1。
Reka bentuk asas
Berikut ialah AVL Kaedah dan atribut mudah yang diperlukan oleh pokok:
public class AVLTree <E extends Comparable<E>>{ class Node{ E value; Node left; Node right; int height; public Node(){} public Node(E value){ this.value = value; height = 1; left = null; right = null; } public void display(){ System.out.print(this.value + " "); } } Node root; int size; public int size(){ return size; } public int getHeight(Node node) { if(node == null) return 0; return node.height; } //获取平衡因子(左右子树的高度差,大小为1或者0是平衡的,大小大于1不平衡) public int getBalanceFactor(){ return getBalanceFactor(root); } public int getBalanceFactor(Node node){ if(node == null) return 0; return getHeight(node.left) - getHeight(node.right); } //判断一个树是否是一个平衡二叉树 public boolean isBalance(Node node){ if(node == null) return true; int balanceFactor = Math.abs(getBalanceFactor(node.left) - getBalanceFactor(node.right)); if(balanceFactor > 1) return false; return isBalance(node.left) && isBalance(node.right); } public boolean isBalance(){ return isBalance(root); } //中序遍历树 private void inPrevOrder(Node root){ if(root == null) return; inPrevOrder(root.left); root.display(); inPrevOrder(root.right); } public void inPrevOrder(){ System.out.print("中序遍历:"); inPrevOrder(root); }}
RR (kidal)
Masukkan nod ke dalam subpohon kanan subpohon kanan pokok, menyebabkan pokok binari menjadi tidak seimbang, seperti yang ditunjukkan di bawah, Memasukkan 5 ke dalam pokok binari seimbang menyebabkan pokok menjadi tidak seimbang Pada masa ini, operasi sebelah kiri diperlukan, seperti berikut:
Kodnya adalah seperti berikut:
//左旋,并且返回新的根节点 public Node leftRotate(Node node){ System.out.println("leftRotate"); Node cur = node.right; node.right = cur.left; cur.left = node; //跟新node和cur的高度 node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1; cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1; return cur; }
LL (putaran tangan kanan)
Memasukkan nod ke dalam subpokok kiri subpokok kiri pokok AVL menyebabkan pokok binari menjadi tidak seimbang Seperti yang ditunjukkan dalam rajah di bawah, memasukkan 2 ke dalam pokok binari seimbang menyebabkan pokok menjadi tidak seimbang Dalam kes ini, putaran kiri diperlukan seperti berikut:
Kod adalah seperti berikut:
//右旋,并且返回新的根节点 public Node rightRotate(Node node){ System.out.println("rightRotate"); Node cur = node.left; node.left = cur.right; cur.right = node; //跟新node和cur的高度 node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1; cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1; return cur; }LR (mula-mula kiri dan kemudian kanan) Masukkan nod ke dalam pepohon AVL
, menyebabkan pokok ini tidak lagi seimbang Anda perlu menjajarkan 左子树的右子树
dahulu dan kemudian 左子树进行左旋
. Seperti yang ditunjukkan dalam rajah di bawah, nod yang dimasukkan ialah 5. 整棵树右旋
Masukkan nod ke dalam pepohon AVL
, menyebabkan pokok menjadi tidak seimbang. Anda perlu menyelaraskan dahulu dan kemudian 右子树的左子树
Seperti yang ditunjukkan dalam rajah di bawah, nod yang dimasukkan ialah 2.右子树进行右旋
整棵树左旋
Tambah nod
Padamkan nod
//添加元素 public void add(E e){ root = add(root,e); } public Node add(Node node, E value) { if (node == null) { size++; return new Node(value); } if (value.compareTo(node.value) > 0) { node.right = add(node.right, value); } else if (value.compareTo(node.value) < 0) { node.left = add(node.left, value); } //跟新节点高度 node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1; //获取当前节点的平衡因子 int balanceFactor = getBalanceFactor(node); //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的左子树上,此时需要进行右旋 if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { return rightRotate(node); } //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上,此时需要进行左旋 else if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) { return leftRotate(node); } //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的右子树上,此时需要先对左子树左旋,在整个树右旋 else if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } //balanceFactor < -1 && getBalanceFactor(node.left) > 0 //该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上,此时需要先对右子树右旋,再整个树左旋 else if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; }
Atas ialah kandungan terperinci Analisis contoh pokok AVL struktur data Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

SublimeText3 Linux versi baharu
SublimeText3 Linux versi terkini

EditPlus versi Cina retak
Saiz kecil, penyerlahan sintaks, tidak menyokong fungsi gesaan kod

PhpStorm versi Mac
Alat pembangunan bersepadu PHP profesional terkini (2018.2.1).

MinGW - GNU Minimalis untuk Windows
Projek ini dalam proses untuk dipindahkan ke osdn.net/projects/mingw, anda boleh terus mengikuti kami di sana. MinGW: Port Windows asli bagi GNU Compiler Collection (GCC), perpustakaan import yang boleh diedarkan secara bebas dan fail pengepala untuk membina aplikasi Windows asli termasuk sambungan kepada masa jalan MSVC untuk menyokong fungsi C99. Semua perisian MinGW boleh dijalankan pada platform Windows 64-bit.

ZendStudio 13.5.1 Mac
Persekitaran pembangunan bersepadu PHP yang berkuasa