Рубрики

Сжатое кодирование бинарного дерева

Краткое кодирование Binary Tree занимает почти минимально возможное пространство. Число структурно различных бинарных деревьев на n узлах равно n-му каталонскому числу . Для больших n это около 4 n ; таким образом, нам нужно по крайней мере около log 2 4 n = 2n бит для его кодирования. Следовательно, сжатое двоичное дерево должно занимать 2n + o (n) битов.

Одно простое представление, которое удовлетворяет этой границе, состоит в том, чтобы посетить узлы дерева в предзаказе, выводя «1» для внутреннего узла и «0» для листа. Если дерево содержит данные, мы можем просто одновременно сохранить их в последовательном массиве в предзаказе.

Ниже приведен алгоритм кодирования:

function EncodeSuccinct(node n, bitstring structure, array data) {
    if n = nil then
        append 0 to structure;
    else
        append 1 to structure;
        append n.data to data;
        EncodeSuccinct(n.left, structure, data);
        EncodeSuccinct(n.right, structure, data);
}

И ниже алгоритм для декодирования

function DecodeSuccinct(bitstring structure, array data) {
    remove first bit of structure and put it in b
    if b = 1 then
        create a new node n
        remove first element of data and put it in n.data
        n.left = DecodeSuccinct(structure, data)
        n.right = DecodeSuccinct(structure, data)
        return n
    else
        return nil
}

Источник: https://en.wikipedia.org/wiki/Binary_tree#Succinct_encodings

Пример:

Input:   
        10
     /      \
   20       30
  /  \        \
 40   50      70 

Data Array (Contains preorder traversal)
10 20 40 50 30 70

Structure Array
1 1 1 0 0 1 0 0 1 0 1 0 0 
1 indicates data and 0 indicates NULL

Ниже приведена реализация вышеуказанных алгоритмов на C ++.

C ++

// C ++ программа для демонстрации кодирования и декодирования сжатого дерева
#include<bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    int key;

    struct Node* left, *right;

};

  
// Сервисная функция для создания нового узла

Node *newNode(int key)

{

    Node *temp = new Node;

    temp->key  = key;

    temp->left  = temp->right = NULL;

    return (temp);

}

  
// Эта функция заполняет списки 'struc' и 'data'. список 'Struc'
// хранит информацию о структуре. список данных хранит данные дерева

void EncodeSuccinct(Node *root, list<bool> &struc, list<int> &data)

{

    // Если root равен NULL, положить 0 в массиве структуры и вернуть

    if (root == NULL)

    {

        struc.push_back(0);

        return;

    }

  

    // Остальное место 1 в структурном массиве, ввод в массиве данных

    // и повторить для левых и правых детей

    struc.push_back(1);

    data.push_back(root->key);

    EncodeSuccinct(root->left, struc, data);

    EncodeSuccinct(root->right, struc, data);

}

  
// Создает дерево из 'struc' и 'data'

Node *DecodeSuccinct(list<bool> &struc, list<int> &data)

{

    if (struc.size() <= 0)

        return NULL;

  

    // Удалить один элемент из списка структуры

    bool b = struc.front();

    struc.pop_front();

  

    // Если удален бит 1,

    if (b == 1)

    {

         // удаляем элемент из списка данных

        int key = data.front();

        data.pop_front();

  

        // Создать узел дерева с удаленными данными

        Node *root = newNode(key);

  

        // И повторяем для создания левого и правого поддеревьев

        root->left = DecodeSuccinct(struc, data);

        root->right = DecodeSuccinct(struc, data);

        return root;

    }

  

    return NULL;

}

  
// Утилита для печати дерева

void preorder(Node* root)

{

    if (root)

    {

        cout << "key: "<< root->key;

        if (root->left)

            cout << " | left child: " << root->left->key;

        if (root->right)

            cout << " | right child: " << root->right->key;

        cout << endl;

        preorder(root->left);

        preorder(root->right);

    }

}

  
// Драйвер программы

int main()

{

    // Построим дерево, показанное на рисунке выше

    Node *root         = newNode(10);

    root->left         = newNode(20);

    root->right        = newNode(30);

    root->left->left   = newNode(40);

    root->left->right  = newNode(50);

    root->right->right = newNode(70);

  

    cout << "Given Tree\n";

    preorder(root);

    list<bool> struc;

    list<int>  data;

    EncodeSuccinct(root, struc, data);

  

    cout << "\nEncoded Tree\n";

    cout << "Structure List\n";

    list<bool>::iterator si; // Структура итератора

    for (si = struc.begin(); si != struc.end(); ++si)

        cout << *si << " ";

  

    cout << "\nData List\n";

    list<int>::iterator di; // Data iIterator

    for (di = data.begin(); di != data.end(); ++di)

        cout << *di << " ";

  

    Node *newroot = DecodeSuccinct(struc, data);

  

    cout << "\n\nPreorder traversal of decoded tree\n";

    preorder(newroot);

  

    return 0;

}

питон

# Программа Python для демонстрации кодирования и декодирования сжатого дерева

  
# Структура узла

class Node:

    # Сервисная функция для создания нового узла

    def __init__(self , key):

        self.key = key 

        self.left = None

        self.right = None

  

def EncodeSuccint(root , struc , data):

      

    # Если root равен None, поместите 0 в массив структуры и верните

    if root is None :

        struc.append(0)

        return

  

    # Остальное место 1 в массиве структур, введите массив данных

    # и повторить для левых и правых детей

    struc.append(1)

    data.append(root.key)

    EncodeSuccint(root.left , struc , data)

    EncodeSuccint(root.right , struc ,data)

      

  
# Создает дерево из 'struc' и 'data'

def DecodeSuccinct(struc , data):

    if(len(struc) <= 0):

        return None

      

    # Удалить один элемент из списка структуры

    b = struc[0]

    struc.pop(0)

      

    # Если удален бит 1

    if b == 1

        key = data[0]

        data.pop(0)

      

        # Создать узел дерева с удаленными данными

        root = Node(key)

  

        # И повторить создание левого и правого поддеревьев

        root.left = DecodeSuccinct(struc , data);

        root.right = DecodeSuccinct(struc , data);

        return root

  

    return None

  

  

def preorder(root):

    if root is not None:

        print "key: %d" %(root.key),

              

        if root.left is not None:

            print "| left child: %d" %(root.left.key),

        if root.right is not None:

            print "| right child %d" %(root.right.key),

        print ""

        preorder(root.left)

        preorder(root.right)

  
# Драйверная программа

root = Node(10)

root.left = Node(20

root.right = Node(30)

root.left.left = Node(40)

root.left.right = Node(50)

root.right.right = Node(70)         

  

print "Given Tree"

preorder(root)

struc = []

data = []

EncodeSuccint(root , struc , data)

  

print "\nEncoded Tree"

print "Structure List"

  

for i in struc:

    print i ,

  

print "\nDataList"

for value in data:

    print value,

  

newroot = DecodeSuccinct(struc , data)

  

print "\n\nPreorder Traversal of decoded tree"

preorder(newroot)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)


Выход:


Given Tree
key: 10 | left child: 20 | right child: 30
key: 20 | left child: 40 | right child: 50
key: 40
key: 50
key: 30 | right child: 70
key: 70

Encoded Tree
Structure List
1 1 1 0 0 1 0 0 1 0 1 0 0 
Data List
10 20 40 50 30 70 

Preorder traversal of decoded tree
key: 10 | left child: 20 | right child: 30
key: 20 | left child: 40 | right child: 50
key: 40
key: 50
key: 30 | right child: 70
key: 70

Эта статья предоставлена Шивамом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Сжатое кодирование бинарного дерева

0.00 (0%) 0 votes