簡介

二元搜索樹 (Binary Search Tree) 是基於二元樹的一種延伸，二元搜索樹的應用範圍很廣，可以利用在搜索、排序和提供資料集合基本結構，發展其他資料結構，所以也是重要的資料結構之一。

定義

定義除了繼承二元樹的定義外，二元搜索樹本身也有額外的定義，但可能會看到幾種不同的說法，而較多數人使用的定義如下：

  1. 左子樹不為空，則左子樹的所有節點的鍵值 (Key) 小於根節點的鍵值。
  2. 右子樹不為空，則右子樹的所有節點的鍵值 (Key) 大於根節點的鍵值。
  3. 左右子樹也都是二元搜索樹。
  4. 節點不會有重複的鍵值。

這個定義是樹中的節點都具有 Key-value pair 情況，有時候可能會其他變化：

  • 沒有鍵值，而用值 (Value) 來比較。
  • 允許重複的資料，此時會出現等於的情況，則將定義 1. 改成小於等於或者定義 2. 改成大於等於。

以下為示意圖：
二元搜索樹 (Binary Search Tree)

實作

不同類型的樹會有不同的介面，原始版本通常會實作以下介面：

  1. add: 加入資料。(或 insert)
  2. remove: 移除資料。(或 delete)
  3. containsKey: 判斷是否包含鍵值。
  4. get: 取出資料。

無鍵值的版本則會有以下介面：

  1. add: 加入資料。(或 insert)
  2. remove: 移除資料。(或d elete)
  3. contains: 判斷是否包含資料。

本文將實作有鍵值版本，另外這邊也實作一些其他的介面：

  1. clone: 複製樹。
  2. size: 資料的數目。

刪除

刪除的操作較為複雜，作為資料集合時，刪除不能直接把節點與其子孫全部移除，而需要進行一些移動的操作讓樹保持二元搜索樹的定義，基本上有三種情況需要考慮：

  1. 沒有子節點時，可以直接移除。
  2. 有一個子節點時，將子節點取代被移除的節點的位置。
  3. 有兩個子節點時，將樹作中序 (in-order) 排列後，可以選擇被移除節點的前驅 (predecessor) 節點或後繼 (successor) 節點來替換；或者白話一點的說法，可以從左子樹找到最大值或右子樹找到最小值的節點，來取代被移除的節點位置，並同時將找到的節點之子節點取代自身的位置。

利用上面的示意圖來做說明，假設移除節點 9，為有一個子節點的情況，所以把子節點 7 移上來取代，如下圖所示：
刪除

而假設移除節點 4，則為兩個子節點的情況，則可以選擇左子樹最大值，也就是節點 3，或者右子樹最小值，也就是節點5來取代，這邊選擇節點 5，如圖所示：
刪除

而節點 5 有子節點 6，子節點 6 取代原來節點5的位置，節點5則取代節點 4 的位置。這類情況可以用這張圖來說明：
刪除

這張圖為移除節點 7 時，可以選擇節點 6 或 9 的調整方式。二元搜索樹的最大值就在最右邊的節點 (搜索直到右子節點為空)，最小值就在最左邊的節點 (搜索直到左子節點為空)，所以選擇左邊的情況，節點 6 一定不會有右子節點，反之節點 9 亦然，但可能會有一個子節點，必須移動到原來節點 6 或 9 的位置。

實作上可以用連結串列或者是陣列的方式來實作：

連結串列

連結串列的方式較為簡單，使用三個指標分別指向父節點、左子節點和右子節點即可完成。

陣列

實作上利用一個陣列來表示整棵樹的資料結構，利用索引公式來找到父節點、左子節點和右子節點，而無需另外的指標表示，可參考二元樹這篇文章。當樹不平衡時，會需要產生非常巨大的陣列，很容易就出現記憶體不足的現象，又加上刪除節點時需要重新調整陣列的元素位置很多，實作上不容易效能也較差，所以一般使用連結串列的方式實作較好。

語法

C#

抽象類別

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    public abstract class BinarySearchTree<K, V> where K : IComparable
    {
        public abstract int Count { get; }
        public abstract void Add(K key, V value);
        public abstract void Remove(K key);
        public abstract V Get(K key);
        public abstract bool ContainsKey(K key);
        public abstract BinarySearchTree<K, V> Clone();
    }
}

連結串列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    public class LinkedBinarySearchTree<K, V> : BinarySearchTree<K, V> where K : IComparable
    {
        public class LinkedBinarySearchTreeNode<NK, NV> where NK : IComparable
        {
            public NK Key { get; set; }
            public NV Value { get; set; }
            public LinkedBinarySearchTreeNode<NK, NV> Parent { get; set; }
            public LinkedBinarySearchTreeNode<NK, NV> Left { get; set; }
            public LinkedBinarySearchTreeNode<NK, NV> Right { get; set; }

            public LinkedBinarySearchTreeNode(NK key, NV value)
            {
                Key = key;
                Value = value;
            }
        }

        protected LinkedBinarySearchTreeNode<K, V> root;
        protected int count;

        public override int Count
        {
            get
            {
                return count;
            }
        }

        public override void Add(K key, V value)
        {
            if (root == null)
                root = new LinkedBinarySearchTreeNode<K, V>(key, value);
            else
            {
                LinkedBinarySearchTreeNode<K, V> node = root;
                LinkedBinarySearchTreeNode<K, V> parent = null;
                int result = 0;
                while (node != null)
                {
                    result = key.CompareTo(node.Key);
                    parent = node;
                    if (result > 0)
                        node = node.Right;
                    else if (result < 0)
                        node = node.Left;
                    else
                    {
                        node.Value = value;
                        return;
                    }
                }
                LinkedBinarySearchTreeNode<K, V> child = new LinkedBinarySearchTreeNode<K, V>(key, value);
                child.Parent = parent;
                if (result > 0)
                    parent.Right = child;
                else
                    parent.Left = child;
            }
            ++count;
        }

        public override void Remove(K key)
        {
            LinkedBinarySearchTreeNode<K, V> node = Find(key);
            if (node == null)
                return;
            if (node.Left == null)
            {
                if (node.Right == null)
                    Replace(node, null);
                else
                    Replace(node, node.Right);
            }
            else if (node.Right == null)
                Replace(node, node.Left);
            else
            {
                LinkedBinarySearchTreeNode<K, V> tmpNode = node.Right;
                while (true)
                {
                    if (tmpNode.Left == null)
                        break;
                    tmpNode = tmpNode.Left;
                }
                Replace(tmpNode, tmpNode.Right);
                tmpNode.Left = node.Left;
                if (node.Left != null)
                    node.Left.Parent = tmpNode;
                tmpNode.Right = node.Right;
                if (node.Right != null)
                    node.Right.Parent = tmpNode;
                Replace(node, tmpNode);
            }
            --count;
        }

        public override V Get(K key)
        {
            LinkedBinarySearchTreeNode<K, V> node = Find(key);
            if(node == null)
                throw new KeyNotFoundException();
            return node.Value;
        }

        public override bool ContainsKey(K key)
        {
            return Find(key) != null;
        }

        protected void Replace(LinkedBinarySearchTreeNode<K, V> node, LinkedBinarySearchTreeNode<K, V> newNode)
        {
            LinkedBinarySearchTreeNode<K, V> parent = node.Parent;
            if (parent != null)
            {
                if (node == parent.Left)
                    parent.Left = newNode;
                else
                    parent.Right = newNode;
                node.Parent = null;
            }
            else
                root = newNode;

            if (newNode != null)
                newNode.Parent = parent;

            node.Left = null;
            node.Right = null;
        }

        protected LinkedBinarySearchTreeNode<K, V> Find(K key)
        {
            LinkedBinarySearchTreeNode<K, V> node = root;
            while (node != null)
            {
                int result = key.CompareTo(node.Key);
                if (result > 0)
                    node = node.Right;
                else if (result < 0)
                    node = node.Left;
                else
                    break;
            }
            return node;
        }

        public override BinarySearchTree<K, V> Clone()
        {
            LinkedBinarySearchTree<K, V> cloneTree = new LinkedBinarySearchTree<K, V>();
            cloneTree.root = new LinkedBinarySearchTreeNode<K, V>(root.Key, root.Value);
            CloneChildren(cloneTree.root, root);
            cloneTree.count = count;
            return cloneTree;
        }

        protected void CloneChildren(LinkedBinarySearchTreeNode<K, V> cloneNode, LinkedBinarySearchTreeNode<K, V> node)
        {
            LinkedBinarySearchTreeNode<K, V> tmpNode = node.Left;
            LinkedBinarySearchTreeNode<K, V> tmpCloneNode;
            if (tmpNode != null)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.Key, tmpNode.Value);
                tmpCloneNode.Parent = cloneNode;
                cloneNode.Left = tmpCloneNode;
                CloneChildren(tmpCloneNode, tmpNode);
            }

            tmpNode = node.Right;
            if (tmpNode != null)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.Key, tmpNode.Value);
                tmpCloneNode.Parent = cloneNode;
                cloneNode.Right = tmpCloneNode;
                CloneChildren(tmpCloneNode, tmpNode);
            }
        }
    }
}

陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    public class ArrayBinarySearchTree<K, V> : BinarySearchTree<K, V> where K : IComparable
    {
        public class ArrayBinarySearchTreeNode<NK, NV> where NK : IComparable
        {
            public NK Key { get; set; }
            public NV Value { get; set; }
            public ArrayBinarySearchTreeNode(NK key, NV value)
            {
                Key = key;
                Value = value;
            }
        }

        protected ArrayBinarySearchTreeNode<K, V>[] array;
        protected int count;

        public override int Count
        {
            get
            {
                return count;
            }
        }

        public ArrayBinarySearchTree()
            : this(10240)
        {
        }

        public ArrayBinarySearchTree(int capacity)
        {
            array = new ArrayBinarySearchTreeNode<K, V>[capacity];
        }

        public override void Add(K key, V value)
        {
            int length = array.Length;
            int index = 1;
            while (array[index] != null)
            {
                int result = key.CompareTo(array[index].Key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                {
                    array[index].Value = value;
                    return;
                }

                if (index + 1 > length)
                {
                    ArrayBinarySearchTreeNode<K, V>[] newArray = new ArrayBinarySearchTreeNode<K, V>[length * 2];
                    Array.Copy(array, newArray, length);
                    array = newArray;
                    length *= 2;
                }
            }
            array[index] = new ArrayBinarySearchTreeNode<K, V>(key, value);
            ++count;
        }

        public override void Remove(K key)
        {
            int index = IndexOf(key);
            if (index == -1)
                return;

            int length = array.Length;
            int leftIndex = index * 2;
            int rightIndex = leftIndex + 1;
            if (leftIndex >= length || array[leftIndex] == null)
            {
                if (rightIndex >= length || array[rightIndex] == null)
                    array[index] = null;
                else
                    MoveTree(rightIndex, index);
            }
            else if (rightIndex >= length || array[rightIndex] == null)
                MoveTree(leftIndex, index);
            else
            {
                // find left-max or right-min node;
                int tmpIndex = rightIndex * 2;
                while (tmpIndex < length && array[tmpIndex] != null)
                    tmpIndex *= 2;
                tmpIndex /= 2;
                array[index] = array[tmpIndex];
                MoveTree(tmpIndex * 2 + 1, tmpIndex);
            }
            --count;
        }

        public override V Get(K key)
        {
            int index = IndexOf(key);
            if (index == -1)
                throw new KeyNotFoundException();
            return array[index].Value;
        }

        public override bool ContainsKey(K key)
        {
            return IndexOf(key) != -1;
        }

        protected int IndexOf(K key)
        {
            int length = array.Length;
            int index = 1;
            while (index < length && array[index] != null)
            {
                int result = key.CompareTo(array[index].Key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                    return index;
            }
            return -1;
        }

        protected void MoveTree(int from, int to)
        {
            Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
            queue.Enqueue(new KeyValuePair<int, int>(from, to));
            while (queue.Count > 0)
            {
                KeyValuePair<int, int> pair = queue.Dequeue();
                int f = pair.Key;
                int t = pair.Value;
                if (Move(f, t))
                {
                    queue.Enqueue(new KeyValuePair<int, int>(f * 2, t * 2));
                    queue.Enqueue(new KeyValuePair<int, int>(f * 2 + 1, t * 2 + 1));
                }
            }
        }

        protected bool Move(int from, int to)
        {
            // from > to
            int length = array.Length;
            if (from < length)
            {
                if (array[from] == null)
                {
                    array[to] = null;
                    return false;
                }
                array[to] = array[from];
                array[from] = null;
                return true;
            }
            else if (to < length)
                array[to] = null;
            return false;
        }

        public override BinarySearchTree<K, V> Clone()
        {
            ArrayBinarySearchTree<K, V> cloneTree = new ArrayBinarySearchTree<K, V>(array.Length);
            for (int i = 1; i < array.Length; ++i)
                if (array[i] != null)
                    cloneTree.array[i] = new ArrayBinarySearchTreeNode<K, V>(array[i].Key, array[i].Value);
            cloneTree.count = count;
            return cloneTree;
        }
    }
}

Java

抽象類別

1
2
3
4
5
6
7
8
public abstract class BinarySearchTree<K extends Comparable<K>, V> {
    public abstract int size();
    public abstract void add(K key, V value);
    public abstract void remove(K key);
    public abstract V get(K key);
    public abstract boolean containsKey(K key);
    public abstract BinarySearchTree<K, V> copy();
}

連結串列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
public class LinkedBinarySearchTree<K extends Comparable<K>, V> extends BinarySearchTree<K, V> {
    public static class LinkedBinarySearchTreeNode<NK, NV>
    {
        public NK key;
        public NV value;
        public LinkedBinarySearchTreeNode<NK, NV> parent;
        public LinkedBinarySearchTreeNode<NK, NV> left;
        public LinkedBinarySearchTreeNode<NK, NV> right;

        public LinkedBinarySearchTreeNode(NK key, NV value)
        {
            this.key = key;
            this.value = value;
        }
    }

    protected LinkedBinarySearchTreeNode<K, V> root;
    protected int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public void add(K key, V value) {
        if (root == null)
            root = new LinkedBinarySearchTreeNode<K, V>(key, value);
        else
        {
            LinkedBinarySearchTreeNode<K, V> node = root;
            LinkedBinarySearchTreeNode<K, V> parent = null;
            int result = 0;
            while (node != null)
            {
                result = key.compareTo(node.key);
                parent = node;
                if (result > 0)
                    node = node.right;
                else if (result < 0)
                    node = node.left;
                else
                {
                    node.value = value;
                    return;
                }
            }
            LinkedBinarySearchTreeNode<K, V> child = new LinkedBinarySearchTreeNode<K, V>(key, value);
            child.parent = parent;
            if (result > 0)
                parent.right = child;
            else
                parent.left = child;
        }
        ++size;
    }

    @Override
    public void remove(K key) {
        LinkedBinarySearchTreeNode<K, V> node = find(key);
        if (node == null)
            return;
        if (node.left == null)
        {
            if (node.right == null)
                replace(node, null);
            else
                replace(node, node.right);
        }
        else if (node.right == null)
            replace(node, node.left);
        else
        {
            LinkedBinarySearchTreeNode<K, V> tmpNode = node.right;
            while (true)
            {
                if (tmpNode.left == null)
                    break;
                tmpNode = tmpNode.left;
            }
            replace(tmpNode, tmpNode.right);
            tmpNode.left = node.left;
            if (node.left != null)
                node.left.parent = tmpNode;
            tmpNode.right = node.right;
            if (node.right != null)
                node.right.parent = tmpNode;
            replace(node, tmpNode);
        }
        --size;
    }

    @Override
    public V get(K key) {
        LinkedBinarySearchTreeNode<K, V> node = find(key);
        if(node == null)
            return null;
        return node.value;
    }

    @Override
    public boolean containsKey(K key) {
        return find(key) != null;
    }

    @Override
    public BinarySearchTree<K, V> copy() {
        LinkedBinarySearchTree<K, V> cloneTree = new LinkedBinarySearchTree<K, V>();
        cloneTree.root = new LinkedBinarySearchTreeNode<K, V>(root.key, root.value);
        cloneChildren(cloneTree.root, root);
        cloneTree.size = size;
        return cloneTree;
    }

    protected void replace(LinkedBinarySearchTreeNode<K, V> node, LinkedBinarySearchTreeNode<K, V> newNode)
    {
        LinkedBinarySearchTreeNode<K, V> parent = node.parent;
        if (parent != null)
        {
            if (node == parent.left)
                parent.left = newNode;
            else
                parent.right = newNode;
            node.parent = null;
        }
        else
            root = newNode;

        if (newNode != null)
            newNode.parent = parent;

        node.left = null;
        node.right = null;
    }

    protected LinkedBinarySearchTreeNode<K, V> find(K key)
    {
        LinkedBinarySearchTreeNode<K, V> node = root;
        while (node != null)
        {
            int result = key.compareTo(node.key);
            if (result > 0)
                node = node.right;
            else if (result < 0)
                node = node.left;
            else
                break;
        }
        return node;
    }

    protected void cloneChildren(LinkedBinarySearchTreeNode<K, V> cloneNode, LinkedBinarySearchTreeNode<K, V> node)
    {
        LinkedBinarySearchTreeNode<K, V> tmpNode = node.left;
        LinkedBinarySearchTreeNode<K, V> tmpCloneNode;
        if (tmpNode != null)
        {
            tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.key, tmpNode.value);
            tmpCloneNode.parent = cloneNode;
            cloneNode.left = tmpCloneNode;
            cloneChildren(tmpCloneNode, tmpNode);
        }

        tmpNode = node.right;
        if (tmpNode != null)
        {
            tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.key, tmpNode.value);
            tmpCloneNode.parent = cloneNode;
            cloneNode.right = tmpCloneNode;
            cloneChildren(tmpCloneNode, tmpNode);
        }
    }
}

陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
import java.util.AbstractMap.SimpleEntry;
import java.util.LinkedList;
import java.util.Queue;


public class ArrayBinarySearchTree<K extends Comparable<K>, V> extends BinarySearchTree<K, V> {
    public static class ArrayBinarySearchTreeNode<NK, NV>
    {
        public NK key;
        public NV value;
        public ArrayBinarySearchTreeNode(NK key, NV value)
        {
            this.key = key;
            this.value = value;
        }
    }

    protected ArrayBinarySearchTreeNode<K, V>[] array;
    protected int size;

    public ArrayBinarySearchTree()
    {
        this(10240);
    }

    @SuppressWarnings("unchecked")
    public ArrayBinarySearchTree(int capacity)
    {
        this.array = (ArrayBinarySearchTreeNode<K, V>[])new ArrayBinarySearchTreeNode[capacity];
    }

    @Override
    public int size() {
        return size;
    }

    @SuppressWarnings("unchecked")
    @Override
    public void add(K key, V value) {
        int length = array.length;
        int index = 1;
        while (array[index] != null)
        {
            int result = key.compareTo(array[index].key);
            if (result > 0)
                index = index * 2 + 1;
            else if (result < 0)
                index = index * 2;
            else
            {
                array[index].value = value;
                return;
            }

            if (index + 1 > length)
            {
                ArrayBinarySearchTreeNode<K, V>[] newArray = (ArrayBinarySearchTreeNode<K, V>[])new ArrayBinarySearchTreeNode[array.length * 2];
                System.arraycopy(array, 0, newArray, 0, array.length);
                array = newArray;
                length *= 2;
            }
        }
        array[index] = new ArrayBinarySearchTreeNode<K, V>(key, value);
        ++size;
    }

    @Override
    public void remove(K key) {
        int index = indexOf(key);
        if (index == -1)
            return;

        int length = array.length;
        int leftIndex = index * 2;
        int rightIndex = leftIndex + 1;
        if (leftIndex >= length || array[leftIndex] == null)
        {
            if (rightIndex >= length || array[rightIndex] == null)
                array[index] = null;
            else
                moveTree(rightIndex, index);
        }
        else if (rightIndex >= length || array[rightIndex] == null)
            moveTree(leftIndex, index);
        else
        {
            // find left-max or right-min node;
            int tmpIndex = rightIndex * 2;
            while (tmpIndex < length && array[tmpIndex] != null)
                tmpIndex *= 2;
            tmpIndex /= 2;
            array[index] = array[tmpIndex];
            moveTree(tmpIndex * 2 + 1, tmpIndex);
        }
        --size;
    }

    @Override
    public V get(K key) {
        int index = indexOf(key);
        if (index == -1)
            return null;
        return array[index].value;
    }

    @Override
    public boolean containsKey(K key) {
        return indexOf(key) != -1;
    }

    @Override
    public BinarySearchTree<K, V> copy() {
        ArrayBinarySearchTree<K, V> cloneTree = new ArrayBinarySearchTree<K, V>(array.length);
        for (int i = 1; i < array.length; ++i)
            if (array[i] != null)
                cloneTree.array[i] = new ArrayBinarySearchTreeNode<K, V>(array[i].key, array[i].value);
        cloneTree.size = size;
        return cloneTree;
    }

    protected int indexOf(K key)
    {
        int length = array.length;
        int index = 1;
        while (index < length && array[index] != null)
        {
            int result = key.compareTo(array[index].key);
            if (result > 0)
                index = index * 2 + 1;
            else if (result < 0)
                index = index * 2;
            else
                return index;
        }
        return -1;
    }

    protected void moveTree(int from, int to)
    {
        Queue<SimpleEntry<Integer, Integer>> queue = new LinkedList<SimpleEntry<Integer, Integer>>();
        queue.add(new SimpleEntry<Integer, Integer>(from, to));
        while (queue.size() > 0)
        {
            SimpleEntry<Integer, Integer> entry = queue.poll();
            int f = entry.getKey();
            int t = entry.getValue();
            if (move(f, t))
            {
                queue.add(new SimpleEntry<Integer, Integer>(f * 2, t * 2));
                queue.add(new SimpleEntry<Integer, Integer>(f * 2 + 1, t * 2 + 1));
            }
        }
    }

    protected boolean move(int from, int to)
    {
        // from > to
        int length = array.length;
        if (from < length)
        {
            if (array[from] == null)
            {
                array[to] = null;
                return false;
            }
            array[to] = array[from];
            array[from] = null;
            return true;
        }
        else if (to < length)
            array[to] = null;
        return false;
    }
}

C++

抽象類別

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

template<typename K, typename V>
class BinarySearchTree
{
    public:
        virtual int size() = 0;
        virtual void add(K key, V value) = 0;
        virtual void remove(K key) = 0;
        virtual V get(K key) = 0;
        virtual bool containsKey(K key) = 0;
        virtual BinarySearchTree<K, V>* clone() = 0;
    protected:
        int compareTo(K key1, K key2)
        {
            if(key1 > key2)
                return 1;
            else if(key1 < key2)
                return -1;
            return 0;
        }
    private:
};

#endif // BINARYSEARCHTREE_H

連結串列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#ifndef LINKEDBINARYSEARCHTREE_H
#define LINKEDBINARYSEARCHTREE_H

#include "BinarySearchTree.h"

template<typename K, typename V>
class LinkedBinarySearchTreeNode;

template<typename K, typename V>
class LinkedBinarySearchTree : public BinarySearchTree<K, V>
{
    public:
        LinkedBinarySearchTree()
        {
            root = 0;
            _size = 0;
        }
        virtual ~LinkedBinarySearchTree()
        {
            if(root != 0)
                delete root;
        }

        int size()
        {
            return _size;
        }

        void add(K key, V value)
        {
            if (root == 0)
                root = new LinkedBinarySearchTreeNode<K, V>(key, value);
            else
            {
                LinkedBinarySearchTreeNode<K, V>* node = root;
                LinkedBinarySearchTreeNode<K, V>* parent = 0;
                int result = 0;
                while (node != 0)
                {
                    result = BinarySearchTree<K, V>::compareTo(key, node->key);
                    parent = node;
                    if (result > 0)
                        node = node->right;
                    else if (result < 0)
                        node = node->left;
                    else
                    {
                        node->value = value;
                        return;
                    }
                }
                LinkedBinarySearchTreeNode<K, V>* child = new LinkedBinarySearchTreeNode<K, V>(key, value);
                child->parent = parent;
                if (result > 0)
                    parent->right = child;
                else
                    parent->left = child;
            }
            ++_size;
        }

        void remove(K key)
        {
            LinkedBinarySearchTreeNode<K, V>* node = find(key);
            if (node == 0)
                return;
            if (node->left == 0)
            {
                if (node->right == 0)
                    replace(node, 0);
                else
                    replace(node, node->right);
            }
            else if (node->right == 0)
                replace(node, node->left);
            else
            {
                LinkedBinarySearchTreeNode<K, V>* tmpNode = node->right;
                while (true)
                {
                    if (tmpNode->left == 0)
                        break;
                    tmpNode = tmpNode->left;
                }
                replace(tmpNode, tmpNode->right);
                tmpNode->left = node->left;
                if (node->left != 0)
                    node->left->parent = tmpNode;
                tmpNode->right = node->right;
                if (node->right != 0)
                    node->right->parent = tmpNode;
                replace(node, tmpNode);
            }
            delete node;
            --_size;
        }

        V get(K key)
        {
            LinkedBinarySearchTreeNode<K, V>* node = find(key);
            if(node == 0)
                throw "Key not found";
            return node->value;
        }

        bool containsKey(K key)
        {
            return find(key) != 0;
        }

        BinarySearchTree<K, V>* clone()
        {
            LinkedBinarySearchTree<K, V>* cloneTree = new LinkedBinarySearchTree<K, V>();
            cloneTree->root = new LinkedBinarySearchTreeNode<K, V>(root->key, root->value);
            cloneChildren(cloneTree->root, root);
            cloneTree->_size = _size;
            return cloneTree;
        }
    protected:
        LinkedBinarySearchTreeNode<K, V>* root;
        int _size;

        void replace(LinkedBinarySearchTreeNode<K, V>* node, LinkedBinarySearchTreeNode<K, V>* newNode)
        {
            LinkedBinarySearchTreeNode<K, V>* parent = node->parent;
            if (parent != 0)
            {
                if (node == parent->left)
                    parent->left = newNode;
                else
                    parent->right = newNode;
                node->parent = 0;
            }
            else
                root = newNode;

            if (newNode != 0)
                newNode->parent = parent;

            node->left = 0;
            node->right = 0;
        }

        LinkedBinarySearchTreeNode<K, V>* find(K key)
        {
            LinkedBinarySearchTreeNode<K, V>* node = root;
            while (node != 0)
            {
                int result = BinarySearchTree<K, V>::compareTo(key, node->key);
                if (result > 0)
                    node = node->right;
                else if (result < 0)
                    node = node->left;
                else
                    break;
            }
            return node;
        }

        void cloneChildren(LinkedBinarySearchTreeNode<K, V>* cloneNode, LinkedBinarySearchTreeNode<K, V>* node)
        {
            LinkedBinarySearchTreeNode<K, V>* tmpNode = node->left;
            LinkedBinarySearchTreeNode<K, V>* tmpCloneNode;
            if (tmpNode != 0)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode->key, tmpNode->value);
                tmpCloneNode->parent = cloneNode;
                cloneNode->left = tmpCloneNode;
                cloneChildren(tmpCloneNode, tmpNode);
            }

            tmpNode = node->right;
            if (tmpNode != 0)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode->key, tmpNode->value);
                tmpCloneNode->parent = cloneNode;
                cloneNode->right = tmpCloneNode;
                cloneChildren(tmpCloneNode, tmpNode);
            }
        }
    private:
};

template<typename K, typename V>
class LinkedBinarySearchTreeNode
{
    public:
        LinkedBinarySearchTreeNode(K key, V value)
        {
            this->key = key;
            this->value = value;
            parent = 0;
            left = 0;
            right = 0;
        }
        //virtual ~ArrayBinarySearchTreeNode();
        K key;
        V value;
        LinkedBinarySearchTreeNode<K, V>* parent;
        LinkedBinarySearchTreeNode<K, V>* left;
        LinkedBinarySearchTreeNode<K, V>* right;
    protected:
    private:
};
#endif // LINKEDBINARYSEARCHTREE_H

陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#ifndef ARRAYBINARYSEARCHTREE_H
#define ARRAYBINARYSEARCHTREE_H

#include <memory.h>
#include <queue>
#include "BinarySearchTree.h"

using namespace std;

template<typename K, typename V>
class ArrayBinarySearchTreeNode;

template<typename K, typename V>
class ArrayBinarySearchTree : public BinarySearchTree<K, V>
{
    public:
        ArrayBinarySearchTree(int capacity = 10240)
        {
            array = new ArrayBinarySearchTreeNode<K, V>*[capacity];
            for(int i = 1;i < capacity;++i)
                array[i] = 0;
            _size = 0;
            arrayLength = capacity;
        }
        virtual ~ArrayBinarySearchTree()
        {
            for(int i = 0;i < arrayLength;++i)
                delete array[i];
            delete [] array;
        }

        int size()
        {
            return _size;
        }

        void add(K key, V value)
        {
            int index = 1;
            while (array[index] != 0)
            {
                int result = BinarySearchTree<K, V>::compareTo(key, array[index]->key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                {
                    array[index]->value = value;
                    return;
                }

                if (index + 1 > arrayLength)
                {
                    int newLength = arrayLength * 2;
                    ArrayBinarySearchTreeNode<K, V>** newArray = new ArrayBinarySearchTreeNode<K, V>*[newLength];
                    memcpy(newArray, array, arrayLength * sizeof(ArrayBinarySearchTreeNode<K, V>*));
                    delete [] array;
                    array = newArray;
                    for(int i = arrayLength;i < newLength;++i)
                        array[i] = 0;
                    arrayLength *= 2;
                }
            }
            array[index] = new ArrayBinarySearchTreeNode<K, V>(key, value);
            ++_size;
        }

        void remove(K key)
        {
            int index = indexOf(key);
            if (index == -1)
                return;

            ArrayBinarySearchTreeNode<K, V>* node = array[index];
            int leftIndex = index * 2;
            int rightIndex = leftIndex + 1;
            if (leftIndex >= arrayLength || array[leftIndex] == 0)
            {
                if (rightIndex >= arrayLength || array[rightIndex] == 0)
                    array[index] = 0;
                else
                    moveTree(rightIndex, index);
            }
            else if (rightIndex >= arrayLength || array[rightIndex] == 0)
                moveTree(leftIndex, index);
            else
            {
                // find left-max or right-min node;
                int tmpIndex = rightIndex * 2;
                while (tmpIndex < arrayLength && array[tmpIndex] != 0)
                    tmpIndex *= 2;
                tmpIndex /= 2;
                array[index] = array[tmpIndex];
                moveTree(tmpIndex * 2 + 1, tmpIndex);
            }
            delete node;
            --_size;
        }

        V get(K key)
        {
            int index = indexOf(key);
            if (index == -1)
                throw "Key not found";
            return array[index]->value;
        }

        bool containsKey(K key)
        {
            return indexOf(key) != -1;
        }

        BinarySearchTree<K, V>* clone()
        {
            ArrayBinarySearchTree<K, V>* cloneTree = new ArrayBinarySearchTree<K, V>(arrayLength);
            for (int i = 1; i < arrayLength; ++i)
                if (array[i] != 0)
                    cloneTree->array[i] = new ArrayBinarySearchTreeNode<K, V>(array[i]->key, array[i]->value);
            cloneTree->_size = _size;
            return cloneTree;
        }
    protected:
        ArrayBinarySearchTreeNode<K, V>** array;
        int arrayLength;
        int _size;

        int indexOf(K key)
        {
            int index = 1;
            while (index < arrayLength && array[index] != 0)
            {
                int result = BinarySearchTree<K, V>::compareTo(key, array[index]->key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                    return index;
            }
            return -1;
        }

        void moveTree(int from, int to)
        {
            queue<int*> queue;
            int* pair = new int[2];
            pair[0] = from;
            pair[1] = to;
            queue.push(pair);
            while (queue.size() > 0)
            {
                pair = queue.front();
                queue.pop();
                int f = pair[0];
                int t = pair[1];
                delete [] pair;
                if (move(f, t))
                {
                    pair = new int[2];
                    pair[0] = f * 2;
                    pair[1] = t * 2;
                    queue.push(pair);
                    pair = new int[2];
                    pair[0] = f * 2 + 1;
                    pair[1] = t * 2 + 1;
                    queue.push(pair);
                }
            }
        }

        bool move(int from, int to)
        {
            // from > to
            if (from < arrayLength)
            {
                if (array[from] == 0)
                {
                    array[to] = 0;
                    return false;
                }
                array[to] = array[from];
                array[from] = 0;
                return true;
            }
            else if (to < arrayLength)
                array[to] = 0;
            return false;
        }
    private:
};

template<typename K, typename V>
class ArrayBinarySearchTreeNode
{
    public:
        ArrayBinarySearchTreeNode(K key, V value)
        {
            this->key = key;
            this->value = value;
        }
        K key;
        V value;
    protected:
    private:
};
#endif // ARRAYBINARYSEARCHTREE_H

隨機產生 1000 筆資料執行結果(因為資料不平衡，陣列很容易就記憶體不足，只跑 1000 筆)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
C#
Add LinkedBinarySearchTree Time: 10ms
Memory uage: 28304bytes
Validate: True
Remove LinkedBinarySearchTree Time: 0ms
Add ArrayBinarySearchTree Time: 30ms
Memory uage: 10460800bytes
Validate: True
Remove ArrayBinarySearchTree Time: 0ms

Java
Add LinkedBinarySearchTree Time: 0ms
Validate: true
Remove LinkedBinarySearchTree Time: 0ms
Add ArrayBinarySearchTree Time: 10ms
Validate: true
Remove ArrayBinarySearchTree Time: 10ms

C++
Add LinkedBinarySearchTree Time: 0ms
Validate: 1
Remove LinkedBinarySearchTree Time: 0ms
Add ArrayBinarySearchTree Time: 50ms
Validate: 1
Remove ArrayBinarySearchTree Time: 0ms

延伸閱讀

樹 (Tree)
二元樹 (Binary Tree)
一般樹轉二元樹
樹的走訪 (Tree Traversal)