比較堆和樹/

Question

我是數據結構中的新手。

所以我問自己，堆和樹有什麼不同？

我也看到在許多文件堆是由數組實現，樹是poniters。是對的嗎？

而當我們需要使用樹或堆？

Answer 1

計算機科學中的樹是表示樹結構的抽象數據類型。根節點可以由子節點組成，其中每個子節點也是樹。

請注意，並非所有的樹都是二叉搜索樹。二叉搜索樹是有2個定義屬性樹：

• 每個節點最多有2個孩子

• 的左孩子小於父

• 右孩子大於父親

另一種特殊的樹是堆。堆是特殊的，因爲它具有以下屬性：

• 樹中的每個節點總是小於或等於每個子節點。

現在你如何選擇實現一棵樹取決於你。樹可以通過指針/引用來實現;一個節點存儲一個值和指向其子的指針/引用。

一棵樹也可以作爲一個數組來實現。父母在索引0處。如果最多有d個孩子，則索引k處父母的子女i處於索引d*k+i。除此之外，我們希望使用數組，因爲與遍歷指針相比，數組非常快。

但是，二叉搜索樹通常使用指針來實現。這是因爲兩個原因。

1. 如果這是一個數組，它總是會爲最壞的情況分配足夠的空間。換句話說，如果你的二叉搜索樹的高度爲h，你的數組的大小必須是O(2^h)。這很糟糕，因爲你的樹只能包含h元素。

2. 刪除也非常耗時。如果刪除根節點，則必須將整個子樹移動以替換它。我們希望首先使用二叉搜索樹的原因是爲了保證O(log n)操作，我們不會使用數組。

堆，在手上，通常作爲數組實現的，因爲它的樹總是完全平衡的（每個節點都有d孩子除了可能在葉）這意味着很少有浪費的空間，所以我們贏了不必擔心1）。此外，堆的刪除不會像二叉搜索樹那樣劇烈地影響樹的結構，所以2）也不適用。