どのように、我々はバランスの取れた二分木を得ますか?

バイナリツリー

エーbinary tree , 名前が示すようにtree 各ノードが2つの子ノードを持つ場合.バイナリツリーは空であり、ツリー内のゼロノードを意味する.クールなことbinary trees は再帰的な構造である.これは、すべてのツリーに対して順番にそれを適用することにより、ツリー全体にルールを適用することができます.

バイナリツリーを定義するには、2つのデータ構造が必要です.一つはルートノードを追跡する全体的なバイナリツリー構造である.もう一方は、左右の部分木を追跡するノード構造である.

class binaryTree {
  public:
    node * root; //a pointer to the root
};

では、ノード構造を定義して、左右の子ノードの両方を追跡し、データを格納します.この場合、キーを呼び出します.

class node {
  public:
    node * left; //a pointer to the root of the left subtree
    node * right; //a pointer to the root of the right subtree
    int key;
};

ここでは、キーデータ型がinteger , ちょうど物事をシンプルに保つ.しかし、それは注意しなければなりませんkey タイプは、比較演算子、すなわち、<<>>>>、<= ,=を許すデータ構造です.
このレッスンは、もともと2007年に出版されましたhttps://algodaily.com , 私は技術的なインタビューコースを維持し、野心的な開発者のために考える作品を書く.

バイナリ検索ツリー

バイナリ検索ツリーBST バイナリの木の特別な場合です.そして、それは木の中で重要な値の配置に加えられた制約を持ちます.簡単に言えば、bstは以下の規則で定義されます:

左のサブツリーのすべてのノードには、親のキー値以下のキー値があります

右のサブツリーのすべてのノードには、親のキー値より大きいか等しいキー値があります

以下の図はバイナリ検索ツリーの例を示します.

バランスBST

エーbalanced BST 左と右のサブツリーの高さの違いが1つ以下であるBSTです1 ). これらの例題は明確にする必要があります.

ハウツーとスタイル

BSTに対する平衡アルゴリズムが存在する.red black trees or AVL trees . これらの構造において、BSTの範囲内で鍵の挿入および削除は、木が平衡のままであるような方法で行われる.
しかし、与えられたunbalanced ツリーは、効率的な方法でバランスの取れたツリーに変換する方法ですか?配列を使うことで、とてもシンプルで効率的なアルゴリズムがあります.2つのステップがあります.

BSTの順をたどって、値を配列で格納します.配列の値は昇順でソートされます.

ソートされた配列からバランスのとれたBSTツリーを作成します.

だからここまでは2つのステップがあります.
ステップ1:順横断
ステップ2:バランスBSTを作成
彼らを探検しましょう.バランスのとれたBSTを効率的に作成するための擬似コードは再帰的であり、基底ケースと再帰的ケースは以下のようになります.

ベースケース：

配列がsizeの場合、null ポインタと停止.

再帰的な場合:

定義するbuild メソッド.

配列の中央を取得し、ルートノードにします.

再帰的な場合を呼び出すbuild 配列の左側の半分に.ルートノードの左の子は、この再帰的な呼び出しによって返されるポインタです.

再帰的な場合を呼び出すbuild 配列の右半分.ルートノードの右の子は、この再帰呼び出しによって返されるポインタです.

手順1で作成したルートノードへのポインタを返します.

上記の疑似コードの優雅さは、木自体が再帰的であるという事実から生じます.したがって、再帰的手続きを適用できる.私たちは何度も何度も同じ部分を左右のサブツリーに適用します.
あなたは、配列の真ん中を得る方法を不思議に思うかもしれません.単純式(size/2) 中央の項目のインデックスを返します.もちろん、配列のインデックスが0 .
以前の擬似コードがどのように機能するかを見てみましょう.我々はいくつかの簡単なシナリオを取るし、より複雑なものを構築します.

Array : [ 30 ]

最初に、1つの要素だけで以下の配列を見ます.30 ).

array : [ 31 , 37 , 38 ]

それではサイズ3の配列を見ましょう.

array :[ 10 , 11 ]

私たちは今、2つの要素を持つ偶数サイズの配列のために行きましょう.

array : [ 10 , 11 , 17 , 19 ]

この例を、4つの要素を持つ偶数サイズの配列に拡張できます.

array : [ 10 , 11 , 17 , 19 , 30 , 31 , 37 , 38 ]

つの要素を持つ偶数サイズの配列.

今、我々は、バランスの仕組みを理解し、我々は楽しい部分を行うことができます、コーディングです.ここでは、再帰的なルーチンですbuild 我々が以前定義したこと.
以下のコードは、上記のヘルパー再帰関数build :

void build(int *arr, int size, binaryTree &tree) {
    tree.root = build(arr, 0, size-1);
}

// build returns a pointer to the root node of the sub-tree
// lower is the lower index of the array
// upper is the upper index of the array
node * build(int * arr, int lower, int upper) {
  int size = upper - lower + 1;
  // cout << size; //uncomment in case you want to see how it's working
  // base case: array of size zero
  if (size <= 0)
    return NULL;
  // recursive case
  int middle = size / 2 + lower;
  // make sure you add the offset of lower
  //  cout << arr[middle] << " "; //uncomment in case you want to see how it's working
  node * subtreeRoot = new node;
  subtreeRoot - > key = arr[middle];
  subtreeRoot - > left = build(arr, lower, middle - 1);
  subtreeRoot - > right = build(arr, middle + 1, upper);
  return subtreeRoot;
}

上記のコードを試してみる前に、常に紙とペンで座って、コードの乾いた実行を何回か行います.前のコードは、O(N) , どこN はツリー内のキーの数です.Inorder traversal 必要O(N) 時間.配列の各要素に一度だけアクセスしているのでbuild 方法は、また、このように時間の複雑さを有するO(N) .
このレッスンは、もともと2007年に出版されましたhttps://algodaily.com , 私は技術的なインタビューコースを維持し、野心的な開発者のために考える作品を書く.